马拉车(manacher)

\(注意:本博客只作为模板，不适合刚学manacher的人看\)

\(几个关键点大概可以表示成这样\)

\(ct-p[ct]----j---ct---i----ct+p[ct]\)

\(因为p[i]<=p[j],所以p[i]=min(p[2ct-i],ct+p[ct]-i)\)

#include <bits/stdc++.h>
using namespace std;
const int maxn=51000100;
int n,p[maxn],ans;
char a[maxn],s[maxn<<1];
void init()
{
	s[0]=s[1]=‘#‘;
	for(int i=0;i<n;i++)
	{
		s[i*2+2]=a[i];
		s[i*2+3]=‘#‘;
	}
	n=n*2+2;
	s[n]=0;
}
int manacher()
{
	int maxright=0,ct,ans=0;
	for(int i=1;i<n;i++)
	{
		if(i<maxright)	p[i]=min(p[ct*2-i],p[ct]+ct-i);
		//----j----ct----i----ct+p[ct]
		//可知j=ct*2-i,但是p[i]最大是(p[ct]+ct)-i 
		else	p[i]=1;
		for(;s[i+p[i]]==s[i-p[i]];++p[i]) 
		if(p[i]+i>maxright)	maxright=p[i]+i,ct=i;
		ans=max(ans,p[i]);
	}
	return ans-1;
}
int main()
{
	cin>>a;
	n=strlen(a);
	init();
	cout<<manacher();
}

马拉车(manacher)

原文：https://www.cnblogs.com/iss-ue/p/12863392.html