一.前言：
经过昨天对kmp的复习，以及做了一道模板题，于是就产生了对多字符串匹配算法AC自动机的好奇心。今天一早就开始学习ac自动机，下午调试了一个小时便实现了该算法。首先来介绍一下什么是ac自动机，
所谓ac自动机，并不是自动判题的机器，而是一种多模式匹配算法，我们都知道kmp算法是每次只能对一个字符串进行匹配，而一旦有多个字符串kmp算法尽管高效，但是在ac自动机算法面前仍然显得不是那么聪明的样子。所以就学习了ac自动机。写了个模板。
二.算法分析：
多模式匹配要高效，一般要用到某些数据结构。没错，那就是——————树
我们前面看过了美丽的圣诞树，今天就来看看美丽的“Trie”树把>0<!
怎么样？这棵树漂亮吧？哈哈哈，圣诞树上全是礼物，这棵树上全是知识点。哈哈
我们说一下ac自动机需要的知识有1、kmp算法（主要是理解前缀和后缀，以及next数组含义，这里类似于fail指针）2、BFS遍历（也称广度优先搜索）
kmp算法和bfs遍历这里就不详细介绍了，我已经在之前的blog里面分析过bfs和kmp了，所以直接进入ac自动机。
第一个步骤：构建Trie树
首先：思考为什么需要Trie树呢？（答案是查询更加方便、高效。）
比如说我让你在某个字符串中查找hers、he这两个单词
你是不是要找完第一个单词，在找第二个单词？
完全不需要啊，因为hers不就包括了he吗？
所以我们就想办法，刚好可以用到Trie树啊。
就是顺着树根往叶子找嘛，碰到一个点我们判断他是否是单词结尾不就行了吗？（太聪明了）
那我们分析一下怎么建立Trie树把。
首先我们需要用到结构体,其中，用一个结构体数组指针存储它的孩子节点，用一个fail指针来存储最长前缀的位置，用1个exist变量来表示是否被遍历过
struct node{
int exist;
node *fail;
node *next[26];//26个英文字母嘛
}
接下来我们每输入一个单词我们就从树根开始判断即可，如果有，则顺着树根的孩子继续找下去，添加到对应的叶子即可；如果不存在的话我们就直接申请节点即可
给出Trie树代码实现：
1 void Trie(node *root,char *str)//构建Trie树
2 {
3 node *p = root;
4 int len = strlen(str);
5 int id,i = 0;
6 for(int i = 0;i < len;i++){
7 id = str[i] - 'a';
8 if(p->next[id] == NULL)
9 p->next[id] = new node();
10 p = p->next[id];
11 }
12 p->exist = 1;//是否为单词的结尾
13 }
第二个步骤：构建fail指针
首先我们先知道fail指针的含义究竟是什么？
fail指针就是这个字符串的后缀在这个树中的最大相似度
比如说我有三个单词：sa,sh,he
Trie树为：
首先root进入队列找到了s、h两个孩子，然后root出队，root没有字符，故他的fail指针肯定为NULL
因为s、h只有一个字符，故只能把fail指针指向root
s、h fail指针为：
接下来a、h进队，s出队，fail指针为
a通过父亲节点的fail指针还是没有找到一个点
但是h通过父亲的fail指针找到了另一个分支的h，而这个h确实就是sh的最长后缀
接下来e入队，h出队
e节点的fail指针通过h的fail指针还是没有找到他的最长后缀，故指向了root
至此遍历完成，fail指针已经完成！
代码如下：
1 void Sfail(node *root)//使用广度搜索创建Trie数
2 {
3 queue <node*> ans;
4 ans.push(root);
5 while(!ans.empty()){
6 node *v = ans.front();
7 ans.pop();
8 for(int i = 0;i < 26;i++){//遍历每个父节点的孩子，如果存在则加入队列
9 if(v->next[i] != NULL){
10 ans.push(v->next[i]);//把存在的孩子加入队列
11 if(v == root)//如果是第一层的节点是没有后缀的，故他的fail指针只能是root
12 v->next[i]->fail = root;
13 else {
14 node *t = v->fail;//如果不是第一层的节点，需要在Trie数中找最长的后缀
15 while(t){
16 if(t->next[i] != NULL){//如果已经通过fail指针找到了后缀，那么这个后缀一定是最长后缀，故指向退出循环
17 v->next[i]->fail = t->next[i];
18 break;
19 }
20 t = t->fail;//如果还没有找到，则通过父亲节点的fail指针继续去寻找
21 }
22 if(t == NULL)//如果通过父亲节点的fail指针依旧没有找到，则无最长后缀，故指向root
23 v->next[i]->fail = root;
24 }
25 }
26 }
27 }
28 }
第三个步骤：匹配字符串
这一步已经非常简单了，只需要按着fail指针匹配就可以了。什么意思呢？就是说如果这个单词在这个字符不匹配了，那么你通过fail指针开始查找是否有相同后缀的从那里匹配就可以了。然后碰到exist为1的话加1就行了。
代码实现：
1 void Query(node *root,char *str)
2 {
3 node *p = root;
4 cout << str << endl;
5 int len = strlen(str);
6 for(int i = 0;i < len;i++){
7 int id = str[i] - 'a';
8 while(p != root && p->next[id] == NULL)//寻找
9 p = p->fail;
10 p = p->next[id];
11 if(p == NULL)
12 p = root;
13 node *t = p;
14 while(t != root){//为什么要循环跑呢，因为可能会出现believe eve这样的单词，防止遗漏，所以需要通过fail指针寻找
15 if(t->exist >= 0){//防止重复加上某个单词
16 cnt += t->exist;
17 t->exist;
18 }
19 else //如果没找到或者说是，找到了但是已经被使用过一次了，就退出循环
20 break;
21 t = t->fail;
22 }
23 }
24 }
三、完整的AC自动机代码：
1 #include "bits/stdc++.h"
2 using namespace std;
3 struct node{
4 node *fail = NULL;//失配指针
5 int exist = 0;//表示是否为一个完整的单词
6 node *next[26] = {NULL};//表示每个节点下的孩子
7 };
8 int cnt;
9 char word[110],s1[10000];
10 void Trie(node *root,char *str)//构建Trie树
11 {
12 node *p = root;
13 int len = strlen(str);
14 int id,i = 0;
15 for(int i = 0;i < len;i++){
16 id = str[i] - 'a';
17 if(p->next[id] == NULL)
18 p->next[id] = new node();
19 p = p->next[id];
20 }
21 p->exist = 1;//是否为单词的结尾
22 }
23 void Sfail(node *root)//使用广度搜索创建Trie数
24 {
25 queue <node*> ans;
26 ans.push(root);
27 while(!ans.empty()){
28 node *v = ans.front();
29 ans.pop();
30 for(int i = 0;i < 26;i++){//遍历每个父节点的孩子，如果存在则加入队列
31 if(v->next[i] != NULL){
32 ans.push(v->next[i]);//把存在的孩子加入队列
33 if(v == root)//如果是第一层的节点是没有后缀的，故他的fail指针只能是root
34 v->next[i]->fail = root;
35 else {
36 node *t = v->fail;//如果不是第一层的节点，需要在Trie数中找最长的后缀
37 while(t){
38 if(t->next[i] != NULL){//如果已经通过fail指针找到了后缀，那么这个后缀一定是最长后缀，故指向退出循环
39 v->next[i]->fail = t->next[i];
40 break;
41 }
42 t = t->fail;//如果还没有找到，则通过父亲节点的fail指针继续去寻找
43 }
44 if(t == NULL)//如果通过父亲节点的fail指针依旧没有找到，则无最长后缀，故指向root
45 v->next[i]->fail = root;
46 }
47 }
48 }
49 }
50 }
51 void Query(node *root,char *str)
52 {
53 node *p = root;
54 cout << str << endl;
55 int len = strlen(str);
56 for(int i = 0;i < len;i++){
57 int id = str[i] - 'a';
58 while(p != root && p->next[id] == NULL)//寻找
59 p = p->fail;
60 p = p->next[id];
61 if(p == NULL)
62 p = root;
63 node *t = p;
64 while(t != root){//为什么要循环跑呢，因为可能会出现believe eve这样的单词，防止遗漏，所以需要通过fail指针寻找
65 if(t->exist >= 0){//防止重复加上某个单词
66 cnt += t->exist;
67 t->exist;
68 }
69 else //如果没找到或者说是，找到了但是已经被使用过一次了，就退出循环
70 break;
71 t = t->fail;
72 }
73 }
74 }
75 int main()
76 {
77 int n;
78 node root;
79 cin >> n;
80 while(n--){
81 getchar();
82 cin >> word;
83 Trie(&root,word);
84 }
85 Sfail(&root);
86 getchar();
87 cin >> s1;
88 Query(&root,s1);
89 cout << cnt << endl;
90 }
四、总结
今天学习了AC自动机，一方面提高了我的编码能力，另一方面也提高了我的查错能力。加油！