洛谷P3804 【模板】后缀自动机
2024-08-29 05:52:41
题目描述
给定一个只包含小写字母的字符串 SS ,
请你求出 SS 的所有出现次数不为 11 的子串的出现次数乘上该子串长度的最大值。
输入输出格式
输入格式:
一行一个仅包含小写字母的字符串 SS
输出格式:
一个整数,为 所求答案
输入输出样例
说明
对于 10\%10% 的数据, |S|<=1000∣S∣<=1000
对于 100\%100% 的数据, |S|<=10^6∣S∣<=106
看了一天的后缀自动机,也算是入了一下门
感觉后缀自动机就是强行加各种优化压空间压时间
这题就是把后缀自动机建出来,再暴力把parent树建出来
在right集合大小*长度中取最大就好
#include<cstdio>
#include<cstring>
#include<vector>
#define LL long long
using namespace std;
const int MAXN = * 1e6 + ;
char s[MAXN];
int N;
int last = , root = , tot = , fa[MAXN], ch[MAXN][], len[MAXN], siz[MAXN];
void insert(int x) {
int now = ++tot, pre = last; last = now;
//last代表全串的点
len[now] = len[pre] + ; siz[now] = ;
for(; pre && !ch[pre][x]; pre = fa[pre])
ch[pre][x] = now;
if(!pre) fa[now] = root;
else {
int q = ch[pre][x];//q是pre的祖先 pre -> q
//说明pre有一条x转移边 q = pre + x
if(len[q] == len[pre] + ) fa[now] = q;
//说明right集合完全重合,此时pre一定是now的后缀??
else {//right集合不完全重合
int nows = ++tot; len[nows] = len[pre] + ;
memcpy(ch[nows], ch[q], sizeof(ch[q]));
fa[nows] = fa[q]; fa[q] = fa[now] = nows;
for(; pre && ch[pre][x] == q; pre = fa[pre]) ch[pre][x] = nows;
}
}
}
vector<int> v[MAXN];
LL ans = ;
void dfs(int x) {
for(int i = ; i < v[x].size(); i++)
dfs(v[x][i]), siz[x] += siz[v[x][i]];
if(siz[x] > ) ans = max(ans, 1ll * siz[x] * len[x]);
} int main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
scanf("%s", s + );
N = strlen(s + );
for(int i = ; i <= N; i++) insert(s[i] - 'a');
for(int i = ; i <= tot; i++) v[fa[i]].push_back(i);
dfs(root);
printf("%lld", ans);
return ;
}
最新文章
- MyEclipse10修改servlet模版
- SQL Server2008函数大全(完整版)
- 安装vim
- js事件应用
- 深入剖析keil c51 --- 从汇编到c51
- python多线程简单例子
- Linux 默认连接数
- 1.3 SQL循环
- 将NULL值转化为“”
- Java核心技术及面试指南 IO部分的面试题归纳以及答案
- c#两个listbox怎么把内容添加到另外个listbox
- day04 运算符 流程控制 (if while/of)
- quora 的东西就是不一样
- SQL Server - 最佳实践 - 参数嗅探问题 转。
- cgo -rpath指定动态库路径
- 将BAT文件注册为服务的方法
- Code Signal_练习题_palindromeRearranging
- Elastic Search操作入门
- Unity让带有Rigidbody组件的游戏对象停止运动
- Jquery.ScrollLoading图片延迟加载技术
热门文章
- 关于FileFOutputStream应用中的FileNotFoundException问题
- VS2012 无法启动 IIS Express Web
- Stage3--Python控制流程及函数
- 跨平台移动开发_PhoneGap 警告,通知,鸣叫,振动4 种通知类型
- Entity Framework:“无法加载指定的元数据资源
- CAA介绍(转)
- oracle数据库建表设置自增主键
- vue-cli3 项目从搭建优化到docker部署
- CRM product UI里assignment block的显示隐藏逻辑
- C语言 字符串的声明与使用