注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3676][Apio2014]回文串  

2015-04-23 21:17:36|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3676: [Apio2014]回文串

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 522  Solved: 162
[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

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。

Solution

回文自动机第一题 
回文自动机能够识别出所有回文串,插入回文串的后半部分,然后剩下的就和AC自动机差不多了。
本题只要沿fail树dp即可,因为如果一个节点沿fail跳的话,所经过的路径均为以这个节点为结尾的回文串

Code

/**************************************************************
    Problem: 3676
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:628 ms
    Memory:35084 kb
****************************************************************/
 
#include<cstdio>
#define N 300010
char s[N];int n,now,cur,fail[N],cnt[N],len[N],tot,las,son[N][26];long long ans;
int nn(int l){len[tot]=l;return tot++;}
int gf(int x,int n){
    while(s[n-len[x]-1]!=s[n])x=fail[x];
    return x;
}
#define cmax(a,b) (a<b?a=b:1)
int main(){
    gets(s+1),s[0]=-1;nn(0),nn(-1),fail[0]=1;
    for(n=1;s[n];cnt[las=son[cur][s[n++]]]++)
    if(s[n]-='a',cur=gf(las,n),!son[cur][s[n]]){
        now=nn(len[cur]+2);
        fail[now]=son[gf(fail[cur],n)][s[n]];
        son[cur][s[n]]=now;
    }
    for(n=--tot;n>1;n--)cnt[fail[n]]+=cnt[n],cmax(ans,1LL*cnt[n]*len[n]);
    printf("%lld\n",ans);
}
  评论这张
 
阅读(146)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018