[Apio2014]回文串

http://www.lydsy.com:808/JudgeOnline/problem.php?id=3676

这是一道回文树裸题,具体如何建图见http://blog.csdn.net/u013368721/article/details/42100363

code:

 #include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define maxn 300005
using namespace std;
typedef long long int64;
char s[maxn];
struct ptree{
int n,last,idx,s[maxn],son[maxn][],fai[maxn],len[maxn],cnt[maxn];
void init(){n=,s[]=-,idx=,last=,fai[]=,len[]=-;}
int get_fai(int x){
while (s[n-len[x]-]!=s[n]) x=fai[x];
return x;
}
void insert(int ch){
s[++n]=ch;
int p=get_fai(last);
if (!son[p][ch]){
len[++idx]=len[p]+;
int q=idx;
fai[q]=son[get_fai(fai[p])][ch];
son[p][ch]=q;
}
cnt[last=son[p][ch]]++;
}
void count(){for (int i=idx;i>=;i--) cnt[fai[i]]+=cnt[i];}
void query(){
int64 ans=;
count();
for (int i=;i<=idx;i++) ans=max(ans,1LL*cnt[i]*len[i]);
printf("%lld\n",ans);
}
}T;
int main(){
scanf("%s",s+); T.init();
for (int i=;s[i];i++) T.insert(s[i]-'a');
T.query();
return ;
}
上一篇:通过VMware Tools 将主机windows的目录共享给linux虚拟机


下一篇:go语言实战教程:Redis实战项目应用