首页 > 代码库 > BZOJ3676:[Apio2014]回文串
BZOJ3676:[Apio2014]回文串
3676: [Apio2014]回文串
Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 2665 Solved: 1164
[Submit][Status][Discuss]
Description
考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出
现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最
大出现值。
Input
输入只有一行,为一个只包含小写字母(a -z)的非空字符串s。
Output
输出一个整数,为逝查回文子串的最大出现值。
Sample Input
【样例输入l】
abacaba
【样例输入2]
www
abacaba
【样例输入2]
www
Sample Output
【样例输出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; }
BZOJ3676:[Apio2014]回文串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。