| 题目名称 | 1913. AC自动机 |
|---|---|
| 输入输出 | ACautomata.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 3000 ms (3 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 7 |
| 题目来源 |
 wolf
于2015-03-08加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：196， 提交：673， 通过率：29.12% | ||||
 6434 |
100 | 0.111 s | 99.17 MiB | C++ |
 joel |
100 | 0.116 s | 95.69 MiB | C++ |
 123 |
100 | 0.122 s | 51.81 MiB | C++ |
 荡漾 |
100 | 0.125 s | 27.34 MiB | C++ |
 Go灬Fire |
100 | 0.127 s | 27.37 MiB | C++ |
 Hzoi_Mafia |
100 | 0.127 s | 28.19 MiB | C++ |
 河北交通广播992大师来了 |
100 | 0.128 s | 27.35 MiB | C++ |
 Furyton |
100 | 0.129 s | 84.93 MiB | C++ |
 kZime |
100 | 0.129 s | 100.43 MiB | C++ |
 Hzoi_QTY |
100 | 0.134 s | 28.19 MiB | C++ |
| 本题关联比赛 | |||
| 欢乐水题赛 | |||
| 关于 AC自动机 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
拓扑优化AC自动机水过
| ||||
|
ac自动机模板√
 CSU_Turkey
2017-09-30 21:38
44楼
| ||||
|
最后一个点打表了，很惭愧
| ||||
 하루Kiev
2017-07-09 15:40
42楼
| ||||
|
第一道 trie图 AC自动机留念
顺便%一发ryf | ||||
|
这道题就显示出Trie图相对于AC自动机的优势了，T了一上午的AC自动机，不如Trie图加一个拓扑序上传。
%%% @5060 orz | ||||
|
我只想打个裸题看看板子对不对= =
T是个鬼 | ||||
|
| ||||
|
学弟接
| ||||
|
回复 @Hzoi_Ivan :
我也是，不要想了，前边人的板子大都没有最后一组点……这个貌似必须要建成Trie图  HZOI_蒟蒻一只
2017-06-14 14:25
36楼
| ||||
I've copied your code, thanks a lot~
Hzoi_Ivan
kemoto
ONCE AGAIN【题目描述】
对，这就是裸的AC自动机。
要求：在规定时间内统计出模版字符串在文本中出现的次数。
【输入格式】
第一行：模版字符串的个数N(N<=10)。
第2->N+1行：N个字符串。(每个模版字符串的长度<=50)
第N+2行：一行很长的字符串。长度小于1e8。
【输出格式】
共N行，每行输出一个模版及出现的次数。（之间有一个空格,按照输入顺序输出）
【样例输入】
4 hers her his she shershisher
【样例输出】
hers 1 her 2 his 1 she 2
【提示】
所有字母均为小写
所给模版不会重复
【来源】
数据已加强
原前rk10复杂度不对的做法全部被卡tle（逃
by rapiz 2017/3/11