- 2022tysc0158 的博客
【模板】manacher
- 2024-7-16 13:41:13 @
#include<iostream>
#include<cstdio>
using namespace std;
char s[22000010],ch;
int c,r,p[22000010],n=1,ans;
int main(){
s[0]='~',s[1]='|';
while(scanf(" %c",&ch)!=EOF)s[++n]=ch,s[++n]='|';
for(int i=1;i<=n;i++){
if(i<r)p[i]=min(r-i+1,p[(c<<1)-i]);
while(s[i-p[i]]==s[i+p[i]])p[i]++;
if(i+p[i]-1>=r)r=i+p[i]-1,c=i;
ans=max(ans,p[i]);
}
printf("%d",ans-1);
}
//对应洛谷 P3805 【模板】manacher