算法简介
Manacher 算法用于求解一串字符串中的最长回文子串的长度。
如:abab 的最长回文子串的长度为3。
时间复杂度
$ O(n) $
实现原理
1.构造
回文串有两种情况:
情况1:abba,其对称轴在两字符中间
情况2:abcba,其对称轴在中间字符上
由于 Manacher 算法只能处理第二种情况,所以要对给定字符串进行重新构造,构造方法如下:
例:对字符串 abbcac 进行构造
1.首先在字符串首段和末端添加开始符和结束符,一般用'$'和'^'表示。
2.对于每个字符,保证其左右两侧分别有一个'#'。那么原字符串就变为 $#a#b#b#c#a#c#^,其任意回文子串都满足情况2
2. 算法思想
设数组 p[i]:以字符 a[i] 为中心的最大的回文串的半径长度。
处理步骤为从前向后枚举,过程中不断维护右边界最靠右的回文串。
其中 mid 为回文串对称轴位置,maxright(后简称为 mr )为最右边界。
对于遍历到的某个 a[i] 可以分为三种情况
① i 在内部且对称点回文串在内部
j 为以 mid 为对称轴的 i 的对称点,由于该区间内的字符串都是以 mid 为中心对称的,所以红色标注的区域也是对称的。
那么此时有 p[i] = p[j]。
② i 在内部且对称点的回文串在外部
这里可得 i 的右侧边界一定等于 mr。
因为若超出的话,i 的红色区域右侧画斜杠部分与左侧部分对称,则与 j 的斜杠部分相同,则白色区域部分并不是以 mid 为中心的,边界最靠右的回文子串,所以 p[i] 最大只能到 mr 。
③ i 在外部
在外部则重新开始计算,令 p[i] = 1,然后不断对比求出 p[i]。
算法代码
const int N = 2e7+10;
int p[N];
char a[N],b[N];
// n 为题目给出的原字符串
int manacher(int n) {
int k = 0;
b[k ++ ] = '$',b[k ++ ] = '#';
for (int i = 0 ; i < n ; i ++ ) b[k ++ ] = a[i], b[k ++ ] = '#';
b[k ++ ] = '^';
int mid,mr = 0;
for (int i = 1 ; i < k ; i ++ ) {
if(i < mr) p[i] = min(p[2 * mid - i] , mr - i);
else p[i] = 1;
while(b[i + p[i]] == b[i - p[i]]) p[i] ++ ;
if(i + p[i] > mr) {
mr = i + p[i];
mid = i;
}
}
int ans = 0;
for (int i = 0 ; i < k ; i ++ ) ans = max(ans,p[i]);
return ans - 1;
}