[BZOJ2342]双倍回文

时间:2021-03-26 13:43:56

[BZOJ2342]双倍回文

对每个大中心暴力找小中心即可。

代码:

 #include<iostream>
#include<cstdio>
#include<cstring>
#define M 1000010
using namespace std;
int n,ans,l;
int len[M];
char s[M],a[M];
void change()
{
s[]=s[]='#';
for(int i=;i<n;i++)
{
s[i*+]=a[i];
s[i*+]='#';
}
n=n*+;
s[n]=;
}
void manacher()
{
int mx=,mid;
for(int i=;i<n;i++)
{
if(i<mx) len[i]=min(len[mid*-i],mx-i);
else len[i]=;
while(s[i-len[i]]==s[i+len[i]]) len[i]++;
if(i+len[i]>mx)
{
mx=i+len[i];
mid=i;
}
}
}
int main()
{
scanf("%d",&n);
scanf("%s",a);
change();
manacher();
for(int i=;i<=n;i+=)
{
l=(i-len[i]+i+)/;
if(l%==) l++;
while(l<=i&&l+len[l]<i) l+=;
ans=max(ans,((i-l)/)*);
}
printf("%d",ans);
return ;
}