考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出
现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最
大出现值。
考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出
现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最
大出现值。
输入只有一行，为一个只包含小写字母(a -z)的非空字符串s。
输出一个整数，为逝查回文子串的最大出现值。
【样例输出l】
7
【样例输出2]
4
思路{回文自动机裸题啊！直接构出回文自动机统计本质不同的串分别有多少个，然后一一比较就可以了。}
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define inf (1<<30)
#define il inline
#define RG register
#define LL long long
#define maxx 300010
using namespace std;
char s[maxx];int nxt[maxx][28],cnt[maxx],f[maxx],num[maxx],len[maxx],l,cc;LL Ans;
il void Insert(RG int n,RG int c){
RG int P=l;while(s[n-len[P]-1]!=s[n])P=f[P];
if(!nxt[P][c]){
len[++cc]=len[P]+2;RG int pp=f[P];
while(s[n-len[pp]-1]!=s[n])pp=f[pp];
f[cc]=nxt[pp][c],nxt[P][c]=cc;
}l=nxt[P][c];cnt[l]++;
}
il void count(){for(RG int i=cc;i!=1;--i)cnt[f[i]]+=cnt[i];}
il void getans(){for(RG int i=cc;i!=1;i--)Ans=max(Ans,(LL)len[i]*cnt[i]);printf("%lld",Ans);}
il void work(){
scanf("%s",s+1);RG int LEN=strlen(s+1);f[0]=1,len[++cc]=-1;
for(RG int i=1;i<=LEN;++i)Insert(i,s[i]-‘a‘+1);count();getans();
}
int main(){
work();
return 0;
}
原文：http://www.cnblogs.com/zzmmm/p/7141945.html