程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 字符串算法之 AC自動機

字符串算法之 AC自動機

編輯:C++入門知識

字符串算法之 AC自動機


最近一直在學習字符串之類的算法,感覺BF算法,雖然很容易理解,但是容易超時,所有就想學習其他的一些字符串算法來提高一下,最近學習了一下AC自動機,雖然感覺有所收獲,但是還是有些朦胧的感覺,在此總結一下,希望大家指教。

一、AC自動機的原理:

Aho-Corasick automaton,該算法在1975年產生於貝爾實驗室,是著名的多模匹配算法之一。一個常見的例子就是給出N個單詞,在給出一段包含m個字符的文章,讓你找出有多少個單詞在這文章中出現過,。要搞懂AC自動機,先的有字典樹和KMP模式匹配算法的基礎知識。

二、AC自動機算法的實現步驟(三步)

AC自動機的存儲數據結構

const int MAXN = 10000000;
struct node
{
int count; //是否為單詞最後一個節點
node *next[26];//Trie每個節點的26個子節點
node *fail; //失敗指針
};
node *q[MAXN]; //隊列,采用bfs 構造失敗指針
char keyword[55];//輸入單詞 模式串
char str[1000010];// 需要查找的 主串
int head,tail;//隊列 頭尾指針

 

1、構造一棵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為:

\

實現代碼:

 

void insert(char *word,node *root)
{
     int index,len;
     node *p = root,*newnode;
     len = strlen(word);
     for(int i=0 ;i < len ; i++ )
     {  
         index=word[i]-'a';
         if(!p->next[index])//該字符節點不存在,加入Trie樹中
         {
           // 初始化 newnode 並 加入 Trie 樹
            newnode=(struct node *)malloc(sizeof(struct node));    
            for(int j=0;j<26;j++)
				 newnode->next[j]=0;
            newnode->count=0;
			newnode->fail=0;
            p->next[index]=newnode;
         }
         p=p->next[index];//指針移動至下一層
     }
     p->count++;  //單詞結尾 節點 count + 1 做標記  
}


 

2、構造失敗指針

 

 

構造失敗指針的過程概括起來就一句話:設這個節點上的字母為x,沿著他父親的失敗指針走,直到走到一個節點,他的兒子中也有字母為x的節點。然後把當前節點的失敗指針指向那個字符也為x的兒子。如果一直走到了root都沒找到,那就把失敗指針指向root。

有兩個規則:

 

  1. root的子節點的失敗指針都指向root。

  2. 節點(字符為x)的失敗指針指向:從X節點的父節點的fail節點回溯直到找到某節點的子節點也是字符x,沒有找到就指向root。

    如下圖

     

    \

    實現代碼:

     

    void build_ac_automation(node *root)
    {
        head=0;
    	tail=1;
        q[head]=root;
        node *temp,*p;
        while(headnext[i])//判斷實際存在的節點 
                 {
                     // root 下的第一層 節點 的 失敗指針都 指向root
                     if(temp==root)
    				 	temp->next[i]->fail=root;
                     else
    				 {
                        //依次回溯 該節點的父節點的失敗指針
                       //直到某節點的next[i]與該節點相同,則
                       //把該節點的失敗指針指向該next[i]節點
                       //若回溯到 root 都沒有找到,則該節點
                       //的失敗指針 指向 root
                      
                        p=temp->fail;//temp 為節點的父指針
                        while(p)
    					{
                           if(p->next[i])
    					   {
    	                       temp->next[i]->fail=p->next[i];
    	                       break;
                           }
                           p=p->fail;
                        }
                        if(!p)temp->next[i]->fail=root;
                     }
                     //每處理一個點,就把它的所有兒子加入隊列,           
                     //直到隊列為空
                     q[tail++]=temp->next[i];
                 }
             }                
         }
    }


     


    3、模式匹配過程

     

     

    從root節點開始,每次根據讀入的字符沿著自動機向下移動。當讀入的字符,在分支中不存在時,遞歸走失敗路徑。如果走失敗路徑走到了root節點, 則跳過該字符,處理下一個字符。因為AC自動機是沿著輸入文本的最長後綴移動的,所以在讀取完所有輸入文本後,最後遞歸走失敗路徑,直到到達根節點, 這樣可以檢測出所有的模式。

    搜索的步驟:

     

    1. 從根節點開始一次搜索;

    2. 取得要查找關鍵詞的第一個字符,並根據該字符選擇對應的子樹並轉到該子樹繼續進行檢索;

    3. 在相應的子樹上,取得要查找關鍵詞的第二個字符,並進一步選擇對應的子樹進行檢索。

    4. 迭代過程……

    5. 在某個節點處,關鍵詞的所有字符已被取出,則讀取附在該節點上的信息,即完成查找。

      匹配模式串中出現的單詞。當我們的模式串在Trie上進行匹配時,如果與當前節點的關鍵字不能繼續匹配的時候,

      就應該去當前節點的失敗指針所指向的節點繼續進行匹配。

      匹配過程出現兩種情況:

       

      1. 當前字符匹配,表示從當前節點沿著樹邊有一條路徑可以到達目標字符, 此時只需沿該路徑走向下一個節點繼續匹配即可 ,目標字符串指針移向下個字符繼續匹配;

      2. 當前字符不匹配,則去當前節點失敗指針所指向的字符繼續匹配,匹配過程隨著指針指向root結束。

        重復這2個過程中的任意一個,直到模式串走到結尾為止。

         

        實現代碼:

         

        int query(node *root)//類似於 kmp算法。
        {//i為主串指針,p為匹配串指針
            int i,cnt=0,index,len=strlen(str);
            node *p=root;
            for(i=0; i < len ;i ++)
            {
               index=str[i]-'a';
              //由失敗指針回溯尋找,判斷str[i]是否存在於Trie樹中 
               while( !p->next[index] && p != root)
        	   {
        	   		p=p->fail;
        	   }
               p=p->next[index];//找到後 p 指向該節點
             
               //指針回為空,則沒有找到與之匹配的字符
              
               if(!p)
        	   {
        	   		p=root;//指針重新回到根節點root,下次從root開始搜索Trie樹
        	   }
              
               node *temp=p;//匹配該節點後,沿其失敗指針回溯,判斷其他節點是否匹配
              
               while(temp != root )//匹配 結束控制
               {
                   if(temp->count>=0)//判斷 該節點是否被訪問
                   {
                      //統計出現的單詞個數cnt,由於節點不是單詞結尾時count為0,
                     //故 cnt+=temp->count; 只有 count >0時才真正統計了單詞個數
                    
                     cnt+=temp->count;
                      temp->count=-1; //標記已訪問
                   }
                   else 
        		   		break;//節點已訪問,退出循環
                   temp=temp->fail;//回溯失敗指針繼續尋找下一個滿足條件的節點     
               }
            }
            return cnt;
        }

         

         

        三、AC自動機模板

         

        
        #include
        #include
        #include
        #define kind 26
        const int MAXN = 10000000;
        struct node
        {
            int count; //是否為單詞最後一個節點
            node *next[26];//Trie每個節點的26個子節點
            node *fail; //失敗指針
        };
        node *q[MAXN]; //隊列,采用bfs 構造失敗指針
        char keyword[55];//輸入單詞 模式串
        char str[1000010];// 需要查找的 主串
        int head,tail;//隊列 頭尾指針
        node *root;
        void insert(char *word,node *root)
        {
             int index,len;
             node *p = root,*newnode;
             len = strlen(word);
             for(int i=0 ;i < len ; i++ )
             {  
                 index=word[i]-'a';
                 if(!p->next[index])//該字符節點不存在,加入Trie樹中
                 {
                   // 初始化 newnode 並 加入 Trie 樹
                    newnode=(struct node *)malloc(sizeof(struct node));    
                    for(int j=0;j<26;j++)
        				 newnode->next[j]=0;
                    newnode->count=0;
        			newnode->fail=0;
                    p->next[index]=newnode;
                 }
                 p=p->next[index];//指針移動至下一層
             }
             p->count++;  //單詞結尾 節點 count + 1 做標記  
        }
        void build_ac_automation(node *root)
        {
            head=0;
        	tail=1;
            q[head]=root;
            node *temp,*p;
            while(headnext[i])//判斷實際存在的節點 
                     {
                         // root 下的第一層 節點 的 失敗指針都 指向root
                         if(temp==root)
        				 	temp->next[i]->fail=root;
                         else
        				 {
                            //依次回溯 該節點的父節點的失敗指針
                           //直到某節點的next[i]與該節點相同,則
                           //把該節點的失敗指針指向該next[i]節點
                           //若回溯到 root 都沒有找到,則該節點
                           //的失敗指針 指向 root
                          
                            p=temp->fail;//temp 為節點的父指針
                            while(p)
        					{
                               if(p->next[i])
        					   {
        	                       temp->next[i]->fail=p->next[i];
        	                       break;
                               }
                               p=p->fail;
                            }
                            if(!p)temp->next[i]->fail=root;
                         }
                         //每處理一個點,就把它的所有兒子加入隊列,           
                         //直到隊列為空
                         q[tail++]=temp->next[i];
                     }
                 }                
             }
        }
        int query(node *root)//類似於 kmp算法。
        {//i為主串指針,p為匹配串指針
            int i,cnt=0,index,len=strlen(str);
            node *p=root;
            for(i=0; i < len ;i ++)
            {
               index=str[i]-'a';
              //由失敗指針回溯尋找,判斷str[i]是否存在於Trie樹中 
               while( !p->next[index] && p != root)
        	   {
        	   		p=p->fail;
        	   }
               p=p->next[index];//找到後 p 指向該節點
              
               //指針回為空,則沒有找到與之匹配的字符
              
               if(!p)
        	   {
        	   	p=root;//指針重新回到根節點root,下次從root開始搜索Trie樹
        	   }
              
               node *temp=p;//匹配該節點後,沿其失敗指針回溯,判斷其他節點是否匹配
              
               while(temp != root )//匹配 結束控制
               {
                   if(temp->count>=0)//判斷 該節點是否被訪問
                   {
                      //統計出現的單詞個數cnt,由於節點不是單詞結尾時count為0,
                     //故 cnt+=temp->count; 只有 count >0時才真正統計了單詞個數
                    
                     cnt+=temp->count;
                      temp->count=-1; //標記已訪問
                   }
                   else 
        		   		break;//節點已訪問,退出循環
                   temp=temp->fail;//回溯失敗指針繼續尋找下一個滿足條件的節點     
               }
            }
            return cnt;
        }
        int main()
        {
            int i,t,n,ans;
            scanf("%d",&t);
            while(t--)
            {
               root=(struct node *)malloc(sizeof(struct node));
               for(int j=0;j<26;j++) root->next[j]=0;
               root->fail=0;
               root->count=0;
               scanf("%d",&n);
               getchar();
               for(i=0;i


         

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved