| 题目名称 | 2011. [USACO Dec10]恐吓信 |
|---|---|
| 输入输出 | thre_letter.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 11 |
| 题目来源 |
 cstdio
于2015-07-03加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：21， 提交：43， 通过率：48.84% | ||||
 AAAAAAAAAA |
100 | 0.000 s | 0.00 MiB | C++ |
 hyghb |
100 | 0.023 s | 8.97 MiB | C++ |
 Hzoi_moyi |
100 | 0.024 s | 8.87 MiB | C++ |
 assassain |
100 | 0.033 s | 11.23 MiB | C++ |
 AntiLeaf |
100 | 0.034 s | 10.98 MiB | C++ |
 TenderRun |
100 | 0.035 s | 11.00 MiB | C++ |
 mikumikumi |
100 | 0.035 s | 11.09 MiB | C++ |
 FoolMike |
100 | 0.036 s | 10.97 MiB | C++ |
 ZXCVBNM_1 |
100 | 0.037 s | 11.23 MiB | C++ |
 stdafx.h |
100 | 0.040 s | 11.74 MiB | C++ |
| 关于 恐吓信 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
复杂度不正确的sa被卡掉了。
 CSU_Turkey
2018-02-21 11:47
6楼
| ||||
|
SAM神速
AAAAAAAAAA
2017-07-03 22:25
5楼
| ||||
|
只有我自己用SA吗？
| ||||
|
注意SAM要开两倍空间，不然死得惨……
这里每次贪心地匹配最长的一段，失配后直接回rt即可，最后答案要加1 | ||||
|
| ||||
|
我用的后缀自动机……万古犇@Chenyao 用的后缀数组……
| ||||
_Itachi
cstdio【题目描述】
$FJ$刚刚和邻居发生了一场可怕的争吵，他咽不下这口气，决定佚名发给他的邻居一封脏话连篇的信。他有无限张完全相同的已经打印好的信件，都包含 $N$个字母$(1 <= N <= 50,000)$。他想剪出其中一些并且粘帖成一个很长的字母串。
$FJ$太懒了，他想用最少的次数裁剪信件。他有一把举世无双的剪刀，他可以从一封信中只剪一刀剪出连续一段。同样，剪一刀可以得到整个完整的字符串。
他想知道他最少需要剪多少刀从而获得这封$M（1<=M<=50,000）$个字母的长信？
保证这总是可能的。
考虑下面38个字母的信：
THEQUICKBROWNFOXDO
GJUMPSOVERTHELAZYDOG
以及FJ想要获得的9个字母的信：
FOXDOG DOG
以上是为了读入方便，实际上这两封信就是：
THEQUICKBROWNFOXDOGJUMPSOVERTHELAZYDOG
FOXDOGDOG
由于FOXDOG已经存在了，$FJ$可以剪一刀得到FOXDOG。还剩下一个DOG，$FJ$可以选择其中任何一个DOG剪下来。
因此，他一共要剪2刀。
【输入格式】
第1行： 两个空格分隔的整数： $N, M$
第2..?行： 一些行包含$N$个字母，$FJ$原来拥有的信，每行不会超过80个字母。
第?...?行： 一些行包含$M$个字母，$FJ$想要写的信，每行不会超过80个字母。
【输出格式】
第1行： $FJ$获得他想要写的信所需要切的最少次数。
【样例输入】
38 9
THEQUICKBROWNFOXDO
GJUMPSOVERTHELAZYDOG
FOXDOG
DOG
【样例输出】
2
【来源】
J.Kuipers, 2002