| 题目名称 | 2216. [BZOJ 4503] 你猜是不是KMP |
|---|---|
| 输入输出 | guess.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 3000 ms (3 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 11 |
| 题目来源 |
 TenderRun
于2016-04-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：64， 提交：152， 通过率：42.11% | ||||
 _Itachi |
100 | 0.566 s | 14.79 MiB | C++ |
 ONCE AGAIN |
100 | 0.671 s | 37.29 MiB | C++ |
|
6666 |
100 | 0.950 s | 14.79 MiB | C++ |
|
_Itachi |
100 | 0.973 s | 14.79 MiB | C++ |
 胡嘉兴 |
100 | 1.096 s | 27.01 MiB | C++ |
 Hzoi_Hugh |
100 | 1.302 s | 16.26 MiB | C++ |
|
_Itachi |
100 | 1.357 s | 22.79 MiB | C++ |
 findstr |
100 | 1.369 s | 0.82 MiB | C++ |
 Link |
100 | 1.384 s | 0.82 MiB | C++ |
|
6666 |
100 | 1.459 s | 1.18 MiB | C++ |
| 关于 你猜是不是KMP 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
把FFT次数减少到3次，效果拔群
| ||||
|
| ||||
|
其实应该还可以用linux下头文件regex.h水（正则表达式库，注意，noi的编译选项可编译通过，并且函数名不违反ccf规定）
不过在windows下不方便，学一波bitset奇迹...  sxysxy
2017-03-20 16:52
20楼
| ||||
 Sky_miner
2017-02-14 07:01
19楼
| ||||
|
原来不是在逗我，泥萌居然都写得FFT。。
_Itachi
2017-01-11 15:17
17楼
| ||||
|
bitset出奇迹
| ||||
|
bitset水过啦
%%%扩展KMP | ||||
|
原来你们都看透了呀
| ||||
|
并不会FFT的路过
 Hzoi_
2016-04-09 18:33
13楼
| ||||
AntiLeaf
YGOI_真神名曰驴蛋蛋
FoolMike
阮行止
TenderRun【题目描述】
XX在玩两个串的游戏。首先,他拿出了两个字符串 S 和 T,XX想知道 T
在 S 中出现了几次,分别在哪些位置出现。注意 T 中可能有“?”字符,这个字
符可以匹配任何字符。
【输入格式】
两行两个字符串,分别代表 S 和 T
【输出格式】
第一行一个正整数 k,表示 T 在 S 中出现了几次。
接下来 k 行正整数,
分别代表 T 每次在 S 中出现的开始位置。按照从小到大
的顺序输出,S 下标从 0 开始。
【样例输入】
ababcadaca a?a
【样例输出】
3 0 5 7
【提示】
对于 10%的数据, S 和 T 的长度不超过 100
对于另外 20%的数据,T 中无“?”
对于 100%的数据,S 长度不超过 10^5,T 长度不会超过 S。S 中只包含小写
字母,T 中只包含小写字母和“?”
【来源】
经典题目 BZOJ 4503 两个串
UPD：Mike新增数据一组2018.1.19