题意

给你一个由小写拉丁字母组成的字符串 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 ;
}

最新文章

  1. oracle数据库迁移---windows环境下
  2. Spring-事物的隔离级别
  3. TP中二维数组的遍历输出
  4. Javascript 正则表达式校验数字
  5. PHPExcel用法有感
  6. TCP/IP详细说明--滑模、拥塞窗口、慢启动、Negle算法
  7. java第九次学习总结
  8. django 连接mangodb 操作
  9. 关于HttpSession 和 Hibernate框架中 session异同点的简单解析
  10. 常见26种NLP任务的练手项目
  11. Java之.jdk安装-Linux
  12. 解决VS调试Web应用无问题而部署在IIS上报500和403的问题
  13. Android 代码画角标 offcutView
  14. 十八、curator recipes之DistributedDelayQueue
  15. Jarvis OJ-Reverse题目Writeup
  16. Vue 2.0学习(五)v-bind及class与style绑定
  17. (转)h264中avc和flv数据的解析
  18. ionic新手教程第八课-(加更)从无到有说Ionic、绘图说明MVC-U-S
  19. List分组迭代器
  20. hadoop20---代理另一种方式

热门文章

  1. Unity5.0 状态机新增的entry/exit
  2. CorelDRAW升级计划--如何购买
  3. vue 中判断向上滚动还是向下滚动
  4. Eclipse中修改GIT分支名称
  5. 使用highcharts动态绘制折线图——so easy
  6. 浅谈自底向上的Shell脚本编程及效率优化
  7. vue如何根据返回的值对元素进行样式渲染
  8. pytorch 3 activation 激活函数
  9. 小学生绞尽脑汁也学不会的python(面对对象-----成员)
  10. centos7下部署FastDFS分布式文件系统