AC自动机
ps：学习AC自动机的时候必须先点亮KMP和字典树的技能点。
步骤：
1.将所有模式串建立一个字典树。
2.对字典树建立失配边。
3.用目标串与字典树进行匹配。
写法：
现在通用的AC自动机写法有两类：1.数组。2.指针。（也有把这两种结合到一起的写法）
指针比较直观，但是做有的题时不好操作；数组相对抽象些，但是适用范围广。我用的是数组的写法，借鉴的是kuangbin大神的板子。
例子：
举个例子，有模式串：she he say shr her
目标串：yasherhs
现在我们要用这5个模式串建立字典树，并构建失配边。如下图：
代码：（对AC自动机的解释都在代码注释中）
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <queue> #include <set> #include <stdlib.h> using namespace std; const int maxn = 500010; struct Trie{ //next存放的是字典树，在上图中是实线，next[i][j]中i是父亲节点，j是孩子节点 //fail存放失配边的信息，在上图中是蓝线 //end标记的是每个模式串末尾节点，在上图中用红色表示 int next[maxn][26],fail[maxn],end[maxn]; int root,L;//root是根节点，L是节点编号 //newnode()创建一个新的节点，并将它的所有孩子节点初始化为-1，返回这个新建节点的编号 int newnode(){ for(int i = 0;i < 26;i++) next[L][i] = -1; end[L++] = 0; return L-1; } //初始化，给根节点初始化为0号节点 void init(){ L = 0; root = newnode(); } //建立字典树 void insert(char buf[]){ int len = strlen(buf); int now = root;//从根节点开始建立树 for(int i = 0;i <len;i++){ if(next[now][buf[i]-'a'] == -1)//如果现在这个节点下面没有这个节点，就建立新的节点 next[now][buf[i]-'a'] = newnode(); now = next[now][buf[i]-'a'];//切换到下一个节点 } end[now]++;//标记末尾节点 } //建立失配边，用bfs的方式建立 void build(){ queue<int> Q; fail[root] = root; for(int i = 0;i < 26;i++){ if(next[root][i] == -1) next[root][i] = root; else{ fail[next[root][i]] = root;//如果没有前缀，就指向root就行了 Q.push(next[root][i]); } } while(!Q.empty()){ int now = Q.front(); Q.pop(); for(int i = 0;i < 26;i++){ if(next[now][i] == -1) next[now][i] = next[fail[now]][i]; else{ fail[next[now][i]] = next[fail[now]][i];//失配边指向相同前缀 Q.push(next[now][i]); } } } } //目标串与字典树进行匹配 int query(char buf[]){ int len = strlen(buf); int now = root; int res = 0; for(int i = 0;i < len;i++){ now = next[now][buf[i]-'a']; int temp = now; //找目标串中与模式串相同的串 while(temp != root){ res += end[temp]; end[temp] = 0;//这里置零是防止重复计数 temp = fail[temp]; } } return res;//返回匹配成功的个数 } //debug函数，不做多解释了 void dubug(){ } }; char buf[1000010]; Trie ac; int main() { int t; int n; scanf("%d",&t); while(t--){ scanf("%d",&n); ac.init();//初始化 for(int i = 0;i < n;i++){ scanf("%s",buf); ac.insert(buf); } ac.build(); scanf("%s",buf); printf("%d\n",ac.query(buf)); } return 0; }
