Manacher算法——找字符串最长的回文子串
1、经典办法:在两头和每个字符加上一个特殊字符,相当于加了一个轴,从头遍历判断回文字符,得到的长度/2就是结果。时间复杂度:O(N^2)
2、Manacher(和经典办法相似,但有加速过程)时间复杂度:O(N):在两头和每个字符加上一个特殊字符,相当于加了一个轴
普及概念:
回文范围=回文直径=2*回文半径=从一个位置为中心出发扩出来的回文范围
最右回文边界:从左往右扩,用一个变量记录最右的边界R,忽略是由哪个字符开始扩的
在此需要记录一个使得右边界更新到更右的中心C。该变量与左右回文边界是伴生的。
可以确定k的回文范围至少是l'~r',继续判断R后的下一个字符
2、Manacher(和经典办法相似,但有加速过程)时间复杂度:O(N):在两头和每个字符加上一个特殊字符,相当于加了一个轴
普及概念:
回文范围=回文直径=2*回文半径=从一个位置为中心出发扩出来的回文范围
最右回文边界:从左往右扩,用一个变量记录最右的边界R,忽略是由哪个字符开始扩的
在此需要记录一个使得右边界更新到更右的中心C。该变量与左右回文边界是伴生的。
每一个位置扩出来的回文半径记录在一个数组里
此处设变量:
C:中心
L:左边界(根据最右回文边界和中心C可得出。非最左回文边界,C和R组成回文半径时,对应找到的)
R:最右回文边界
(1)第一种情况:当前字符在最右回文边界外面,暴力扩。不保证每次O(1),但总体能做到:O(N)
(2)第二种情况:当前字符k在最右回文边界里面。
A、 k的对称点k'在左边界L内 每次O(1),最多发生N次,O(N)
不用扩,k的对称点k'的回文范围就是k的回文范围。
B、 k的对称点k'不在左边界L内 每次O(1),最多发生N次,O(N)
不用扩,字符k的回文半径是k~R
例子:
可以确定k的回文范围至少是l'~r',继续判断R后的下一个字符
例子: