【算法】manacher
【题解】【算法】字符串
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=;
int n,p[maxn];
char s[maxn],ss[maxn];
void manacher()
{
int mx=,id=;
int ans=;
for(int i=;i<=n;i++)//$不管
{
if(i<mx)
{
p[i]=min(p[id*-i],mx-i+);
}
else p[i]=;
while(s[i+p[i]]==s[i-p[i]])p[i]++;
if(i+p[i]->mx)
{
mx=i+p[i]-;
id=i;
}
ans=max(ans,p[i]-);
}
printf("%d\n",ans);
}
int main()
{
while(scanf("%s",ss+)==)
{
int tot=strlen(ss+);
n=;s[]='$';s[]='#';
for(int i=;i<=tot;i++)s[++n]=ss[i],s[++n]='#';
manacher();
}
return ;
}