求最长双回文串,正反建回文树求最大。
题目链接:http://www.tsinsen.com/ViewGProblem.page?gpid=A1280
By:大奕哥
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+;
const int M=; struct Palindromic_Tree{
int nex[N][M];
int fail[N];
int cnt[N];
int num[N];
int len[N];
int S[N];
int last;
int n;
int p;
int newnode(int l)
{
for(int i=;i<M;++i)nex[p][i]=;
cnt[p]=;
num[p]=;
len[p]=l;
return p++;
}
void init()
{
p=;
newnode();
newnode(-);
last=;
n=;
S[n]=-;
fail[]=;
}
int get_fail(int x){
while(S[n-len[x]-]!=S[n])x=fail[x];
return x;
}
int add(int c){
c-='a';
S[++n]=c;
int cur=get_fail(last);
if(!nex[cur][c]){
int now=newnode(len[cur]+);
fail[now]=nex[get_fail(fail[cur])][c];
nex[cur][c]=now;
num[now]=num[fail[now]]+;
}
last=nex[cur][c];
cnt[last]++;
return len[last];
}
void count(){
for(int i=p-;i>=;--i)cnt[fail[i]]+=cnt[i];
}
}T;
char s[N];
int l[N];
void solve()
{
T.init();
int ll=strlen(s);
for(int i=ll-;i>=;--i)
{
l[i]=T.add(s[i]);
}
T.init();int ans=;
for(int i=;i<ll-;++i)
{
int tmp=T.add(s[i]);ans=max(ans,l[i+]+tmp);
}
printf("%d\n",ans);
}
int main()
{
while(~scanf("%s",s))solve();
return ;
}