AC自动机
Aho-Corasick automaton,该算法在1975年产生于贝尔实验室，是著名的多模匹配算法之一。比如，给出一组单词，再给出一组字符串，找出有多少个单词在这个字符串中出现了。当然最简单的方法是逐个去找～:P
预备知识
- KMP
- Trie
AC自动机需要以KMP、Trie字典树为基础来实现。不了解的话可以先看下这个2个。
KMP算法是单模式的字符匹配算法，AC自动机是多模式串的字符匹配算法，可以理解为是KMP加强版😄。
AC自动机的实现过程
我们给出5个单词，say,she,shr,he,her.给出字符串yasherhs.要找出有多少个单词在这个字符串中出现。
- 用这5个单词，构造Trie字典树
- 构造失败指针
- 扫描字符串进行匹配
Trie
首先我们需要建立一棵Trie。这棵树和一般的Trie不一样，多一个fail指针。
那么这里有2个指针。
- p 指向当前匹配的字符。
- p->fail p的失败指针，当p->next[i]为空的时候，可以跳转到p->fail继续匹配,如果没有，则指向root
对于Trie树的一个节点，对应一个序列s[1…m]。即p指向s[m]，那么接下来的下一个字符s[m+1]有2种情况。
1.p->next[s[m+1]] 不为空，那么就继续匹配。
2.p->next[s[m+1]] 如果为空，则跳转到失败指针p=p->fail 然后再重复1或2。如果失败指针为空，那么就匹配结束。
这里有个p指针转移的过程，如果是一般的Trie树匹配，那么在2的情况下p－>next[s[m+1]]==NULL,匹配直接结束了，就说找不到单词s[1…m+1]。
那么这里p指针转移的目的是： 虽然单词s[1…m+1]不存在，也许单词s[i…m+1]存在，所以我们可以让p跳到某个节点，并且这个节点对应的字符串是s[i…m]，然后以s[i…m]为前缀继续匹配s[i…m+1]。这里的s[i…m]是s[1…m]的后缀，i具体是多少这里暂时先不管。
这里用失败指针跳转就有KMP的next数组的味道了。
这里讲了失败指针的作用。下面再说如何构造。
构造失败指针
首先从root开始，root的失败指针设置为空，因为本身这个节点也没有实际意义。
还要有一个队列q，存储待构造失败指针的节点
那么对于root的子节点s,h,第一个字符匹配失败也不需要跳转，因此将失败指针指向root，对应图中虚线(1)(2)。构造完s,h的失败指针，还需要把它们的子节点放入队列，也就是e,a,h.
然后第2次循环，队列弹出e节点，接下来p指向h节点的fail指针指向的节点，也就是root;此时p==root，p->next['e'] == NULL,所以p=p->fail,也就是NULL，因为root->fail == NULL.那么就把e的失败指针指向root,对应图中虚线(3)。再看看另外一个h(图中左边这个)，p指向s节点的fail指针，也就是root;此时p==root，p->next['h'] != NULL,有点不一样了，那么就把左边的h节点的失败指向右边的h节点，对应图中虚线(5).以此类推做完e,a h的失败指针构造，然后要把对应的子节点放入q队列。再做下一次循环，直到q队列为空，失败指针构造结束。
void TrieTree::setFail()
{
//使用队列 利用bfs遍历完所有节点
std::queue<TrieNode*> q;
q.push(root);
while (!q.empty()) {
TrieNode* tmp = q.front();
TrieNode* p = tmp->fail;
q.pop();
for (int i=0; i<CHILDNUM; i++) {
if( !tmp->next[i] ) continue;
//父节点的失败指针 作为子节点的失败指针
p = tmp->fail;
//当p->next[i]为空 继续寻找fail指向的节点
while (p && !p->next[i]) p = p->fail;
tmp->next[i]->fail = p ? p->next[i]:root;
//子节点放入队列 待后续构造
q.push(tmp->next[i]);
}
}
}
匹配
匹配过程分2种情况
1.当前字符匹配，p指针移到下一个字符继续匹配
2.当前字符不匹配，p指针移到失败指针所指向的字符继续匹配，直到指针指向root结束。
重复这2个过程，直到模式串结束。
拿出匹配串yasherhs i=0,1时，Trie没有对应的路径，然后继续往后移i=2,3,4.指针p走到左边的e节点。然后遍历失败节点，从左边的e跳到右边的e，然后再跳到root。整个过程发现有2个单词，就是红色圈圈的，跳转过程中发现有单词，可以记录下来。
然后i=5，此时p指向的还是刚才左下角的e，那么p->next['r']==NULL，那么p=p->fail,p指导右边的e，此时p->next['r']!=NULL,p=p->next['r'],然后就是和刚才一样，遍历失败指针。
void TrieTree::query(std::string& s,std::set<std::string>& ret)
{
TrieNode* p = root;
for (int i=0; i<s.size(); i++) {
//匹配不上 则使用失败指针
while( p && !(*p)[s[i]]) p = p->fail;
//这里的 p不动 下次循环再次从这个节点开始匹配
p = p ? (*p)[s[i]] : root;
//遍历完所有的失败节点，并且记录 所有找到的字符串
for (TrieNode* tmp = p; tmp; tmp = tmp->fail) {
if (tmp->isWord) {
ret.insert(tmp->word);
}
}
}
}