首页 > 代码库 > BZOJ 3676 [Apio2014]回文串（回文树）
BZOJ 3676 [Apio2014]回文串（回文树）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=3676
【题目大意】
考虑一个只包含小写拉丁字母的字符串s。
我们定义s的一个子串t的"出现值"为t在s中的出现次数乘以t的长度。
求s的所有回文子串中的最大出现值。
【题解】
我们对给出串建立回文树，统计每个回文串出现次数和长度，相乘取组大即可
【代码】
#include <cstdio>#include <algorithm>#include <cstring> using namespace std;const int N=300010,S=26;int all,son[N][S],fail[N],cnt[N],len[N],text[N],last,tot;int newnode(int l){ for(int i=0;i<S;i++)son[tot][i]=0; cnt[tot]=0,len[tot]=l; return tot++;}void init(){ last=tot=all=0; newnode(0),newnode(-1); text[0]=-1,fail[0]=1;}int getfail(int x){ while(text[all-len[x]-1]!=text[all])x=fail[x]; return x;}void add(int w){ text[++all]=w; int x=getfail(last); if(!son[x][w]){ int y=newnode(len[x]+2); fail[y]=son[getfail(fail[x])][w]; son[x][w]=y; }cnt[last=son[x][w]]++;}void count(){for(int i=tot-1;~i;i--)cnt[fail[i]]+=cnt[i];}char s[N];int main(){ while(~scanf("%s",s)){ int n=strlen(s); init(); for(int i=0;i<n;i++)add(s[i]-‘a‘); count(); long long ans=0; for(int i=0;i<tot;i++)ans=max(ans,1LL*cnt[i]*len[i]); printf("%lld\n",ans); }return 0;}BZOJ 3676 [Apio2014]回文串（回文树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。