重谈 manacher

• 名称：马拉车，即 manacher。

• 实现问题方面：处理出整字符串 \(s\) 的回文串个数、位置。

• 中心数组：数组 \(p\)，\(p_i\) 表示以第 \(i\) 个字符为中心最长回文半径。

• 预处理：将字符串间加入特殊字符（一般是 $），以及结尾和开头的特殊处理。

• 优势：马拉车的时空复杂度和字符集的大小无关，为 \(O(n)\)。

实现

马拉车最核心的思想就是利用前面的信息得到后面的信息。

最重要的变量：\(\texttt{mr,mid}\)

\(\texttt{mr}\) 表示扩展到最远的回文半径，\(\texttt{mid}\) 表示最远回文半径的中心。

如果一个点的位置 \(pos\) 满足 \(pos\in[mid,mr]\)，我们可以预处理出这个点的答案：\(\min(p[2\times mid -pos],mr-i+1)\)。这是由对称得到的，也就是说利用 \(i\) 与 \(mid\) 对称的点的答案，不难看出在 \(mr-i+1\) 范围内一定是合法的。否则我们暴力扩展，容易发现，每暴力扩展一次，\(mr\) 同时也一定会扩展一次。根据 \(mr\) 是一直递增的，容易分析出时间复杂度为 \(O(n)\)。

• 代码：

#include<bits/stdc++.h>
#define N 22000005
using namespace std;
int n,cnt;
char t[N],s[N];
void build()
{
	n=strlen(t+1);
	s[0]='>',s[1]='#';
	for(int i=1;i<=n;i++)
		s[i<<1]=t[i],s[(i<<1)|1]='#';
	n=(n<<1)|1;
}
int ans;
int mr,mid;
int p[N];
void solve()
{
	for(int i=1;i<=n;i++)
	{
		if(i<=mr) p[i]=min(p[mid*2-i],mr-i+1);
		while(s[i-p[i]]==s[i+p[i]]) p[i]++;
		if(i+p[i]>mr) mr=i+p[i]-1,mid=i;
		ans=max(ans,p[i]-1);
	}
}
int main()
{
	scanf("%s",t+1);
	build();
	solve();
	printf("%d",ans);
	return 0;
}

只有彻底明白一个算法，才不会在考场上后悔。