题目描述

给定一个只包含小写字母的字符串 SS ,

请你求出 SS 的所有出现次数不为 11 的子串的出现次数乘上该子串长度的最大值。

输入输出格式

输入格式:

一行一个仅包含小写字母的字符串 SS

输出格式:

一个整数,为 所求答案

输入输出样例

输入样例#1: 复制

abab
输出样例#1: 复制

4

说明

对于 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 ;
}

最新文章

  1. MyEclipse10修改servlet模版
  2. SQL Server2008函数大全(完整版)
  3. 安装vim
  4. js事件应用
  5. 深入剖析keil c51 --- 从汇编到c51
  6. python多线程简单例子
  7. Linux 默认连接数
  8. 1.3 SQL循环
  9. 将NULL值转化为“”
  10. Java核心技术及面试指南 IO部分的面试题归纳以及答案
  11. c#两个listbox怎么把内容添加到另外个listbox
  12. day04 运算符 流程控制 (if while/of)
  13. quora 的东西就是不一样
  14. SQL Server - 最佳实践 - 参数嗅探问题 转。
  15. cgo -rpath指定动态库路径
  16. 将BAT文件注册为服务的方法
  17. Code Signal_练习题_palindromeRearranging
  18. Elastic Search操作入门
  19. Unity让带有Rigidbody组件的游戏对象停止运动
  20. Jquery.ScrollLoading图片延迟加载技术

热门文章

  1. 关于FileFOutputStream应用中的FileNotFoundException问题
  2. VS2012 无法启动 IIS Express Web
  3. Stage3--Python控制流程及函数
  4. 跨平台移动开发_PhoneGap 警告,通知,鸣叫,振动4 种通知类型
  5. Entity Framework:“无法加载指定的元数据资源
  6. CAA介绍(转)
  7. oracle数据库建表设置自增主键
  8. vue-cli3 项目从搭建优化到docker部署
  9. CRM product UI里assignment block的显示隐藏逻辑
  10. C语言 字符串的声明与使用