manacherP

O(n)求回文子串（不是回文子序列！）

题目

#include<bits/stdc++.h>
using namespace std;
#define maxn 30001000
#define MOD 998244353
#define ll long long
#define endl '\n'

int p[maxn],a[maxn];
int main() {
	string s;
	cin>>s;
	int n=s.length();
	for(int i=1;i<=n;i++){
		a[2*i-1]=-1;
		a[2*i]=s[i-1]-'a'+1;
	}
	//a[1]=-114514;bug4:a[1]=-1,a[0]=-114514;
	//e.g. -1 1 -1 1 -1这时a[3]才能被记录为回文数 
	a[0]=-114514;
	a[2*n+1]=-1;
	int ans=0;
	int r=0,mid=0;
	//for(int i=1;i<=2*n+1;i++) cout<<a[i]<<":";
	//cout<<endl;
	for(int t=1;t<=2*n+1;t++){
		if(t<r){
			p[t]=min(p[mid*2-t],r-t+1);
		}else{
			p[t]=1;
		}
		while(1){
			//if(a[t+p[t]+1]!=a[t-p[t]-1]) break;
			//bug2:[下一个]就是t+p[t]
			//e.g.单独一个a,p[t]=1,下一个:1+p[t]; 
			if(a[t+p[t]]!=a[t-p[t]]) break;
			p[t]++;
		}
		if(t+p[t]>r){//mid-r是“为mid-r内的t作保证用的”,因此这里>=也是同样效果 
			//r=t+p[t];同bug2,这里也应该是:
			r=t+p[t]-1; 
			mid=t;
		}
		ans=max(ans,p[t]);
	}
	cout<<ans-1;
	return 0;
}