P3805 【模板】manacher算法

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
char data[22000666];
int p[22000666],cnt,ans;
void read(){
	char c=getchar();
	data[0]=‘~‘,data[cnt=1]=‘|‘;
	while(c<‘a‘||c>‘z‘){
		c=getchar();
	}
	while(c>=‘a‘&&c<=‘z‘){
		data[++cnt]=c;
		data[++cnt]=‘|‘;
		c=getchar();
	}
}
int main(){
	read();
	for(int t=1,r=0,mid=0;t<=cnt;++t){
        if(t<=r){
			p[t]=min(p[mid*2-t],r-t+1);
		}
        while(data[t-p[t]]==data[t+p[t]]){
			p[t]++;
		}
        if(p[t]+t>r){
			r=p[t]+t-1,mid=t;
		}
        if(p[t]>ans){
			ans=p[t];
		}
	}
	printf("%d",ans-1);
	return 0;
}