簡單版AC自動機

簡單版\(AC\)自動機

學之前聽別人說起一直以為很難，今天學了簡單版的\(AC\)自動機，感覺海星，只要理解了\(KMP\)一切都好說。

前置知識：\(KMP\)（有鏈接）

前置知識：\(Trie\)樹

字典樹（\(Trie\)樹）比較簡單，就是把許多個單詞通過樹連接起來。每個點記錄一下兒子個數以及是否是單詞結尾即可。每次加入一個單詞時，從第一個字母開始搜索，如果當前字母存在，就從該字母的兒子里找下一個字母，否則就新建一個節點，直到把這個單詞全部加入進去，然後在最後的字元上標記一下表示以這個字母結尾的單詞多了一個。

那麼\(AC\)自動機實際上就是將兩者合併了起來，在字典樹上進行\(KMP\)。

先說一下\(AC\)自動機是乾什麼的。一個常見的例子就是給出n個單詞，再給出一段包含m個字元的文章，讓你找出有多少個單詞在文章里出現過。要搞懂AC自動機，先得有模式樹（字典樹）\(Trie\)和\(KMP\)模式匹配演算法的基礎知識。\(KMP\)演算法是單模式串的字元匹配演算法，\(AC\)自動機是多模式串的字元匹配演算法。

說白了就是給你一堆字元串，然後再給你一個字元串，問最後這個字元串中出現了多少個前面給出的字元串。

首先我們要有一個字典樹。對於給出的那一堆字元串，我們要一個一個加到樹里。代碼如下：

struct AC{//字典樹
    int end,vis[26],fail;//vis表示兒子的編號
}AC[1000006];
int cnt;
void Build(string s){//要加入的單詞
    int l=s.length(),now=0;//now是當前節點
    for(int i=0;i<l;++i){
        if(AC[now].vis[s[i]-'a']==0) AC[now].vis[s[i]-'a']=++cnt;
        //如果這個字母沒有，就新建一個
        now=AC[now].vis[s[i]-'a'];//如果有或者已經建好，就往下跳
    }
    AC[now].end++;//在最後一個字母處標記有幾個單詞以它結尾
}

有了字典樹，考慮怎樣在樹上進行\(KMP\)

在\(KMP\)裡面的\(next\)指針在這裡改成\(fail\)，其實都一樣。

每個節點\(t\)有\(fail\)指針，其所指向的節點和\(t\)節點的字元是一樣的。因為如果\(t\)匹配成功，而\(t\)的兒子匹配失敗，那麼需要從\(t\)的\(fail\)指針的兒子節點開始匹配。

\(fail\)指針用\(BFS\)來求。

首先，根節點的\(fail\)指針顯然指向他自己，即\(0\)。而他的兒子，也就是深度為一的節點的指針也是指向他的。那麼考慮剩下的節點\(t\)。它的父親節點的\(fail\)指針已經知道，那麼這個指針指向的節點假如是\(u\)的話，如果\(u\)有一個和\(t\)一樣的節點，那麼\(t\)的\(fail\)指針就應該指向它，如果沒有，就要從\(father->fail->fail\)里找，直到找到相同的節點或者到根節點。也就是說要順著之前的失配指針走一遍，有點麻煩。

考慮如果當前節點沒有某個字母，那麼我們可以將該節點指向這個字母的指針，指到他的失配指針指向的節點的這個字母上。

if(AC[u].vis[i]==0)
    AC[u].vis[i]=AC[AC[u].fail].vis[i];

這樣就不用沿著失配指針走一遍了。代碼如下：

void Get_fail(){
    queue<int>Q;//隊列，bfs
    for(int i=0;i<26;++i)//處理深度為二的點
        if(AC[0].vis[i]) AC[AC[0].vis[i]].fail=0,Q.push(AC[0].vis[i]);
    while(!Q.empty()){
        int u=Q.front();
        for(int i=0;i<26;++i)
            if(AC[u].vis[i]) AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i],Q.push(AC[u].vis[i]);
            //如果有這個點，就直接更新指針並壓入隊列
            else AC[u].vis[i]=AC[AC[u].fail].vis[i];//沒有就按上述方法處理
        Q.pop();
    }
}

最後就是統計了。

對於每個字母，如果他是幾個單詞的結尾，那麼久加上他的以及他的所有失配指針的答案，因為他可以，他的失配指針同樣可以。

代碼：

int AC_query(string s){
    int l=s.length(),now=0,ans=0;
    for(int i=0;i<l;++i){
        now=AC[now].vis[s[i]-'a'];
        for(int t=now;t&&AC[t].end!=-1;t=AC[t].fail)//沿著失配指針跳
            ans+=AC[t].end,AC[t].end=-1;//統計答案，標記-1為了防止重覆統計
    }
    return ans;
}

\(Code\)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
struct AC{
    int end,vis[26],fail;
}AC[1000006];
int cnt;
void Build(string s){
    int l=s.length(),now=0;
    for(int i=0;i<l;++i){
        if(AC[now].vis[s[i]-'a']==0) AC[now].vis[s[i]-'a']=++cnt;
        now=AC[now].vis[s[i]-'a'];
    }
    AC[now].end++;
}
void Get_fail(){
    queue<int>Q;
    for(int i=0;i<26;++i)
        if(AC[0].vis[i]) AC[AC[0].vis[i]].fail=0,Q.push(AC[0].vis[i]);
    while(!Q.empty()){
        int u=Q.front();
        for(int i=0;i<26;++i)
            if(AC[u].vis[i]) AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i],Q.push(AC[u].vis[i]);
            else AC[u].vis[i]=AC[AC[u].fail].vis[i];
        Q.pop();
    }
}
int AC_query(string s){
    int l=s.length(),now=0,ans=0;
    for(int i=0;i<l;++i){
        now=AC[now].vis[s[i]-'a'];
        for(int t=now;t&&AC[t].end!=-1;t=AC[t].fail)
            ans+=AC[t].end,AC[t].end=-1;
    }
    return ans;
}
int main(){
    int n;
    string s;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>s,Build(s);
    AC[0].fail=0;
    Get_fail();
    cin>>s;
    cout<<AC_query(s);
    return 0;
}