A1280. 最长双回文串

学习了回文树,地址:http://blog.csdn.net/u013368721/article/details/42100363;

这个题就是正这反着加一遍就好,一开始我想的是枚举每个位置,然后一直按fail跳,再接上跳完的位置的len,后来想了不行,一个很长的全是a的串就可以卡成n^2。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=;
int m,len[maxn],n,nxt[maxn][],fail[maxn],last,now,ss[maxn],tot,res[maxn],ans;
char s[maxn];
int getfail(int x){
while(ss[m-len[x]-]!=ss[m])x=fail[x];
return x;
}
int add(char c){
int x=c-'a';
ss[++m]=x;
int cur=getfail(last);
if(!nxt[cur][x]){
len[tot]=len[cur]+;
fail[tot]=nxt[getfail(fail[cur])][x];
nxt[cur][x]=tot;
++tot;
}
last=nxt[cur][x];
return len[last];
}
void init(){
memset(nxt,,sizeof(nxt));
fail[]=;len[]=;
len[]=-;last=;tot=;
ss[]=-;m=;
}
int main(){
scanf("%s",s+);n=strlen(s+);
init();for(int i=;i<=n;++i){res[i]=add(s[i]);}
init();for(int i=n;i>=;--i){ans=max(ans,add(s[i])+res[i-]);}
cout<<ans;
return ;
}
上一篇:ASP.NET内置对象一


下一篇:Linux进程间通信之管道