當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

Keywords Search HDU - 2222（AC自动机模板）

發布時間：2023/12/4 编程问答 30 豆豆

生活随笔收集整理的這篇文章主要介紹了 Keywords Search HDU - 2222（AC自动机模板）小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

題意：

給定 n個長度不超過 50的由小寫英文字母組成的單詞準備查詢，以及一篇文章，問：文中出現了多少個待查詢的單詞。多組數據。

題目：

In the modern time, Search engine came into the life of everybody like Google, Baidu, etc.
Wiskey also wants to bring this feature to his image retrieval system.
Every image have a long description, when users type some keywords to find the image, the system will match the keywords with description of image and show the image which the most keywords be matched.
To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will be match.
Input
First line will contain one integer means how many cases will follow by.
Each case will contain two integers N means the number of keywords and N keywords follow. (N <= 10000)
Each keyword will only contains characters ‘a’-‘z’, and the length will be not longer than 50.
The last line is the description, and the length will be not longer than 1000000.
Output
Print how many keywords are contained in the description.
Sample Input
1
5
she
he
say
shr
her
yasherhs
Sample Output
3

分析：

此題為AC自動機模板匹配多模式串問題。單模式串匹配用KMP算法，那么多模式串匹配，不可能一個一個字符串建立失配數組，復雜度太高0(m*n),所以對多模式串建成一個trie樹，再建立失配數組，復雜度為o(n $n\sqrt{n}$ )。AC自動機詳細分析見代碼后。

AC代碼：

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int N=5e5+10; int ans,tot,dp[N],ch[N][30],bo[N],que[N]; void makes(char *s)/**將所有模式串構建成一顆tire樹*/ {int u=1,len=strlen(s);for(int i=0; i<len; i++){int c=s[i]-'a';if(!ch[u][c])ch[u][c]=++tot;u=ch[u][c];}bo[u]++;return ; } void bfs()/**通過BFS構建dp(失配)數組*/ {for(int i=0; i<26; ++i)ch[0][i]=1;/**為了方便將0的所有轉移邊都設為根節點1*/que[1]=1,dp[1]=0;/**若在根節點失配，則無法匹配字符*/for(int x=1,y=1; x<=y; x++){int u=que[x];for(int i=0; i<=25; i++){if(!ch[u][i])/**如果不存在u的轉移邊i時，失配，KMP*/ch[u][i]=ch[dp[u]][i];///優化else{que[++y]=ch[u][i];/**若有這個兒子則將其加入隊列中*/dp[ch[u][i]]=ch[dp[u]][i];}}} } void find(char *s) {int u=1,len=strlen(s),c,k;for(int i=0; i<=len; i++){c=s[i]-'a';k=ch[u][c];while(k>1){ans+=bo[k];bo[k]=0;k=dp[k];}u=ch[u][c];}return ; } int main() {int t,n;char s[N<<1];scanf("%d",&t);while(t--){ans=0,tot=1;memset(bo,0,sizeof(bo));memset(ch,0,sizeof(ch));scanf("%d",&n);while(n--){scanf("%s",s);makes(s);}bfs();scanf("%s",s);find(s);printf("%d\n",ans);}return 0; }

AC自動機詳細分解：

ac自動機很神奇，在于這個算法中失配指針的妙處（好比kmp算法中的next數組），說它高深，是因為這個不是一般的算法，而是建立在兩個普通算法的基礎之上，而這兩個算法就是kmp與字典樹。ac自動機其實就是一種多模匹配算法，那么你可能會問什么叫做多模匹配算法。下面是我對多模匹配的理解，與多模與之對于的是單模，單模就是給你一個單詞，然后給你一個字符串，問你這個單詞是否在這個字符串中出現過（匹配），這個問題可以用kmp算法在比較高效的效率上完成這個任務。那么現在我們換個問題，給你很多個單詞，然后給你一段字符串，問你有多少個單詞在這個字符串中出現過，當然我們暴力做，用每一個單詞對字符串做kmp,這樣雖然理論上可行，但是時間復雜度非常之高。

建立tire樹(就是tire樹模板)這個簡單

void makes(char *s)/**將所有模式串構建成一顆tire樹*/ {int u=1,len=strlen(s);for(int i=0; i<len; i++){int c=s[i]-'a';if(!ch[u][c])ch[u][c]=++tot;u=ch[u][c];}bo[u]++;return ; }

建立后此時多模式串為一個字典樹，將存在公共前綴的字符串“合并”，可以用一個數組（每個新點插入++tot）表示樹上所有點。

建一個樹的圖：

建立該字典樹的失配數組(bfs（隊列）+KMP+前綴數組）重點

void bfs()/**通過BFS構建dp(失配)數組*/ {for(int i=0; i<26; ++i)ch[0][i]=1;/**為了方便將0的所有轉移邊都設為根節點1*/que[1]=1,dp[1]=0;/**若在根節點失配，則無法匹配字符*/for(int x=1,y=1; x<=y; x++){int u=que[x];for(int i=0; i<=25; i++){if(!ch[u][i])/**如果不存在u的轉移邊i時，失配，KMP*/ch[u][i]=ch[dp[u]][i];///優化else{que[++y]=ch[u][i];/**若有這個兒子則將其加入隊列中*/dp[ch[u][i]]=ch[dp[u]][i];}}} }

首先建立的是一個tire樹，一個結點上可能連多個節點，所以這里用BFS（用進入隊列的方式，處理每一個點），最后將tire樹建立成一個可與給定串匹配的失配數組
構建失配數組（在代碼中我寫的是dp數組），使當前字符失配時跳轉到另一段（最近匹配的位置）【root開始每一個字符（前綴）都與當前已匹配字符段某一個后綴完全相同且長度最大的位置繼續匹配】如同KMP算法一樣，AC自動機在匹配時如果當前字符串匹配失敗，那么利用失配指針進行跳轉。由此可知如果跳轉，跳轉后的串的前綴必為跳轉前的模式串的后綴，并且跳轉的新位置的深度（匹配字符個數）一定小于跳之前的節點（跳轉后匹配字符數不可能大于跳轉前，否則無法保證跳轉后的序列的前綴與跳轉前的序列的后綴匹配）。
因為是一個字典樹（用ch數組表示，是一個二維數組,ch[u][c]）,由于字典樹c就為當前點++tot，u為上一個點，ch[u][c]就為當前點是否為樹上的第幾個點。 dp[ch[u][i]]（等同于dp[i++] 由tire樹ch[u][c]==++tot(將字典樹上的某一個鏈看做需要匹配的字符串) ） =ch[dp[u]][i]（等同于j++(上次匹配位置的++tot)) ;
顯然我們在構建失配數組的時候都是從當前節點的父節點的失配數組出發，由于Trie樹將所有單詞中相同前綴壓縮在了一起，所以所有失配數組都不可能平級跳轉（到達另一個與自己深度相同的節點），因為如果平級跳轉，很顯然跳轉所到達的那個節點肯定不是當前匹配到的字符串的后綴的一部分，否則那兩個節點會合為一個，所以跳轉只能到達比當前深度小的節點，又是由當前節點（ch[u][c]==++tot ）父節點（u ）開始的跳轉，所以這樣就可以保證從root到所跳轉到位置的那一段字符串長度小于當前匹配到的字符串長度。另一方面，我們可以類比KMP求NEXT數組時求最大匹配數量的思想，那種思想在AC自動機中的體現就是當構建失配數組時不斷地回到之前的跳轉位置，然后判斷跳轉位置的下一個字符是否包含當前字符，如果是就將失配數組與那個跳轉位置連接，如果跳轉位置指向tire樹上的空點就說明當前匹配的字符在當前深度之前沒有出現過，無法與任何跳轉位置匹配，而若是找到了第一個跳轉位置的下一個字符包含當前字符的的跳轉位置，則必然取到了最大的長度，這是因為其余的當前正在匹配的字符必然在第一個跳轉位置的下一個字符包含當前字符的的跳轉位置深度之上，而那樣的跳轉位置就算可以，也不會是最大的（最后一個字符的深度比當前找到的第一個可行的跳轉位置的最后一個字符的深度小，串必然更短一些）。

if(!ch[u][i])/**如果不存在u的轉移邊i時，失配，KMP*/ch[u][i]=ch[dp[u]][i];///優化(即找到后綴完全相同且長度最大的位置)

如圖：

查詢操作（與字符串匹配)

void find(char *s) {int u=1,len=strlen(s),c,k;for(int i=0; i<=len; i++){c=s[i]-'a';k=ch[u][c];while(k>1){ans+=bo[k];bo[k]=0;k=dp[k];}u=ch[u][c];}return ; }

如果節點匹配，就一直進行下去，每次都加每個節點的bo[u]，并初始化為0，但只有代表單詞結尾的字符bo[u]才是1，其他的為0.所以才有

while(k>1){ans+=bo[k];bo[k]=0;k=dp[k];}

例如，在查詢過程中，匹配字符為abcdef,若有一個模式串為bc，那么因為KMP只掃過前綴，就會忽略導致結果錯誤，所以每次讓某匹配點失配，看匹配串的后綴和之前匹配的前綴是否存在一模式串（bo[u]!=0）到空點結束.

該查詢默認一直匹配，因為在構造失配數組時進行了優化,見下代碼