2342: [Shoi2011]双倍回文
Time Limit: 10 Sec Memory Limit: 128 MB
Description
Input
输入分为两行，第一行为一个整数，表示字符串的长度，第二行有个连续的小写的英文字符，表示字符串的内容。
Output
输出文件只有一行，即：输入数据中字符串的最长双倍回文子串的长度，如果双倍回文子串不存在，则输出0。
Sample Input
16
ggabaabaabaaball
Sample Output
12
HINT
N<=500000
这道题显然是想考我们manachermanachermanacher算法，我们知道，manachermanachermanacher算法可以在O（n）O（n）O（n）的时间内求出每个点的最长回文半径。既然这样的话，我们直接通过求出的最长回文半径来更新答案即可。但是这里有个小技巧，如果我们直接使用最长回文半径来更新的话会直接TTT掉，于是我们可以先把这些半径处理一下，消去常数就可以跑过了。
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define N 500005
char t[N],s[N<<1];
int n=0,tot,r[N<<1],f[N<<1],pos=0,id=0,ans=0;
int main(){
scanf("%d%s",&n,t);
s[0]='@';
for(int i=0;i<n;++i){
s[++tot]='#';
s[++tot]=t[i];
}
s[++tot]='#';
s[++tot]='*';
for(int i=1;i<tot;++i){
if(pos>i)r[i]=min(r[id*2-i],pos-i+1);
else r[i]=0;
while(s[i-r[i]]==s[i+r[i]])++r[i];
if(i+r[i]-1>pos)pos=i+r[i]-1,id=i;
}
//消去常数
for(int i=0;i<tot;++i)f[i]=(r[i<<1|1]-1)>>1;
for(int i=0;i<tot;++i)
for(int j=f[i]>>1;j&&((j<<2)>ans);--j)
if(f[i+j]>=j&&f[i-j]>=j)ans=max(ans,j<<2);
printf("%d",ans);
}