AC自动机算法总结
AC自动机是一种巧妙的字符串多模匹配算法，其中Fail失配的思想非常值得思考
AC自动机是一种字符串多模匹配算法，它使用了字典树这种数据结构
字典树是一种特殊的…树，它有三个特殊的性质
1）根节点不表示字符，但是其他的节点都表示字符
2）从根节点到某个节点连起来，可以表示一个字符串
3）每个节点表示的所有子节点表示的字符都不相同
Trie树还有一些特性：
1）根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2）从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3）每个节点的所有子节点包含的字符都不相同。
4）如果字符的种数为n，则每个结点的出度为n，这也是空间换时间的体现，浪费了很多的空间。
5）插入查找的复杂度为O(n)，n为字符串长度。
例如这就是一棵友善的字典树
如何创建一棵友善的字典树呢
对于一个单词，从根开始，沿着单词的各个字母所对应的树中的节点分支向下走，要是没有就新建一个节点，直到单词遍历完，将最后的节点打个标记，就行了。
具体的话就是每一层开一个长度26的内存池，存一下。
【理论上也可以用前向星存，想挑战的可以试一下，但是fz同志的前向星现在还没调出来
查询也是相同的原理，按照顺序往下跑就行了
例题
Description
A prefix of a string is a substring starting at the beginning of the given string. The prefixes of “carbon” are: “c”, “ca”, “car”, “carb”, “carbo”, and “carbon”. Note that the empty string is not considered a prefix in this problem, but every non-empty string is considered to be a prefix of itself. In everyday language, we tend to abbreviate words by prefixes. For example, “carbohydrate” is commonly abbreviated by “carb”. In this problem, given a set of words, you will find for each word the shortest prefix that uniquely identifies the word it represents.
In the sample input below, “carbohydrate” can be abbreviated to “carboh”, but it cannot be abbreviated to “carbo” (or anything shorter) because there are other words in the list that begin with “carbo”.
An exact match will override a prefix match. For example, the prefix “car” matches the given word “car” exactly. Therefore, it is understood without ambiguity that “car” is an abbreviation for “car” , not for “carriage” or any of the other words in the list that begins with “car”.
Input
The input contains at least two, but no more than 1000 lines. Each line contains one word consisting of 1 to 20 lower case letters.
Output
The output contains the same number of lines as the input. Each line of the output contains the word from the corresponding line of the input, followed by one blank space, and the shortest prefix that uniquely (without ambiguity) identifies this word.
Sample Input
carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate
Sample Output
carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona
这道题是一道字典树的裸题，大概意思就是给你一堆字符串，把每个字符串可以用的最小前缀表示求出来
我们先用所有字符串求出一个字典树，然后把字符串一个一个地放到里面遍历，直到当前节点表示单词的个数是1就结束
代码
#include <cstdio>
#include <cstring>
using namespace std;
char str[10001][35];
int tot,size,sz;
int tree[300001][26],siz[300001];
void insert(char s[])
{
int k,len=strlen(s+1),now=0;
for (int i=1;i<=len;i++)
{
k=s[i]-'a';
if (!tree[now][k])
tree[now][k]=++sz;
now=tree[now][k];
siz[now]++;
}
}
void ask(char ch[])
{
int now=0,k,len=strlen(ch+1);
for (int i=1;i<=len;i++)
{
if (siz[now]==1) break;
k=ch[i]-'a';
printf("%c",ch[i]);
now=tree[now][k];
}
}
main()
{
while(~scanf("%s",str[++tot]+1))
insert(str[tot]);
for (int i=1;i<=tot;i++)
{
printf("%s ",str[i]+1);
ask(str[i]);
puts("");
}
return 0;
}
哪里会用到它呢
就像这种地方
那些下拉框中的匹配就是它的功劳
什么是AC自动机呢
AC自动机是一种基于Trie树，原理与KMP算法类似的多模匹配算法。
其实是Aho-Corasick自动机，并不是什么自动AC的机器。。
而且它其实就比Trie树多了失配指针。。。
现在我们有一棵友善的Trie树，我们要查找一个单词，直接向下找就行了。
但是假如我们要用多模匹配算法——所谓多模匹配算法，就是类似一本字典，里面有许多单词，然后我们查找在一个文本字符串s中是否有字典中的一个单词w出现。
友善Trie树就会回到朴素匹配算法的缺点上——每次失配或配上，只能从开始比较的那位的下一位开始遍历一次Trie，效率也会很低。
这样我们可以用和kmp类似的思路，对于每一个点，求出一个next失配函数，一旦失配，不必回到根节点，直接继续顺着函数跳，直到整个串匹配完毕。
当我们友善的Trie树上加上了失配函数以后，他就变成了和善的AC自动机
如何求失配函数呢？
失配函数满足p->fail 所代表的字符串是p 所代表的字符串的一个后缀，且最长。
首先，讲一下上面话的含义，因为之前提到，一个串的某个字符匹配失败的时候，就跳到它的失败指针上继续匹配，重复上述操作，直到这个字符匹配成功，所以失败指针一定满足一个性质，它指向的一定是某个串的前缀，并且这个前缀是当前结点所在前缀的后缀，而且一定是最长后缀。仔细理解一下这句话，首先，一定是某个串的前缀，这是显然的，因为trie树本来就是前缀树，它的任意一个结点都是某个字典串的前缀；然后再来看后面一句话，为了让当前字符能够找到匹配，那么当前结点的某个后缀必须要和某个模式串的前缀相匹配，这个性质就和KMP的next数组不谋而合了。
然后，就是来看如何利用BFS求出所有结点的失败指针了。
queue<int>que;
void make_fail()
{
int i;
for (int i=0;i<26;i++)
if (tree[1][i])
que.push(tree[1][i]),fail[tree[1][i]]=root;
while(!que.empty())
{
int now=que.front();que.pop();
for (int i=0;i<26;i++)
if (tree[now][i])
{
int t=fail[now];
while(!tree[t][i]&&t)
t=fail[t];
if (now!=root&&t)
fail[tree[now][i]]=tree[t][i];
else
fail[tree[now][i]]=root;
que.push(tree[now][i]);
}
}
}
首先 root节点的fail定义为空，然后每个节点的fail都取决自己的父节点的fail指针，从父节点的fail出发，直到找到存在这个字符为边的节点（向回递归），将他的孩子赋值给寻找节点。如果找不到就指向根节点，具体参照代码。
通过一个bfs，分层进行。第一层节点的失配显然是根节点。第二层开始，节点的失配函数是他父亲节点的失配中和它相等的那个儿子的位置（有点绕）。其实记住就好了，至于正确性，也许不用深究。但是可以想到，其实跳到失配的时候，前面的字符已经比较完毕，可以从失配继续比较。用while来顺着失配往下推，推到某个儿子相等（且不等于它本身），就把失配函数指过去即可。 ——来自fz
那么该如何查询呢
（例题中是查询字符串中字典里的词出现了几次
for (int i=0;i<len;i++)
{
int k=s[i]-'a';
while(!tree[now][k]&&now)
now=fail[now];
if (!now)
now=root;
else
now=tree[now][k];
int t=now;
while(t!=root)
{
ans+=is_end[t];
is_end[t]=0;
t=fail[t];
}
}
假如我们已经有了和善的AC自动机和fail指针
我们定义一个now指针表示现在跑到哪里了
先从第一位开始
我们用k表示字符串第i为的字符
假如now没有k这个儿子就开始跳fail，直到有k这个儿子或者跳到了根
把now变成那个儿子
这时在now的fail上跳，一路加上fail的结尾标记。
（可以用文末的模拟器跳跳试试）
例题 hdu2222
Problem Description
In the modern time, Search engine came into the life of everybody like Google, Baidu, etc.
Wiskey also wants to bring this feature to his image retrieval system.
Every image have a long description, when users type some keywords to find the image, the system will match the keywords with description of image and show the image which the most keywords be matched.
To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will be match.
Input
First line will contain one integer means how many cases will follow by.
Each case will contain two integers N means the number of keywords and N keywords follow. (N <= 10000)
Each keyword will only contains characters ‘a’-‘z’, and the length will be not longer than 50.
The last line is the description, and the length will be not longer than 1000000.
Output
Print how many keywords are contained in the description.
Sample Input
1
5
she
he
say
shr
her
yasherhs
Sample Output
3
#include <cstdio>
#include <cstring>
#include <queue>
#define N 1000010
using namespace std;
int siz[N],is_end[N],fail[N];
int tree[N][26];
int sz;
int vis[N];
int root=1;
void insert(char s[])
{
int len=strlen(s),k,now=root;
for (int i=0;i<len;i++)
{
k=s[i]-'a';
if (!tree[now][k])
tree[now][k]=++sz;
now=tree[now][k];
}
is_end[now]++;
}
queue<int>que;
void make_fail()
{
int i;
for (int i=0;i<26;i++)
if (tree[1][i])
que.push(tree[1][i]),fail[tree[1][i]]=root;
while(!que.empty())
{
int now=que.front();que.pop();
for (int i=0;i<26;i++)
if (tree[now][i])
{
int t=fail[now];
while(!tree[t][i]&&t)
t=fail[t];
if (now!=root&&t)
fail[tree[now][i]]=tree[t][i];
else
fail[tree[now][i]]=root;
que.push(tree[now][i]);
}
}
}
main()
{
int T;
scanf("%d",&T);
for (int i=1;i<=T;i++)
{
int n,ans=0;
sz=1;
char s[N]={0};
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%s",s),insert(s);
make_fail();
scanf("%s",s);
int now=root;
int len=strlen(s);
for (int i=0;i<len;i++)
{
int k=s[i]-'a';
while(!tree[now][k]&&now)
now=fail[now];
if (!now)
now=root;
else
now=tree[now][k];
int t=now;
while(t!=root)
{
ans+=is_end[t];
is_end[t]=0;
t=fail[t];
}
}
printf("%dn",ans);
for (int i=1;i<=sz;i++)
{
is_end[i]=fail[i]=0;
for (int j=0;j<26;j++) tree[i][j]=0;
}
}
}
附赠AC自动机模拟器
（很好用