[APIO2014]回文串(回文自动机)
2024-10-01 14:28:37
题意
给你一个由小写拉丁字母组成的字符串 s。我们定义 s 的一个子串的存在值为这个子串在 s 中出现的次数乘以这个子串的长度。
对于给你的这个字符串 s,求所有回文子串中的最大存在值。
|S|<=300000
题解
裸的回文树,我们在每一个节点结束的最长回文后缀上记录一个cnt代表出现次数。
这个最长回文后缀T的每一个回文后缀一定也会出现和cnt[T]一样的次数。
所以倒着统计答案并使cht前移就行了。
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=;
int n,tot,len[N],fail[N],s[N],last,to[N][],cnt[N];
int L;
long long ans;
char ch[N];
void init(){
n=;tot=;
len[]=;len[]=-;
fail[]=;s[]=-;last=;
memset(to,,sizeof(to));
}
void add(int c){
s[++n]=c;
int cur,now,tmp;
for(cur=last;s[n-len[cur]-]!=c;cur=fail[cur]);
if(!to[cur][c]){
tot++;
len[tot]=len[cur]+;now=tot;
for(tmp=fail[cur];s[n-len[tmp]-]!=c;tmp=fail[tmp]);
fail[now]=to[tmp][c];
to[cur][c]=now;
}
last=to[cur][c];
cnt[last]++;
}
void count(){
for(int i=tot;i>=;i--){
cnt[fail[i]]+=cnt[i];
ans=max(1ll*cnt[i]*len[i],ans);
}
}
int main(){
scanf("%s",ch+);
L=strlen(ch+);
init();
for(int i=;i<=L;i++)add(ch[i]-'a');
count();
printf("%lld",ans);
return ;
}
最新文章
- oracle数据库迁移---windows环境下
- Spring-事物的隔离级别
- TP中二维数组的遍历输出
- Javascript 正则表达式校验数字
- PHPExcel用法有感
- TCP/IP详细说明--滑模、拥塞窗口、慢启动、Negle算法
- java第九次学习总结
- django 连接mangodb 操作
- 关于HttpSession 和 Hibernate框架中 session异同点的简单解析
- 常见26种NLP任务的练手项目
- Java之.jdk安装-Linux
- 解决VS调试Web应用无问题而部署在IIS上报500和403的问题
- Android 代码画角标 offcutView
- 十八、curator recipes之DistributedDelayQueue
- Jarvis OJ-Reverse题目Writeup
- Vue 2.0学习(五)v-bind及class与style绑定
- (转)h264中avc和flv数据的解析
- ionic新手教程第八课-(加更)从无到有说Ionic、绘图说明MVC-U-S
- List分组迭代器
- hadoop20---代理另一种方式