Aho-Corasick AC自动机

http://www.geeksforgeeks.org/aho-corasick-algorithm-pattern-searching/

Part1

先来加深一下对Trie的理解：

structs TrieNode {
    bool flag;
    Trie nxt[26];
};

(root) --b--> (Node) --u--> (Node) --s-->(Node)
针对这个字符串bus，每个Node相当于字符之间的间隙，即.b.u.s.这里面的'.'

AC自动机的failure指针，有点类似于KMP算法的next[]数组。
AC自动机所增加的部分：
在每个TrieNode上增加一个failure指针，用于表示待匹配的pattern中“下一步就要匹配了的character但在这个TrieNode里面没有nxt[char]”这种情况该去哪继续尝试。

Part2 流程以及模版

• 建Trie树，failure指针留空。
• 在Trie树的*root位置 foreach(root->next[i]==NULL): root->next[i]=root; 表示“pattern当前位置”什么都没配上，那么如果字典里没有想要的char，就要跳过“pattern当前位置”，跳到pattern的第一个字母之前。
• 把root的孩子（pattern的第一个字母之后）的failure指向root。此步骤为了在后文计算所有TrieNode的failure，赋个初始值。
• 整一个queue (FIFO)，把root的孩子都进queue。
• bfs遍历queue的每一个点，每次取出一个点p，把所有p的后代p->next[ch]的failure算出来，依据就是，从p的failure里面(甚至p->failure->failure)找，找到一个包含next[ch]的。
  注意每次跳转failure，都将导致prefix变短（从root到TrieNode的距离），因此我们使用bfs而不是dfs，可以保证计算p->next[]的时候，沿failure跳转所到的沿途TrieNode必然经过计算。
  感觉这个AC自动机，展开成树形，比KMP更容易理解。。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

struct Trie {
    //fend: the word's last char.
    //fout: there have Trie->fend=true in 'failure link', along with this link, we could find out it.
    bool fend,fout;
    Trie *nxt[26], *failure;
    Trie() {
        fend=fout=0; failure=0;
        memset(nxt, 0,sizeof(nxt));
    }
}*root;
void addTrie(string word) {
    Trie *p=root;
    for (int i=0; i<word.length(); i++) {
        int idx = word[i]-'a';
        if (!p->nxt[idx])
            p->nxt[idx] = new Trie();
        p=p->nxt[idx];
    }
    p->fend=p->fout=1;
}
void makeFailure() {
    queue<Trie*> que;
    for (int i=0; i<26; i++)
        if (root->nxt[i]) {
            root->nxt[i]->failure = root;
            que.push(root->nxt[i]);
        }else
            root->nxt[i] = root; // it used to skip the word(its first character) doesn't exist in dictionary.
    //because each skip along with 'failure point' will make the pattern word shorter. So it's safe to use BFS.
    while (!que.empty()) {
        Trie *p=que.front(); que.pop();
        // we update all informations of 'p->nxt[all]'.
        for (int i=0; i<26; i++)
            if (p->nxt[i]) {
                Trie *tmp=p->failure;
                while (! tmp->nxt[i] )
                    tmp=tmp->failure;
                p->nxt[i]->failure = tmp->nxt[I];
                //p->nxt[i]->fout means that whether have some string stop at this character or not.
                //cuz there may have some substring,
                //e.g.: "abcd" and "bc", we travel at string("abcd")[2], 
                //but this 'c' is the last char of string in other branch, string("bc")[1].
                p->nxt[i]->fout |= tmp->nxt[i]->fout;
                que.push(p->nxt[i]);
            }
    }
}
void query(string ss) {
    Trie *tr=root;
    for (int i=0; i<ss.length(); i++) {
        //cuz the 'root' have all child 'nxt[]', this 'while' is safe.
        while ( !tr->nxt[ss[i]-'a'] )
            tr = tr->failure;
        tr = tr->nxt[ss[i]-'a'];

        //save to ans.
        Trie *anst=tr;
        while (anst->fout) {
            if (anst->fend) {
                cout<<"Got an answer. Stop at s["<<i<<"]."<<endl;
                //travel from 'anst' upstream, we could find out the whole word until reach 'root';
            }
            anst = anst->failure;
        }
    }
}

int main() {
    root = new Trie();
    int W; cin>>W;
    for(int i=0; i<W; i++) {
        string pattern;
        cin>>pattern;
        addTrie(pattern);
    }
    makeFailure();
    query("stringstringstring");
    return 0;
}