| 题目名称 | 2566. [51nod 1129] 字符串最大值 |
|---|---|
| 输入输出 | string_maxval.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 sxysxy
于2016-11-25加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：90， 提交：175， 通过率：51.43% | ||||
 Hyoi_0Koto |
100 | 0.002 s | 1.33 MiB | C++ |
 Shirry |
100 | 0.008 s | 2.22 MiB | C++ |
 瑆の時間~無盡輪迴·林蔭 |
100 | 0.010 s | 4.45 MiB | C++ |
 HZOI_蒟蒻一只 |
100 | 0.015 s | 1.78 MiB | C++ |
 Hallmeow |
100 | 0.019 s | 1.80 MiB | C++ |
 jhs |
100 | 0.024 s | 2.22 MiB | C++ |
 yrtiop |
100 | 0.038 s | 2.64 MiB | C++ |
 pedro6521 |
100 | 0.057 s | 8.89 MiB | C++ |
 WeiSama |
100 | 0.065 s | 8.45 MiB | C++ |
 joel |
100 | 0.072 s | 8.90 MiB | C++ |
| 本题关联比赛 | |||
| 字符串练习 | |||
| 关于 字符串最大值 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
数据有点水阿，后缀数组+启发式合并没有判断后缀 1 是否在集合中就过了。
当时写 KMP 有点不懂，学习了 Fail 树后大概理解了，KMP 做法的本质其实是 Fail 树上修改一条链的值。 | ||||
|
SAM的挣扎，为什么开大数组会显示RE
| ||||
|
后缀自动机乱搞
| ||||
|
感觉对这道题理解更深了
ps：虽然我写的解释很乱可能只有我自己能看懂 | ||||
|
我个辣鸡还看了看题解。。没想到递推。。脑子里直接就蹦出来了暴力。。
| ||||
|
啊啊啊啊啊啊必须要用三目运算符啊啊啊啊啊啊啊
 attack
2017-05-05 21:15
6楼
| ||||
|
暴力在51nod T了6个点，在这里只T一个点，只是n比较大但是数据太随机的话，稍微跳几次fail就结束了，根本达不到$O(n^2)$，顶多是$O(n)$加点常数。
 kito
2017-03-14 08:11
5楼
| ||||
|
对于后缀自动机突然就明朗了。。
欢迎提问，不兹瓷回答 | ||||
|
卡...卡过.....
 YGOI_真神名曰驴蛋蛋
2017-03-01 20:48
3楼
| ||||
Hale
AAAAAAAAAA
CSU_Turkey
sxysxy2566. [51nod 1129] 字符串最大值
★★★ 输入文件：string_maxval.in
输出文件：string_maxval.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
一个字符串的前缀是指包含该字符第一个字母的连续子串，例如：abcd的所有前缀为a, ab, abc, abcd。
给出一个字符串S，求其所有前缀中，字符长度与出现次数的乘积的最大值。
例如：S = "abababa" 所有的前缀如下:
"a", 长度与出现次数的乘积 1 * 4 = 4,
"ab",长度与出现次数的乘积 2 * 3 = 6,
"aba", 长度与出现次数的乘积 3 * 3 = 9,
"abab", 长度与出现次数的乘积 4 * 2 = 8,
"ababa", 长度与出现次数的乘积 5 * 2 = 10,
"ababab", 长度与出现次数的乘积 6 * 1 = 6,
"abababa", 长度与出现次数的乘积 7 * 1 = 7. 其中"ababa"出现了2次，二者的乘积为10，是所有前缀中最大的
【输入格式】
输入字符串T, (1 <= L <= 1000000， L为T的长度)，T中的所有字符均为小写英文字母。 (注意:原题是L <= 10W，这里加强一下!)
【输出格式】
输出所有前缀中字符长度与出现次数的乘积的最大值。
【样例输入】
abababa
【样例输出】
10
【提示】
【来源】