洛谷 P3805：【模板】manacher ← 最长回文串
【题目来源】
https://www.luogu.com.cn/problem/P3805
https://www.acwing.com/problem/content/3190/
【题目描述】
给出一个只由小写英文字符 a, b, c, ..., y, z 组成的字符串 S，求 S 中最长回文串的长度。
字符串长度为 n。
【输入格式】
一行小写英文字符 a, b, c, ..., y, z 组成的字符串 S。
【输出格式】
一个整数表示答案。
【输入样例】
aaa
【输出样例】
3
【算法分析】
Manacher 算法，谐称马拉车算法，是用于在O(n)时间复杂度内找到字符串中最长回文子串的高效算法。核心内容如下。
备注：此图由豆包 AI 创作生成
★ 基于原字符串 a 生成由特殊字符分割的字符串 b
方法：在原字符串 a 的首尾及每两个相邻字符间插入未在原串中出现的字符作为分隔符。分隔符的选择依据是其未在原串中出现，通常可以选择#号。如果原字符串中有 # 号，就需要插入其他未在原串中出现的分隔符。此外，为了避免在搜索回文子串时总是判断是否越界，通常在原字符串 a 的首端加 $ 号，在尾端加 ^ 号等原串中未出现的特殊字符。
void init() { int k=0; b[k++]='$', b[k++]='#'; for(int i=0; i<n; i++) b[k++]=a[i],b[k++]='#'; b[k++]='^'; n=k; }例如，若原字符串为“google”，那么插入分隔符 # 及 $、^ 之后，变为了“$#g#o#o#g#l#e#^”。
意义：在设计 Manacher 算法时，可以统一考虑为作用于包含奇数个字符的字符串。
这是因为不论原字符串 a 中包含奇数个字符还是偶数个字符，其插入的分隔符的个数，如 # 号的个数一定等于原字符串 a 中的字符个数+1。因此，若原字符串 a 包含奇数个字符，则插入分隔符 # 后所得的字符串 b 中的字符个数为“奇数+偶数=奇数”。若原字符串 a 包含偶数个字符，则插入分隔符 # 后所得的字符串 b 中的字符个数为“偶数+奇数=奇数”。例如："aba"-->"#a#b#a#"（长度是7）、"abba"-->"#a#b#b#a#"（长度是9）。
之后，首尾再加上 $、^ 两个字符后，生成的字符串 b 中的字符个数仍然为奇数。换种说法，即这样处理后，使得原串 a 中的任意回文串在 b 串中都表示为奇数长度串的形式，且都有一个中心点。
★ Manacher 算法主要内容解析
设p[i]表示以字符串第 i 位为中心的回文串的最大半径，即回文半径。由下图易知，原字符串 a 中回文串的长度就是添加特殊字符 # 之后的字符串 b 的回文半径 -1。
设mr为之前得到的最长回文子串的右端点位置的最大值，并且设取得这个最大值的回文子串的中心位置为 mid，分两种情况讨论：
第一种情况：i>mr
如果 i>mr，说明以 i 为中心的回文串还没有进行匹配。此时，置 p[i]=1，然后开始匹配，匹配完成后更新 mr 和对应的 mid 以及 p[i]。
第二种情况：i<=mr
（1）p[i]<mr−i
下图中 2*mid-mr 是 mr 关于 mid 的对称点，j 是 i 关于 mid 的对称点，可知j = 2*mid - i。
且据 p[i]<mr−i， 可知 i 的回文区域（i 附近的黄色区域部分）位于之前求得的mid 的回文区域[2*mid-mr, mr]的内部，为了满足回文串的对称性，故其必与已经求得的 j 的回文区域（j 附近的黄色区域部分）相同且关于 mid 对称，此时p[i]=p[j]=p[2*mid-i]。
（2）p[i]>=mr−i
由对称性，说明以 i 为中心的回文串可能会延伸到 mr 之外。而大于 mr 的部分还没有进行匹配，所以要从mr+1位置开始一个一个进行匹配，直到发生失配。然后更新 mr 和对应的 mid 以及 p[i]。此时，p[i]=mr-i。
所以，在i<=mr的条件下，p[i]=min(p[mid+mid-i],mr-i)。
综上，可得求 p[i] 的核心代码如下所示。
if(i<=mr) p[i]=min(p[mid+mid-i],mr-i); else p[i]=1;★ 为啥用if(i<=mr) p[i]=min(p[mid+mid-i],mr-i);取最小值，而不是取最大值？
p[i] = min(...)的意义是：在已知信息下，这个赋值给出了 p[i]的一个安全下界——即 p[i]至少有多大，但可能更大。取最小值，是为了保证这个初始值不超出已验证区域，后续再用 while 循环暴力扩展，探索真正的边界。
【算法代码】
#include <bits/stdc++.h> using namespace std; const int maxn=2e7+5; char a[maxn],b[maxn]; int p[maxn]; int n; void init() { int k=0; b[k++]='$', b[k++]='#'; for(int i=0; i<n; i++) b[k++]=a[i],b[k++]='#'; b[k++]='^'; n=k; } void manacher() { int mr=0; int mid=0; for(int i=0; i<n; i++) { if(i<=mr) p[i]=min(p[mid+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 main() { cin>>a; //scanf("%s", a); n=strlen(a); init(); manacher(); int ans=0; for(int i=0; i<n; i++) ans=max(ans,p[i]-1); cout<<ans<<endl; return 0; } /* in: abcbabcbabcba out: 13 */
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/142873220
https://www.acwing.com/file_system/file/content/whole/index/content/9348088/
https://www.cnblogs.com/cloudplankroader/p/10988844.html
https://www.acwing.com/solution/content/66912/