当前位置:首页 > Windows程序 > 正文

BZOJ3676:[Apio2014]回文串

2024-03-31 Windows程序

标签:

3676: [Apio2014]回文串 Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 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

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]回文串

温馨提示: 本文由Jm博客推荐,转载请保留链接: https://www.jmwww.net/file/39097.html

Jm-杰米博客Jamie
草根站长的技术交流乐园!IT不会不要紧快来好好学习吧!
  • 20786文章总数
  • 7494595访问次数
  • 建站天数
  • 友情链接