洛谷 P3805：【模板】manacher ← 最长回文串

【题目来源】https://www.luogu.com.cn/problem/P3805https://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 k0; b[k]$, b[k]#; for(int i0; in; i) b[k]a[i],b[k]#; b[k]^; nk; }例如若原字符串为“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分两种情况讨论第一种情况imr如果 imr说明以 i 为中心的回文串还没有进行匹配。此时置 p[i]1然后开始匹配匹配完成后更新 mr 和对应的 mid 以及 p[i]。第二种情况imr1p[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]。2p[i]mr−i由对称性说明以 i 为中心的回文串可能会延伸到 mr 之外。而大于 mr 的部分还没有进行匹配所以要从mr1位置开始一个一个进行匹配直到发生失配。然后更新 mr 和对应的 mid 以及 p[i]。此时p[i]mr-i。所以在imr的条件下p[i]min(p[midmid-i],mr-i)。综上可得求 p[i] 的核心代码如下所示。if(imr) p[i]min(p[midmid-i],mr-i); else p[i]1;★ 为啥用if(imr) p[i]min(p[midmid-i],mr-i);取最小值而不是取最大值p[i] min(...)的意义是在已知信息下这个赋值给出了 p[i]的一个安全下界——即 p[i]至少有多大但可能更大。取最小值是为了保证这个初始值不超出已验证区域后续再用 while 循环暴力扩展探索真正的边界。【算法代码】#include bits/stdc.h using namespace std; const int maxn2e75; char a[maxn],b[maxn]; int p[maxn]; int n; void init() { int k0; b[k]$, b[k]#; for(int i0; in; i) b[k]a[i],b[k]#; b[k]^; nk; } void manacher() { int mr0; int mid0; for(int i0; in; i) { if(imr) p[i]min(p[midmid-i],mr-i); else p[i]1; while(b[i-p[i]]b[ip[i]]) p[i]; if(ip[i]mr) { mrip[i]; midi; } } } int main() { cina; //scanf(%s, a); nstrlen(a); init(); manacher(); int ans0; for(int i0; in; i) ansmax(ans,p[i]-1); coutansendl; return 0; } /* in: abcbabcbabcba out: 13 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/142873220https://www.acwing.com/file_system/file/content/whole/index/content/9348088/https://www.cnblogs.com/cloudplankroader/p/10988844.htmlhttps://www.acwing.com/solution/content/66912/