适用场景

专用于快速查找字符中的最长回文

细节

在回文问题中,我们有时会使用中心扩散的方式进行求解,但直接使用中心扩散的方式.需要考虑回文为偶数个以及奇数个的情况,增加了算法的复杂度
在Manacher算法中,使用了较为巧妙的方式进行处理数据,使所有的回文变为奇回文

在字符串前后使用不同的字符用做标记字符串的开始以及结束, 且该字符不会在目标字符串中出现.目的是为了在进行中心扩散时,无需考虑边界
所有字符之间使用另一个特殊字符进行间隔(与作为开始结束的字符也不同)

例如 kabakdkabacdc 处理成 ^#k#a#b#a#k#d#k#a#b#a#c#d#c#$

index	0	1	2	3	4	5	6	7	8	9	1 0	1 1	1 2	1 3	1 4	1 5
处理后的字符串	^	#	k	#	a	#	b	#	a	#	k	#	d	#	k	#
	1 6	1 7	1 8	1 9	2 0	2 1	2 2	2 3	2 4	2 5	2 6	2 7	2 8
	a	#	b	#	a	#	c	#	d	#	c	#	$

除此之外还使用了回文对称的特点对查询的过程进行加速,将已知的回文长度存储服务于后续的回文长度统计
PS: 存储时可以记录当前点为中心的整个回文长度,或者是记录半个长度(包含中点或者不包含),此处我是不包含中点的半个长度
那么表格将会变成这样(^#$ 都为0)

index	0	1	2	3	4	5	6	7	8	9	1 0	1 1	1 2	1 3	1 4	1 5
处理后的字符串	^	#	k	#	a	#	b	#	a	#	k	#	d	#	k	#
不包含中点的回文半长	^	#	1	#	1	#	5	#	1	#	1	#	9	#	1	#
	1 6	1 7	1 8	1 9	2 0	2 1	2 2	2 3	2 4	2 5	2 6	2 7	2 8
	a	#	b	#	a	#	c	#	d	#	c	#	$
	1	#	9	#	1	#	1	#	3	#	1	#	$

那么是怎么使用已有的信息进行加速呢

假设当前我们已经遍历到了第14位,那我们其实已经知道了以第12位的d为中心的最大回文半长是9,第14位的k包含在这个半径之内
所以一定能以第12位的d为对称轴,查到第12位的k的对称点第10位的k,因为第10位的k与第12位的d的距离加上自身的最大回文半径未超过第12位的d的回文半径,所以第14位的k能够直接使用第12位的k已计算的半径,然后再继续使用中心扩展进行尝试是否还能扩大以第14位的k为中心的回文范围

假设当我们遍历到第18位的b,还是找对称点第6位的b,因为第12位的d与第12位的d的距离加上自身的最大回文半径超过第12位的d的回文半径,所以第18位的b只能获取第6位的b未超出部分长度,虽然第6位的b最大回文半径是5,但能映射的最大值是3.因为d只能保证自身回文范围内的是对称的.
接下来第18位的b就能在这个范围的基础上继续中心扩展,最终确定最大回文范围

在算法的实现过程中,我们常常会缓存对称点加上半径的长度,所以也可以这样计算

所以可以直接同时取和计算未超出部分,取最小值即可.

1	当前需要计算点的初始回文半径 = min(映射位的最大回文半径, 未超出对称轴最大回文半径的长度)

实现

impl Solution {
    fn expand_str(s:&String) -> Vec<char> {
        let mut chs = Vec::new();
        chs.push('^');
        chs.push('#');
        for ch in  s.chars(){
            chs.push(ch);
            chs.push('#');
        }
        chs.push('$');
        chs
    }
    pub fn longest_palindrome(s: String) -> String {
        if  s.len() <= 1 {
            return s;
        }
        
        let chs = Self::expand_str(&s);
        let mut palindromic_len = vec![0; chs.len()];

        let mut center_index = 0 as usize;
        let mut can_cache_range = 0 as usize;

        for index in 1..chs.len() - 1 {

            if can_cache_range > index {
                palindromic_len[index] = palindromic_len[center_index * 2 - index].min(can_cache_range - index);
            } else {
                palindromic_len[index] = 0 as usize;
            }

            while chs[index + palindromic_len[index] + 1] == chs[index - palindromic_len[index] - 1] {
                palindromic_len[index] += 1;
            }

            if index + palindromic_len[index] > can_cache_range {
                can_cache_range = index + palindromic_len[index];
                center_index = index;
            }
        }
        
        let mut max = (0, 0);
        for (k ,&v) in palindromic_len.iter().enumerate() {
            if max.1 < v {
                max = (k ,v);
            }
        }
        let start = (max.0 - max.1)/ 2;
        return String::from(&s[start..(start + max.1)]);
    }
}

适用场景

细节

实现

参考链接