學習筆記：AC自動機

話說AC自動機有什么用......我想要自動AC機

AC自動機簡介：?

首先簡要介紹一下AC自動機：Aho-Corasick automation，該算法在1975年產生于貝爾實驗室，是著名的多模匹配算法之一。一個常見的例子就是給出n個單詞，再給出一段包含m個字符的文 章，讓你找出有多少個單詞在文章里出現過。要搞懂AC自動機，先得有字典樹Trie和KMP模式匹配算法的基礎知識。KMP算法是單模式串的字符匹配算 法，AC自動機是多模式串的字符匹配算法。

AC自動機的構造：

1.構造一棵Trie，作為AC自動機的搜索數據結構。

2.構造fail指針，使當前字符失配時跳轉到具有最長公共前后綴的字符繼續匹配。如 同 KMP算法一樣， AC自動機在匹配時如果當前字符匹配失敗，那么利用fail指針進行跳轉。由此可知如果跳轉，跳轉后的串的前綴，必為跳轉前的模式串的后綴并且跳轉的新位 置的深度（匹配字符個數）一定小于跳之前的節點。所以我們可以利用 bfs在 Trie上面進行 fail指針的求解。

3.掃描主串進行匹配。

AC自動機詳講：

我們給出5個單詞，say，she，shr，he，her。給定字符串為yasherhs。問多少個單詞在字符串中出現過。

一、Trie

首先我們需要建立一棵Trie。但是這棵Trie不是普通的Trie，而是帶有一些特殊的性質。

首先會有3個重要的指針，分別為p, p->fail, temp。

1.指針p，指向當前匹配的字符。若p指向root，表示當前匹配的字符序列為空。（root是Trie入口，沒有實際含義）。

2.指針p->fail，p的失敗指針，指向與字符p相同的結點，若沒有，則指向root。

3.指針temp，測試指針（自己命名的，容易理解！~），在建立fail指針時有尋找與p字符匹配的結點的作用，在掃描時作用最大，也最不好理解。

對于Trie樹中的一個節點，對應一個序列s[1...m]。此時，p指向字符s[m]。若在下一個字符處失配，即p->next[s[m+1]] == NULL，則由失配指針跳到另一個節點(p->fail)處，該節點對應的序列為s[i...m]。若繼續失配，則序列依次跳轉直到序列為空或出現 匹配。在此過程中，p的值一直在變化，但是p對應節點的字符沒有發生變化。在此過程中，我們觀察可知，最終求得得序列s則為最長公共后綴。另外，由于這個 序列是從root開始到某一節點，則說明這個序列有可能是某些序列的前綴。

再次討論p指針轉移的意義。如果p指針在某一字符s[m+1]處失配(即p->next[s[m+1]] == NULL)，則說明沒有單詞s[1...m+1]存在。此時，如果p的失配指針指向root，則說明當前序列的任意后綴不會是某個單詞的前綴。如果p的失 配指針不指向root，則說明序列s[i...m]是某一單詞的前綴，于是跳轉到p的失配指針，以s[i...m]為前綴繼續匹配s[m+1]。

對于已經得到的序列s[1...m]，由于s[i...m]可能是某單詞的后綴，s[1...j]可能是某單詞的前綴，所以s[1...m]中可能會出現 單詞。此時，p指向已匹配的字符，不能動。于是，令temp = p，然后依次測試s[1...m], s[i...m]是否是單詞。

構造的Trie為：

二、構造失敗指針

用BFS來構造失敗指針，與KMP算法相似的思想。

首先，root入隊，第1次循環時處理與root相連的字符，也就是各個單詞的第一個字符h和s，因為第一個字符不匹配需要重新匹配，所以第一個字符都指 向root（root是Trie入口，沒有實際含義）失敗指針的指向對應下圖中的(1)，(2)兩條虛線；第2次進入循環后，從隊列中先彈出h，接下來p 指向h節點的fail指針指向的節點，也就是root；p=p->fail也就是p=NULL說明匹配序列為空，則把節點e的fail指針指向 root表示沒有匹配序列，對應圖-2中的(3)，然后節點e進入隊列；第3次循環時，彈出的第一個節點a的操作與上一步操作的節點e相同，把a的 fail指針指向root，對應圖-2中的(4)，并入隊；第4次進入循環時，彈出節點h(圖中左邊那個)，這時操作略有不同。由于 p->next[i]!=NULL(root有h這個兒子節點，圖中右邊那個)，這樣便把左邊那個h節點的失敗指針指向右邊那個root的兒子節點 h，對應圖-2中的(5)，然后h入隊。以此類推：在循環結束后，所有的失敗指針就是圖-2中的這種形式。

三、掃描

構造好Trie和失敗指針后，我們就可以對主串進行掃描了。這個過程和KMP算法很類似，但是也有一定的區別，主要是因為AC自動機處理的是多串模式，需要防止遺漏某個單詞，所以引入temp指針。

匹配過程分兩種情況：(1)當前字符匹配，表示從當前節點沿著樹邊有一條路徑可以到達目標字符，此時只需沿該路徑走向下一個節點繼續匹配即可，目標 字符串指針移向下個字符繼續匹配；(2)當前字符不匹配，則去當前節點失敗指針所指向的字符繼續匹配，匹配過程隨著指針指向root結束。重復這2個過程 中的任意一個，直到模式串走到結尾為止。

?對照上圖，看一下模式匹配這個詳細的流程，其中模式串為yasherhs。對于i=0,1。Trie中沒有對應的路徑，故不做任何操 作；i=2,3,4時，指針p走到左下節點e。因為節點e的count信息為1，所以cnt+1，并且講節點e的count值設置為-1，表示改單詞已經 出現過了，防止重復計數，最后temp指向e節點的失敗指針所指向的節點繼續查找，以此類推，最后temp指向root，退出while循環，這個過程中 count增加了2。表示找到了2個單詞she和he。當i=5時，程序進入第5行，p指向其失敗指針的節點，也就是右邊那個e節點，隨后在第6行指向r 節點，r節點的count值為1，從而count+1，循環直到temp指向root為止。最后i=6,7時，找不到任何匹配，匹配過程結束。

到此，AC自動機入門知識就講完了。HDU 2222入門題必須果斷A掉。bzoj3172也要A。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<iomanip>
#include<cassert>
#include<climits>
#include<vector>
#include<list>
#define maxn 1000001
#define F(i,j,k) for(int i=j;i<=k;i++)
#define M(a,b) memset(a,b,sizeof(a))
#define FF(i,j,k) for(int i=j;i>=k;i--)
#define inf 0x7fffffff
#define maxm 2016
#define mod 1000000007
//#define LOCAL
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int pos[maxn];
struct AC_automation
{
    int cnt;
    int next[maxn][26],sum[maxn],fail[maxn],q[maxn];
    char ch[maxn];
    AC_automation()
    {
        cnt=1;
        F(i,0,25) next[0][i]=1;
    }
    void insert(int &pos)
    {
        int now=1;
        cin>>ch;
        int len=strlen(ch)-1;
        F(i,0,len){
            if(!next[now][ch[i]-'a']) next[now][ch[i]-'a']=++cnt;
            now=next[now][ch[i]-'a'];
            sum[now]++;
        }
        pos=now;
    }
    void build_fail()
    {
        int head=0,tail=1;
        q[0]=1;
        fail[1]=0;
        while(head<tail)
        {
            int now=q[head];
            head++;
            F(i,0,25){
                int v=next[now][i];
                if(!v) continue;
                int k=fail[now];
                while(!next[k][i]) k=fail[k];
                fail[v]=next[k][i];
                q[tail++]=v;
            }
        }
        FF(i,tail-1,0){
            sum[fail[q[i]]]+=sum[q[i]];
        }
    }
}ac;
long long n,m;
int main()
{
    std::ios::sync_with_stdio(false);//cout<<setiosflags(ios::fixed)<<setprecision(1)<<y;
    #ifdef LOCAL
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    #endif
    cin>>n;
    F(i,1,n){
        ac.insert(pos[i]);
    }
    ac.build_fail();
    F(i,1,n){
        cout<<ac.sum[pos[i]]<<endl;
    }
    return 0;
}

?