luogu 3804 【模板】后缀自动机
2024-08-30 17:13:58
学习一波后缀自动机
求字符串$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);
}
最新文章
- PostGIS(解压版)安装
- [LeetCode] Valid Palindrome 验证回文字符串
- 《编写可维护的JavaScript》——JavaScript编码规范(七)
- NET中的类型和装箱/拆箱原理
- 旋转屏幕时,假如自定义的xib大小变了,可能是这个属性没有修改
- 替换NavigationController里面的返回按钮
- Base64笔记
- 第五章 使用 SqlSession
- VirtualBox: How to config higher screen resolution
- 网站开发进阶(三)Windows NAT端口映射
- Linux的文件类型
- 【工利其器】必会工具之(二)Android开发者官网篇
- IT题库-134 | String、StringBuffer和StringBuilder的区别
- PHP 多维数组排序 函数怎么保持数字键不被重新索引
- Complete Binary Search Tree
- python--第二十天总结(Django的一些注意)
- android开发学习——day6
- hdu 2266 dfs
- JSP--JDBC技术
- Druid如何自动根据URL自动识别DriverClass的
热门文章
- [NOIP2001] 提高组 洛谷P1024 一元三次方程求解
- input文本框的value属性在页面中不随输入的数据而变化
- CPM、CPC、CPA、PFP、CPS、CPL、CPR介绍
- HDU 5883 欧拉路径异或值最大 水题
- HDU 6278 主席树(区间第k大)+二分
- codeforces 892E(离散化+可撤销并查集)
- loj6169 相似序列(可持久化线段树)
- Extjs.panel.Panel赋值的问题
- 2003-07-16T01:24:32Z这是什么时间格式
- [Tools] Scroll, Zoom, and Highlight code in a mdx-deck slide presentation with Code Surfer <;&#127940;/>;