首页 > 代码库 > bzoj3676 [Apio2014]回文串

bzoj3676 [Apio2014]回文串

Description

考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最大出现值。 

Input

输入只有一行,为一个只包含小写字母(a -z)的非空字符串s。 

Output

输出一个整数,为逝查回文子串的最大出现值。 

Sample Input

【样例输入l】
abacaba

【样例输入2]
www

Sample Output

【样例输出l】
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。

 

正解:回文自动机。

集训队论文里出现了回文自动机这种高级东西,于是学了一下,其实挺简单的。。

这题就是直接构造出回文自动机,统计每个回文串出现的次数,取个最值就行了。。没什么好说的。。

 

 1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <cmath> 7 #define N (300010) 8 #define il inline 9 #define RG register10 #define ll long long11  12 using namespace std;13  14 int ch[N][26],f[N],v[N],l[N],n,la,tot;15 char s[N];16 ll ans;17 18 il void add(RG int c,RG int n){19     RG int x=la; while (s[n-l[x]-1]!=s[n]) x=f[x];20     if (!ch[x][c]){21     RG int v=++tot,k=f[x]; l[v]=l[x]+2;22     while (s[n-l[k]-1]!=s[n]) k=f[k];23     f[v]=ch[k][c],ch[x][c]=v;24     }25     v[la=ch[x][c]]++; return;26 }27  28 il void work(){29     scanf("%s",s+1),n=strlen(s+1),l[++tot]=-1,f[0]=1;30     for (RG int i=1;i<=n;++i) add(s[i]-97,i);31     for (RG int i=tot;i;--i) ans=max(ans,1LL*l[i]*v[i]),v[f[i]]+=v[i];32     printf("%lld\n",ans); return;33 }34  35 int main(){36     work();37     return 0;38 }

 

bzoj3676 [Apio2014]回文串