Manacher 算法学习笔记
Manacher 算法是一种支持在 \(O(n)\) 时间内求出一个长度为 \(n\) 的字符串的最长回文子串的算法。
需要注意的是，Manacher 算法只能求形如 \(aabbcbbaa\) 类的回文串，而不能处理形如 \(aabbbbaa\) 类的回文串，也就是只能求长度为奇数的回文串。所以，在最初需要对原串进行预处理，用没有出现过的字符将原串中的相邻两个字符隔开，同时要用两个不同的字符分别放在原串的开头和结尾。
如原串为 \(abbcac\)，转化后就可以是 $#a#b#b#c#a#c#^。此时再和原串中的回文子串一一对应，会发现原串的回文串长度就是新串的回文串半径的长度减一。
回到 Manacher 算法，它本身的思想是从前往后一个个递推，求出 \(p[i]\) 表示以 \(s_i\) 为中心的最长回文串的半径长度。而 \(\max(s_i-1)\) 自然就是答案。（下文简记回文子串 \(s_i\) 表示以 \(s_i\) 为中心的最长回文子串）
从前往后递推的时候，维护一个右边界最靠右的回文子串，记为 \(maxright\)，简称 \(mr\)，而回文子串的中心就被称为 \(mid\)。
由于这个回文子串是在 \(i\) 之前枚举到的，所以必然有 \(mid
\(1\). \(i \leq mr\)。由于此时 \(i\) 在回文子串 \(mid\) 内，那么就可以在这个回文子串中找到 \(i\) 的对称点，记为 \(j\)，那么根据简单的数学知识，可知 \(j=2*mid-i\)。
(1).\(j-p[i]+1 \geq 2*mid-mr\),即 回文子串 \(j\) 完全在回文子串 \(mid\) 内，那么根据回文子串内部 \(mid\) 左右两边对称的性质，就有 \(p[i]=p[j]\)。如果此时恰好 \(i+p[j]-1\) 取到 \(mr\)，那么就无法保证 \(i+p[j]\) 是否与 \(i-p[j]\) 相等，因此是 \(p[i] \geq p[j]\)。
(2).\(j-p[i]+1 \geq 2*mid-mr\)，即回文子串 \(j\) 的一部分前缀不在回文子串 \(mid\) 内。此时一定满足 \(p[i] \leq mr\)。证明如下图所示：
可以推出最左边和最右边的红色部分的子串对称，这与 \(mr\) 是回文子串 \(mid\) 的右边界矛盾。故一定有 \(p[i] \leq mr\)。但是根据回文子串 \(i\) 与左边的回文子串 \(j\) 对称，只能是 \(p[i]=mr-i+1
综上，当 \(i \leq mr\) 时，有 \(p[i] \geq \min(p[j],mr-i+1)\)。
\(2\).\(i >mr\)。此时回文子串 \(i\) 就有可能很大。直接从 \(p[i]=1\) 开始枚举即可。
综合以上两种情况，我们先求出 \(p[i]\) 的下界，并不断往外拓展，直到不能扩展为止。如果此时 \(i+p[i]-1 > mr\)，就需要更新 \(mid\) 和 \(mr\)。
下面来简单证明一下为什么这样做的时间复杂度是 \(O(n)\)。在情况 \(1\) 中，只有当 \(j-p[j]+1\) 恰好与 \(2*mid-mr\) 相等时扩展操作会执行多次。那么此时的 \(mid\) 就会更新成 \(i\)，实际上也就是 \(mr\) 在单调递增。而情况 \(2\) 也是如此，故扩展操作最多执行 \(O(n)\) 次。那么复杂度也就稳定在 \(O(n)\)。
code：
#include
#include
using namespace std;
const int N=32000005;
int ans,n,p[N];char a[N],b[N];
void init()
{
int k=0;b[k++]='$',b[k++]='#';
for(int i=0;a[i];i++) b[k++]=a[i],b[k++]='#';
b[n=k]='^';//$和^主要是防止边界问题，如果不想加也可以在while循环里特判一下
}
void manacher()
{
int mr=0,mid;//在代码实现中，通常会将mr定义为最长回文子串最右边再过去一个字符的下标，因此下面部分代码与思路有所不同
for(int i=1;i<=n;i++)
{
if(imr) mr=i+p[i],mid=i;
ans=max(ans,p[i]-1);
}
}
int main()
{
scanf("%s",a);init();manacher();printf("%d\n",ans);
return 0;
}```