AcWing 3188：Manacher 算法 → 最长回文子串
【题目来源】
https://www.acwing.com/problem/content/3190/
【题目描述】
给定一个长度为 n 的由小写字母构成的字符串，求它的最长回文子串的长度是多少。
【输入格式】
一个由小写字母构成的字符串。
【输出格式】
输出一个整数，表示最长回文子串的长度。
【数据范围】
1≤n≤10^7
【输入样例】
abcbabcbabcba
【输出样例】
13
【算法分析】
Manacher算法，谐称马拉车算法，是用于在 O(n) 时间复杂度内找到字符串中最长回文子串的高效算法。核心内容如下。
★ 基于原字符串 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 中的字符个数+1，因此插入分隔符 # 后所得的字符串中的字符个数为“偶数+奇数=奇数”。再加上 $、^ 两个字符后，生成的字符串 b 中的字符个数仍然为奇数。换种说法，即这样处理后，使得原串 a 中的任意回文串在 b 串中都表示为奇数长度串的形式，且都有一个中心点。
★ Manacher 算法主要内容解析
设 p[i] 表示以字符串第 i 位为中心的回文串的最大半径。
设 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;【算法代码】
#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://www.cnblogs.com/cloudplankroader/p/10988844.html
https://www.acwing.com/file_system/file/content/whole/index/content/9348088/
https://www.acwing.com/solution/content/66912/
原文地址：https://blog.csdn.net/hnjzsyjyj/article/details/142873220
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！