【概述】

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

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

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

其運行原理是通過字典樹來構(gòu)建字典圖實現(xiàn)自動跳轉(zhuǎn)，構(gòu)建失配指針實現(xiàn)多模式匹配。

【預(yù)處理】

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

基礎(chǔ)的 Trie 樹結(jié)構(gòu)：將所有的模式串構(gòu)成一棵 Trie 樹

KMP 的思想：對 Trie 樹上所有的結(jié)點構(gòu)造失配指針。

1.Trie 樹的構(gòu)建

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

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

2.構(gòu)造失配指針

1）失配指針

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

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

2）構(gòu)造

失配指針（fail）的構(gòu)造與 KMP 中 next 數(shù)組的構(gòu)造相似，即利用部分已經(jīng)求出的 fail 指針的結(jié)點推導(dǎo)出當前結(jié)點的 fail，具體使用 bfs 來實現(xiàn)：

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

對于跳轉(zhuǎn)到 p 的 fail 指針指向的節(jié)點 fail[p]，有：

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

按照如上步驟，即完成了 fail 指針的構(gòu)建。

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

注：2 號結(jié)點的指針畫錯了，應(yīng)為 fail[2]=0

如上圖，以節(jié)點 6 為例分析 fail 指針的構(gòu)建：

• 找到節(jié)點 6 的父節(jié)點 5，5 的 fail 指針指向 10，而節(jié)點 1 沒有字符 s 連出邊
• 跳到 10 的 fail 指針指向的節(jié)點 0，發(fā)現(xiàn)節(jié)點 0 有字符 s 連出的邊，指向節(jié)點 7
• 因此 fail[6]=7

3）字典樹與字典圖

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

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

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

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

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

在構(gòu)建 fail 指針過程中得到的字典圖，在查詢時也會起到關(guān)鍵作用。

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

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

4）實現(xiàn)

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

?【多模式匹配】

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

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

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

【模版】

1.文本串中模版串總個數(shù)

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

?2.文本串中單個模版串個數(shù)

int res[N]; struct AC_Automata{int tire[N][26];//字典樹int val[N];//字符串結(jié)尾標記int fail[N];//失配指針int last[N];//last[i]=j表j節(jié)點表示的單詞是i節(jié)點單詞的后綴，且j節(jié)點是單詞節(jié)點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){//構(gòu)造trie與val數(shù)組，v需非0，表示一個單詞節(jié)點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(){//構(gòu)造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){//遞歸打印與結(jié)點i后綴相同的前綴節(jié)點編號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）(文本串中模版串總個數(shù))：點擊這里
• 病毒侵襲持續(xù)中（HDU-3065）(文本串中單個模版串個數(shù))：點擊這里
• 病毒侵襲（HDU-2896）(每個文本串中單個模版串個數(shù)+set)：點擊這里
• Searching the String（ZOJ-3228）(可重復(fù)的模版串)：點擊這里

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。