学习一波后缀自动机

求字符串$S$的所有出现次数不为1的子串的出现次数乘上该子串长度的最大值

 #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#define rep(i,s,t) for(register int i=(s);i<=(t);++i)
#define dwn(i,s,t) for(register int i=(s);i>=(t);--i)
#define ren for(register int i=fst[x];i;i=nxt[i])
#define Fill(x,t) memset(x,t,sizeof(x))
#define ll long long
#define inf 2139062143
#define MAXN 2001000
using namespace std;
char s[MAXN];
int n,rt,lst,tr[MAXN][],tot,sz[MAXN],mxlen[MAXN],rnk[MAXN],cnt[MAXN],fa[MAXN];
ll ans;
inline void extend(int c)
{
int p=lst,np=lst=++tot;mxlen[np]=mxlen[p]+,sz[np]=;
for(;p&&!tr[p][c];p=fa[p]) tr[p][c]=np;
if(!p) {fa[np]=rt;return ;}
int q=tr[p][c];if(mxlen[q]==mxlen[p]+) {fa[np]=q;return ;}
int nq=++tot;mxlen[nq]=mxlen[p]+;
memcpy(tr[nq],tr[q],sizeof(tr[nq]));
fa[nq]=fa[q],fa[np]=fa[q]=nq;
for(;p&&tr[p][c]==q;p=fa[p]) tr[p][c]=nq;
}
void build()
{
rep(i,,tot) cnt[mxlen[i]]++;rep(i,,n) cnt[i]+=cnt[i-];
rep(i,,tot) rnk[cnt[mxlen[i]]--]=i;int p;
dwn(i,tot,)
{
p=rnk[i],sz[fa[p]]+=sz[p];
if(sz[p]>) ans=max(ans,1LL*sz[p]*mxlen[p]);
}
}
int main()
{
rt=lst=tot=;scanf("%s",s+);n=strlen(s+);
rep(i,,n) extend(s[i]-'a');
build();printf("%lld\n",ans);
}

最新文章

  1. PostGIS(解压版)安装
  2. [LeetCode] Valid Palindrome 验证回文字符串
  3. 《编写可维护的JavaScript》——JavaScript编码规范(七)
  4. NET中的类型和装箱/拆箱原理
  5. 旋转屏幕时,假如自定义的xib大小变了,可能是这个属性没有修改
  6. 替换NavigationController里面的返回按钮
  7. Base64笔记
  8. 第五章 使用 SqlSession
  9. VirtualBox: How to config higher screen resolution
  10. 网站开发进阶(三)Windows NAT端口映射
  11. Linux的文件类型
  12. 【工利其器】必会工具之(二)Android开发者官网篇
  13. IT题库-134 | String、StringBuffer和StringBuilder的区别
  14. PHP 多维数组排序 函数怎么保持数字键不被重新索引
  15. Complete Binary Search Tree
  16. python--第二十天总结(Django的一些注意)
  17. android开发学习——day6
  18. hdu 2266 dfs
  19. JSP--JDBC技术
  20. Druid如何自动根据URL自动识别DriverClass的

热门文章

  1. [NOIP2001] 提高组 洛谷P1024 一元三次方程求解
  2. input文本框的value属性在页面中不随输入的数据而变化
  3. CPM、CPC、CPA、PFP、CPS、CPL、CPR介绍
  4. HDU 5883 欧拉路径异或值最大 水题
  5. HDU 6278 主席树(区间第k大)+二分
  6. codeforces 892E(离散化+可撤销并查集)
  7. loj6169 相似序列(可持久化线段树)
  8. Extjs.panel.Panel赋值的问题
  9. 2003-07-16T01:24:32Z这是什么时间格式
  10. [Tools] Scroll, Zoom, and Highlight code in a mdx-deck slide presentation with Code Surfer &lt;&#127940;/&gt;