| 题目名称 | 2688. 鱼的感恩 |
|---|---|
| 输入输出 | fool.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 TARDIS
于2017-05-03加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：61， 提交：174， 通过率：35.06% | ||||
 zxj |
100 | 0.230 s | 5.08 MiB | C++ |
 szzy |
100 | 0.261 s | 25.18 MiB | C++ |
 _小妖 |
100 | 0.298 s | 48.00 MiB | C++ |
 呵呵酵母菌 |
100 | 0.325 s | 2.22 MiB | C++ |
 Youngsc |
100 | 0.326 s | 0.40 MiB | C++ |
 梦那边的美好ET |
100 | 0.342 s | 7.92 MiB | C++ |
 Hzoi_moyi |
100 | 0.383 s | 0.89 MiB | C++ |
|
szzy |
100 | 0.385 s | 50.36 MiB | C++ |
 星尘 |
100 | 0.388 s | 10.27 MiB | C++ |
 可以的. |
100 | 0.399 s | 0.86 MiB | C++ |
| 本题关联比赛 | |||
| cmath生日赛 | |||
| 关于 鱼的感恩 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
kmp策略：先o（n）把每个前缀的前缀函数求出来，再o（n）比对每个前缀和其本身的前缀函数，如果相等就能保证至少三处完全相等，如果没有满足条件的前缀，那么答案就是字符串本身的前缀函数的前缀函数（表达的好像不是很标准
| ||||
|
| ||||
|
| ||||
|
| ||||
|
做的我想哭。。
| ||||
|
数组开到100000就行了，超时好像是因为memset……
输出字符用printf("%c",…) 然而我看了下面的来源，跳进了51nod 1286的大坑，折腾了一下午发现扩展kmp我没学过 好像不加回车能过？刚开始没打回车过了5个点后面的T | ||||
|
回复 @Hzoi_Ivan :
KMP不叫暴力，我的才叫…… | ||||
|
暴力水上榜。。
| ||||
|
论做题少的危害
 HZOI_蒟蒻一只
2017-08-07 14:28
7楼
| ||||
|
我头一次这么恨弱数据 = =
  ~玖湫~
2017-08-07 14:09
6楼
| ||||
tat
kZime
Hzoi_QTY
Hzoi_Ivan【题目描述】
从前有一个渔夫抓到了一条特别的鱼，放走了。
渔夫再次抓到了这条鱼，正要再次放走之时，这条鱼吐出了一片迷雾，迷雾散去以后，渔夫不见了。
渔夫睁开眼，发现自己到了一个石碑面前，碑上有一行小写英文字符串S，下面写着：“汝等既有护生之念，应是善良之人，理当授以嘉奖。但是为了证明你的善良，你需要展现你的智慧，以确保吾所见之善良，并非出于汝之愚笨。上面的字符串，你若于其中找到最长的子串，使得这个子串既出现在前缀，又出现在后缀，还出现在字符串的中间，也就是既非前缀又非后缀的位置，则该石碑会将其所藏之物拱手相送。”
渔夫听完以后，可谓一脸懵逼，遂将这个问题分享给你，希望你能够解决。若能解决，渔夫愿意拿出10,000,000,000,000 mod 250 元，作为解决这个问题的报酬。
【输入格式】
第一行是一个数字q，表示这个问题有q组不同问题。
接下来q行每行一个由小写英文字母组成的字符串S，意义见于上文。
【输出格式】
输出共q行，每行一个字符串，表示对于每组问题，所求的字符串，如果不存在长度大于0且满足要求的字符串，就改成输出”---”（不包含引号）
【样例输入】
1 niconiconi
【样例输出】
ni
【提示】
前10%的数据，q<=10
前30%的数据，q<=30
前50%的数据，q<=100
所有数据，q<=200,000
题目保证O(n)算法能过！
【来源】
QBXT春季训练营第二次测试T3 OR 51nod 1286