题目背景
通过套取数据而直接 "打表" 过题者, 是作弊行为, 发现即棕名.
这是一道简单的 AC 自动机模板题.
用于检测正确性以及算法常数.
为了防止卡 OJ, 在保证正确的基础上只有两组数据, 请不要恶意提交.
管理员提示: 本题数据内有重复的单词, 且重复单词应该计算多次, 请各位注意
题目描述
给定 n 个模式串和 1 个文本串, 求有多少个模式串在文本串里出现过.
输入输出格式
输入格式:
第一行一个 n, 表示模式串个数;
下面 n 行每行一个模式串;
下面一行一个文本串.
输出格式:
一个数表示答案
输入输出样例
输入样例 #1: 复制 2 a aa aa
输出样例 #1: 复制 2
说明
subtask1[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6,n=1;
subtask2[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6;
题解
在通常就没什么人认真听的集训里, qwerta 刚撸完一把 Win7 原装的扫雷, 舒适的抬起头, 正好对上了老师讲 fail 树的眼神.
所以是懂一丢丢手推方法的.
建议大家先构造点小数据手推, 像是什么在 $her,him,he,his,she$ 上匹配 $shehisher$ 之类的.
网上教程也蛮多, 就不画图了.(懒
其实是自己也推不蛮清楚
然后是教材 QAQ yyb 大佬的博客 http://www.cnblogs.com/cjyyb/p/7196308.html
总之, AC 自动机就是在 trie 树上 bfs 一下然后乱搞, 可以理解为 trie 上的 KMP 叭.
自己都不怎么会, 就不讲这个东西了 QAQ
- #include<queue>
- #include<cstdio>
- #include<cstring>
- #include<iostream>
- using namespace std;
- #define R register
- const int MAXL=1e6+3;
- char s[MAXL];
- struct emm{
- int fail;
- int nxt[26];
- int tag;
- }AC[MAXL];//Tree 结构体
- queue<int>q;//get_fail 的时候用的 queue
- int main()
- {
- //freopen("a.in","r",stdin);
- iOS::sync_with_stdio(false);
- cin.tie(false);cout.tie(false);
- int n;
- cin>>n;
- int tot=0;
- //trie
- while(n--)
- {
- cin>>s;
- int len=strlen(s);
- int now=0;//now 表示当前的节点编号
- for(R int i=0;i<len;++i)
- {
- if(!AC[now].nxt[s[i]-'a'])// 如果当前节点没有这个儿子
- AC[now].nxt[s[i]-'a']=++tot;// 就造个儿子
- now=AC[now].nxt[s[i]-'a'];//now 跳到这个儿子上
- }
- AC[now].tag++;//now 最后在的地方是这个模式串的结束点, 标记一下
- }
- //get_fail
- {
- // 首先把跟 0 号节点相连的点处理一下
- for(R int i=0;i<26;++i)
- {
- if(AC[0].nxt[i])// 如果这个儿子存在
- {
- AC[AC[0].nxt[i]].fail=0;// 把 fail 指向 0 号节点 (其实默认就是 0 啊 QAQ
- q.push(AC[0].nxt[i]);// 把这个儿子 push 进去
- }
- }
- while(!q.empty())
- {
- int x=q.front();q.pop();// 取点
- for(R int i=0;i<26;++i)
- {
- if(AC[x].nxt[i])// 如果这个儿子存在
- {
- AC[AC[x].nxt[i]].fail=AC[AC[x].fail].nxt[i];// 敲重点!!!
- // 这个儿子的 fail, 等于这个节点 fail 的儿子 会手推就能懂叭 QAQ
- q.push(AC[x].nxt[i]);//push 进去
- }
- else
- AC[x].nxt[i]=AC[AC[x].fail].nxt[i];// 这里直接把 nxt 指向了 fail 的对应儿子
- }
- }
- }
- //run
- cin>>s;
- long long ans=0;
- int len=strlen(s);
- int now=0;//now 表示当前节点编号
- for(R int i=0;i<len;++i)
- {
- now=AC[now].nxt[s[i]-'a'];// 往下走一层 (因为之前直接把空的 nxt 往 fail 指了, 所以不需要通常的 while 跳 fail
- // 大概就是 Trie 图和 Trie 树的区别了叭
- for(R int t=now;t&&AC[t].tag!=-1;t=AC[t].fail)// 从这个点开始暴力跳 fail, 找匹配
- {
- ans+=AC[t].tag;
- AC[t].tag=-1;// 这是个剪枝
- }
- }
- cout<<ans;
- return 0;// 撒花
- }
然后吐槽一下咕咕的数据, 之前有一大段把 $now$ 和 $i$ 混用了, 结果还过了一个点 (???
来源: http://www.bubuko.com/infodetail-2798473.html