Description
考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出
现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最
大出现值。
Input
输入只有一行，为一个只包含小写字母(a -z)的非空字符串s。
Output
输出一个整数，为逝查回文子串的最大出现值。
Sample Input
【样例输入l】
abacaba
abacaba
【样例输入2]
www
Sample Output
【样例输出l】
7
7
【样例输出2]
4
HINT
一个串是回文的，当且仅当它从左到右读和从右到左读完全一样。
在第一个样例中，回文子串有7个：a，b，c，aba，aca，bacab，abacaba，其中：
● a出现4次，其出现值为4：1：1=4
● b出现2次，其出现值为2：1：1=2
● c出现1次，其出现值为l：1：l=l
● aba出现2次，其出现值为2：1：3=6
● aca出现1次，其出现值为1=1：3=3
●bacab出现1次，其出现值为1：1：5=5
● abacaba出现1次，其出现值为1：1：7=7
故最大回文子串出现值为7。
【数据规模与评分】
数据满足1≤字符串长度≤300000。
这道题要求出每一个回文串，以及出现的次数。
先用马拉车算法求出每个位置最长的回文子串，可以证明：从每个位置上取出最长的回文串去枚举一定能枚举出最优解。
接着对于，每个位置的最长回文子串用SA与ST快速求出其出现的次数，然而这并非正解，回文自动机才是（话说APIO2014的时候还没有这玩意儿），那时这个算法应该是最优的了。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=;
char s[maxn],S[maxn<<];
int maxl[maxn<<];
int pos[maxn<<],maxL[maxn];
int rank[maxn],Wa[maxn],Wb[maxn],Wv[maxn],Ws[maxn],sa[maxn],r[maxn];
int lcp[maxn],len;
int mm[maxn],Min[maxn][];
bool cmp(int *p,int a,int b,int l){
return p[a]==p[b]&&p[a+l]==p[b+l];
} void DA(int n,int m){
int i,j,p,*x=Wa,*y=Wb,*t;
for(i=;i<m;i++)Ws[i]=;
for(i=;i<n;i++)++Ws[x[i]=r[i]];
for(i=;i<m;i++)Ws[i]+=Ws[i-];
for(i=n-;i>=;i--)sa[--Ws[x[i]]]=i; for(j=,p=;p<n;j<<=,m=p){
for(p=,i=n-j;i<n;i++)y[p++]=i;
for(i=;i<n;i++)
if(sa[i]>=j)
y[p++]=sa[i]-j; for(i=;i<m;i++)Ws[i]=;
for(i=;i<n;i++)++Ws[Wv[i]=x[y[i]]];
for(i=;i<m;i++)Ws[i]+=Ws[i-];
for(i=n-;i>=;i--)sa[--Ws[Wv[i]]]=y[i];
for(t=x,x=y,y=t,x[sa[]]=,i=,p=;i<n;i++)
x[sa[i]]=cmp(y,sa[i],sa[i-],j)?p-:p++;
}
} void Lcp(int n){
int i,j,k=;
for(i=;i<=n;i++)rank[sa[i]]=i;
for(i=;i<n;lcp[rank[i++]]=k)
for(k?--k:k,j=sa[rank[i]-];r[j+k]==r[i+k];++k);
}
int Qmin(int l,int r){
return min(Min[l][mm[r-l+]],Min[r-(<<mm[r-l+])+][mm[r-l+]]);
} int Query(int p,int l){
int ret=,lo,hi;
hi=rank[p];lo=;
while(lo<=hi){
int mid=(lo+hi)>>;
if(Qmin(mid,rank[p])>=l)hi=mid-;
else lo=mid+;
}
ret+=rank[p]-lo+; hi=len;lo=rank[p]+;
while(lo<=hi){
int mid=(lo+hi)>>;
if(Qmin(rank[p]+,mid)>=l)lo=mid+;
else hi=mid-;
}
return ret+hi-rank[p];
} int main(){
scanf("%s",s);
len=strlen(s);
int l=;
S[l++]='#';S[l++]='&';
for(int i=;i<len;i++){
pos[l]=i;
S[l++]=s[i];
pos[l]=i+;
S[l++]='&';
}
S[l]=;
int mx=,id;
for(int i=;i<l;i++){
maxl[i]=mx>i?min(maxl[id*-i],mx-i):;
while(S[i+maxl[i]]==S[i-maxl[i]])maxl[i]++;
if(i+maxl[i]>mx){
mx=i+maxl[i];
id=i;
}
} for(int i=;i<=l;i++)
maxL[pos[i-maxl[i]+]]=max(maxL[pos[i-maxl[i]+]],maxl[i]-);
//maxL[i]原s字符串中i位置最长回文子串
for(int i=;i<len;i++)r[i]=s[i];
DA(len+,);
Lcp(len); mm[]=-;
for(int i=;i<=len;i++){
mm[i]=(i&(i-))?mm[i-]:mm[i-]+;
Min[i][]=lcp[i];
} for(int k=;k<=mm[len];k++)
for(int i=;i+(<<k)-<=len;i++)
Min[i][k]=min(Min[i][k-],Min[i+(<<(k-))][k-]); long long ans=;
for(int i=;i<len;i++){
ans=max(ans,1ll*maxL[i]*Query(i,maxL[i]));
}
printf("%lld\n",ans);
return ;
}
然后还有一种方法，前面提过，回文自动机：
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=;
int last,cnt,ch[maxn][],fail[maxn],len[maxn],num[maxn];
long long ans=;
char s[maxn];
int find(int i,int x){
while(s[i-len[x]-]!=s[i])x=fail[x];
return x;
}
int main(){
scanf("%s",s);
fail[]=;len[]=-;cnt=;
for(int i=;s[i];i++){
int j=find(i,last);
if(ch[j][s[i]-'a'])
last=ch[j][s[i]-'a'];
else{
len[last=++cnt]=len[j]+;
fail[last]=ch[find(i,fail[j])][s[i]-'a'];
ch[j][s[i]-'a']=last;
}
num[last]++;
}
for(int i=cnt;i>=;i--)
ans=max(ans,1ll*num[i]*len[i]),num[fail[i]]+=num[i];
printf("%lld\n",ans);
return ;
}
超级短，超级简单，但还是有些地方要注意：
14行的初始化不能乱改，改了挺麻烦的；21，22行是有顺序的，写反了会死循环。