【概述】

KMP 算法用于解決長文本的單模板匹配問題，字典樹用于解決單個單詞（短文本）多模板匹配問題，而 AC 自動機用于解決的是長文本的多模板匹配問題，其是以 trie 樹的結構為基礎，結合 KMP 的思想建立的。

長文本的多模式匹配就是給出多個模式串 P1,P2,P3...，Pm，求出所有這些模式串在連續文本 T1....n 中的所有可能出現的位置、出現的個數、出現的單詞等等。

例如：給出模式集合：{"nihao","hao","hs","hsr"} 與指定文本："sdmfhsgnshejfgnihaofhsrnihao"，求模式集合在文本中所有可能出現的位置。

其運行原理是通過字典樹來構建字典圖實現自動跳轉，構建失配指針實現多模式匹配。

【預處理】

建立一個 AC 自動機進行查詢前，通常需要兩個步驟：

基礎的 Trie 樹結構：將所有的模式串構成一棵 Trie 樹

KMP 的思想：對 Trie 樹上所有的結點構造失配指針。

1.Trie 樹的構建

AC 自動機中?Trie 樹個構建與單純的 Trie 樹中的 insert 操作一樣，只需要利用 Trie 樹的結構，將模式串存入即可。

int tot=0;//編號 int trie[N][26];//字典樹 int val[N];//字符串結尾標記 void insert(char * s){//插入模式串int root=0;//字典樹上當前匹配到的結點for(int i=0;s[i];i++){int id=s[i]-'a';//子節點編號if(trie[root][id]==0)//若之前沒有從root到id的前綴trie[root][id]=++tot;//插入root=trie[root][id];//順著字典樹往下走}val[root]++; }

2.構造失配指針

1）失配指針

AC 自動機的失配指針與 KMP 的 next 數組，兩者都是在失配的時候用于跳轉的指針，不同的是，KMP 要求的是最長相同前后綴，AC 自動機要求的是相同后綴。

由于 KMP 只對一個模式串做匹配，AC 自動機要對多個模式串做匹配，因此，有可能 fail 指針指向的結點對應著另一個模式串，兩個模式串的前綴不同，也就是說，AC 自動機在對匹配串做逐位匹配時，同一位上可能匹配多個模式串，因此，fail 指針會在字典樹上來回穿梭，而不是像 KMP 的 next 數組在線性結構上跳轉。

2）構造

失配指針（fail）的構造與 KMP 中 next 數組的構造相似，即利用部分已經求出的 fail 指針的結點推導出當前結點的 fail，具體使用 bfs 來實現：

首先考慮字典樹中當前節點 u，u 的父節點是 p，p 通過字符 ch 的邊指向 u，那么假設深度小于 u 的所有節點的 fail 指針都已求得，那么 p 的 fail 指針也可求得.

對于跳轉到 p 的 fail 指針指向的節點 fail[p]，有：

• ??????若結點?fail[p]?通過字符?ch?連接到的子結點?w?存在：
  則讓 u 的 fail 指針指向這個結點 w，相當于在 p 和 fail[p] 后加了一個字符 ch，即：fail[u]=w
• ??????若結點?fail[p]?通過字符?ch?連接到的子結點?w 不存在：
  則繼續找 fail[fail[p]] 所指向的結點，重復上述過程，一直跳轉 fail 指針直到根節點，若到達根節點時也不存在，那么就令 fail[u]=root

按照如上步驟，即完成了 fail 指針的構建。

如下圖，對于字典樹 {i,he,his,she,hers} 構建 fail 指針，黃色結點表示當前節點，綠色節點表示已經 bfs 遍歷完畢的節點，橙色的邊表示完成的 fail 指針，紅色的邊表示當前節點所指向的 fail 指針。

注：2 號結點的指針畫錯了，應為 fail[2]=0

如上圖，以節點 6 為例分析 fail 指針的構建：

• 找到節點 6 的父節點 5，5 的 fail 指針指向 10，而節點 1 沒有字符 s 連出邊
• 跳到 10 的 fail 指針指向的節點 0，發現節點 0 有字符 s 連出的邊，指向節點 7
• 因此 fail[6]=7

3）字典樹與字典圖

由于 fail 指針跳轉的路徑需要跳轉很多次，因此將 fail 指針跳轉的路徑進行壓縮（類似并查集的路徑壓縮），使得本來需要跳很多次的 fail 指針只跳一次。

在進行 bfs 時，若將根節點入隊，則在第一次 bfs 的時，會將根節點的子節點的 fail 指針標記為本身，因此選擇將根節點的子節點入隊，由于 fail 指針初始化為 0，因此并不影響算法的正確性。

根節點的子節點入隊后，每次取出隊首元素 k，由于其 fail 指針已經求得，因此只需要求節點 k 的子節點的 fail 指針，則：

• 當字符 i 對應的子節點存在時，將這個子節點 fail 指針賦給 fail[k] 的字符 i 對應的節點
• 當字符 i 對應的子節點不存在時，將 fail[k] 的子節點直接賦成 k 的子節點

將上面的圖改一下，藍色結點表示 bfs 遍歷到的結點 k，藍色、黑色的邊表示執行完路徑壓縮連出字典樹的邊，可以發現，眾多交錯的黑邊將字典樹轉為了字典圖（圖中省略了連向根節點的邊）。

在構建 fail 指針過程中得到的字典圖，在查詢時也會起到關鍵作用。

如上圖，以節點 5 為例分析遍歷時的情況：

• 如上圖，本來應該跳 2 次才能找到 7 號節點，但是通過 10 號節點的黑色邊直接通過字符 s 就找到了 7 號節點
• 因此，在路徑壓縮后，就能在 O(1) 的時間內對單個節點構造 fail 指針

4）實現

void build(){//構建fail指針域建立字典圖memset(fail,0,sizeof(fail));queue<int>q;for(int i=0;i<26;i++)//將根節點的子節點入隊if(trie[0][i])q.push(trie[0][i]);while(!q.empty()){int k=q.front();//對于隊首節點k，其fail指針已求得，現在要求的是他子節點的fail指針q.pop();for(int i=0;i<26;i++){//遍歷字符集if(trie[k][i]){//若字符i對應的子節點存在fail[trie[k][i]]=trie[fail[k]][i];//將這個子節點fail指針賦給fail[k]的字符i對應的節點q.push(trie[k][i]);}else trie[k][i]=trie[fail[k]][i];//將fail[k]的子節點直接賦成k的子節點}} }

?【多模式匹配】

fail 指針是在匹配串同一個位置失敗時的跳轉指針，因此可以利用 fail 指針在同一個位置上進行多模式匹配，匹配完了，就在字典圖上自動跳轉到下一位置。

以下圖為例，紅色結點表示當前匹配到的結點 root，粉色箭頭表示?root 在字典圖上的跳轉，藍色的邊表示成功匹配的模式串，藍色的結點表示跳 fail 指針時的結點。其中的部分跳轉，利用的就是新構建的字典圖上的邊，它也滿足后綴相同，所以自動跳轉到下一個位置。

int query(char *t){//對文本串進行匹配int res=0;//存儲結果int root=0;//字典樹上當前匹配到的結點for(int i=0;t[i];i++){//對文本串進行遍歷int id=t[i]-'a';//子節點編號root=trie[root][id];//在字典圖中不斷穿梭跳動int j=root;while(j&&val[j]!=-1){//利用fail指針找出所有匹配的模式串res+=val[j];//累加到答案中val[j]=-1;j=fail[j];//fail指針跳轉}}return res; }

【模版】

1.文本串中模版串總個數

int tot=0;//編號 int trie[N][26];//字典樹 int val[N];//字符串結尾標記 int fail[N];//失配指針 void insert(char * s){//插入模式串int root=0;//字典樹上當前匹配到的結點for(int i=0;s[i];i++){int id=s[i]-'a';//子節點編號if(trie[root][id]==0)//若之前沒有從root到id的前綴trie[root][id]=++tot;//插入root=trie[root][id];//順著字典樹往下走}val[root]++; } void build(){//構建fail指針域建立字典圖memset(fail,0,sizeof(fail));queue<int>q;for(int i=0;i<26;i++)//將根節點的子節點入隊if(trie[0][i])q.push(trie[0][i]);while(!q.empty()){int k=q.front();//對于隊首節點k，其fail指針已求得，現在要求的是他子節點的fail指針q.pop();for(int i=0;i<26;i++){//遍歷字符集if(trie[k][i]){//若字符i對應的子節點存在fail[trie[k][i]]=trie[fail[k]][i];//將這個子節點fail指針賦給fail[k]的字符i對應的節點q.push(trie[k][i]);}else trie[k][i]=trie[fail[k]][i];//將fail[k]的子節點直接賦成k的子節點}} } int query(char *t){//對文本串進行匹配int res=0;//存儲結果int root=0;//字典樹上當前匹配到的結點for(int i=0;t[i];i++){//對文本串進行遍歷int id=t[i]-'a';//子節點編號root=trie[root][id];//在字典圖中不斷穿梭跳動int j=root;while(j&&val[j]!=-1){//利用fail指針找出所有匹配的模式串res+=val[j];//累加到答案中val[j]=-1;j=fail[j];//fail指針跳轉}}return res; } char P[N]; char T[N]; int main(){int t;scanf("%d",&t);while(t--){memset(trie,0,sizeof(trie));memset(val,0,sizeof(val));memset(fail,0,sizeof(fail));tot=0;int n;//模式串個數scanf("%d",&n);while(n--){scanf("%s",P);//輸入模式串insert(P);//插入字典樹中}build();//構建失配指針與字典圖scanf("%s",T);//輸入文本串int res=query(T);printf("%d\n",res);}return 0; }

?2.文本串中單個模版串個數

int res[N]; struct AC_Automata{int tire[N][26];//字典樹int val[N];//字符串結尾標記int fail[N];//失配指針int last[N];//last[i]=j表j節點表示的單詞是i節點單詞的后綴，且j節點是單詞節點int tot;//編號void init(){//初始化0號點tot=1;val[0]=0;last[0]=0;fail[0]=0;memset(tire[0],0,sizeof(tire[0]));}void insert(char *s,int v){//構造trie與val數組，v需非0，表示一個單詞節點int len=strlen(s);int root=0;for(int i=0;i<len;i++){int id=s[i]-'a';if(tire[root][id]==0){tire[root][id]=tot;memset(tire[tot],0,sizeof(tire[tot]));val[tot++]=0;}root=tire[root][id];}val[root]=v;}void build(){//構造fail與lastqueue<int> q;for(int i=0;i<26;i++){int root=tire[0][i];if(root!=0){fail[root]=0;last[root]=0;q.push(root);}}while(!q.empty()){//bfs求failint k=q.front();q.pop();for(int i=0;i<26; i++){int u=tire[k][i];if(u==0)continue;q.push(u);int v=fail[k];while(v && tire[v][i]==0)v=fail[v];fail[u]=tire[v][i];last[u]=val[fail[u]]?fail[u]:last[fail[u]];}}}void print(int i){//遞歸打印與結點i后綴相同的前綴節點編號if(val[i]){res[val[i]]++;print(last[i]);}}void query(char *s){//匹配int len=strlen(s);int j=0;for(int i=0;i<len;i++){int id=s[i]-'a';while(j && tire[j][id]==0)j=fail[j];j=tire[j][id];if(val[j])print(j);else if(last[j])print(last[j]);}} }ac; char P[1000][1000]; char T[N]; int main(){int n;while(scanf("%d",&n)!=EOF&&n){memset(res,0,sizeof(res));ac.init();for(int i=1;i<=n;i++){scanf("%s",P[i]);ac.insert(P[i],i);}ac.build();scanf("%s",T);ac.query(T);for(int i=1;i<=n;i++)if(res[i])printf("%s: %d\n",P[i],res[i]);}return 0; }

【例題】

• Keywords Search（HDU-2222）(文本串中模版串總個數)：點擊這里
• 病毒侵襲持續中（HDU-3065）(文本串中單個模版串個數)：點擊這里
• 病毒侵襲（HDU-2896）(每個文本串中單個模版串個數+set)：點擊這里
• Searching the String（ZOJ-3228）(可重復的模版串)：點擊這里

總結

以上是生活随笔為你收集整理的字符串处理 —— AC 自动机的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。