青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

AC自動機算法詳解

    首先簡要介紹一下AC自動機:Aho-Corasick automation,該算法在1975年產生于貝爾實驗室,是著名的多模匹配算法之一。一個常見的例子就是給出n個單詞,再給出一段包含m個字符的文章,讓你找出有多少個單詞在文章里出現過。要搞懂AC自動機,先得有模式樹(字典樹)TrieKMP模式匹配算法的基礎知識。AC自動機算法分為3步:構造一棵Trie樹,構造失敗指針和模式匹配過程。
     如果你對KMP算法和了解的話,應該知道KMP算法中的next函數(shift函數或者fail函數)是干什么用的。KMP中我們用兩個指針ij分別表示,A[i-j+ 1..i]B[1..j]完全相等。也就是說,i是不斷增加的,隨著i的增加j相應地變化,且j滿足以A[i]結尾的長度為j的字符串正好匹配B串的前 j個字符,當A[i+1]B[j+1]KMP的策略是調整j的位置(減小j值)使得A[i-j+1..i]B[1..j]保持匹配且新的B[j+1]恰好與A[i+1]匹配,而next函數恰恰記錄了這個j應該調整到的位置。同樣AC自動機的失敗指針具有同樣的功能,也就是說當我們的模式串在Tire上進行匹配時,如果與當前節點的關鍵字不能繼續匹配的時候,就應該去當前節點的失敗指針所指向的節點繼續進行匹配。
      看下面這個例子:給定5個單詞:say she shr he her,然后給定一個字符串yasherhs問一共有多少單詞在這個字符串中出現過。我們先規定一下AC自動機所需要的一些數據結構,方便接下去的編程。
 1 const int kind = 26
 2 struct node{  
 3     node *fail;       //失敗指針
 4     node *next[kind]; //Tire每個節點的個子節點(最多個字母)
 5     int count;        //是否為該單詞的最后一個節點
 6     node(){           //構造函數初始化
 7         fail=NULL; 
 8         count=0
 9         memset(next,NULL,sizeof(next)); 
10     } 
11 }*q[500001];          //隊列,方便用于bfs構造失敗指針
12 char keyword[51];     //輸入的單詞
13 char str[1000001];    //模式串
14 int head,tail;        //隊列的頭尾指針

有了這些數據結構之后,就可以開始編程了:
   
首先,將這5個單詞構造成一棵Tire,如圖-1所示。

 

 1 void insert(char *str,node *root){ 
 2     node *p=root; 
 3     int i=0,index;  
 4     while(str[i]){ 
 5         index=str[i]-'a'
 6         if(p->next[index]==NULL) p->next[index]=new node();  
 7         p=p->next[index];
 8         i++;
 9     } 
10     p->count++;     //在單詞的最后一個節點count+1,代表一個單詞
11 }

在構造完這棵Tire之后,接下去的工作就是構造下失敗指針。構造失敗指針的過程概括起來就一句話:設這個節點上的字母為C,沿著他父親的失敗指針走,直到走到一個節點,他的兒子中也有字母為C的節點。然后把當前節點的失敗指針指向那個字母也為C的兒子。如果一直走到了root都沒找到,那就把失敗指針指向root。具體操作起來只需要:先把root加入隊列(root的失敗指針指向自己或者NULL),這以后我們每處理一個點,就把它的所有兒子加入隊列,隊列為空。

 1 void build_ac_automation(node *root){
 2     int i;
 3     root->fail=NULL; 
 4     q[head++]=root; 
 5     while(head!=tail){ 
 6         node *temp=q[tail++]; 
 7         node *p=NULL; 
 8         for(i=0;i<26;i++){ 
 9             if(temp->next[i]!=NULL){ 
10                 if(temp==root) temp->next[i]->fail=root;                 
11                 else
12                     p=temp->fail; 
13                     while(p!=NULL){  
14                         if(p->next[i]!=NULL){ 
15                             temp->next[i]->fail=p->next[i]; 
16                             break
17                         } 
18                         p=p->fail; 
19                     } 
20                     if(p==NULL) temp->next[i]->fail=root; 
21                 } 
22                 q[head++]=temp->next[i];  
23             } 
24         }   
25     } 
26 }

    從代碼觀察下構造失敗指針的流程:對照圖-2來看,首先rootfail指針指向NULL,然后root入隊,進入循環。第1次循環的時候,我們需要處理2個節點:root->next[‘h’-‘a’](節點h) root->next[‘s’-‘a’](節點s)。把這2個節點的失敗指針指向root,并且先后進入隊列,失敗指針的指向對應圖-2中的(1)(2)兩條虛線;第2次進入循環后,從隊列中先彈出h,接下來p指向h節點的fail指針指向的節點,也就是root;進入第13行的循環后,p=p->fail也就是p=NULL,這時退出循環,并把節點efail指針指向root,對應圖-2中的(3),然后節點e進入隊列;第3次循環時,彈出的第一個節點a的操作與上一步操作的節點e相同,把afail指針指向root,對應圖-2中的(4),并入隊;第4次進入循環時,彈出節點h(圖中左邊那個),這時操作略有不同。在程序運行到14行時,由于p->next[i]!=NULL(rooth這個兒子節點,圖中右邊那個),這樣便把左邊那個h節點的失敗指針指向右邊那個root的兒子節點h,對應圖-2中的(5),然后h入隊。以此類推:在循環結束后,所有的失敗指針就是圖-2中的這種形式。

  最后,我們便可以在AC自動機上查找模式串中出現過哪些單詞了。匹配過程分兩種情況:(1)當前字符匹配,表示從當前節點沿著樹邊有一條路徑可以到達目標字符,此時只需沿該路徑走向下一個節點繼續匹配即可,目標字符串指針移向下個字符繼續匹配;(2)當前字符不匹配,則去當前節點失敗指針所指向的字符繼續匹配,匹配過程隨著指針指向root結束。重復這2個過程中的任意一個,直到模式串走到結尾為止。
 1 int query(node *root){ 
 2     int i=0,cnt=0,index,len=strlen(str); 
 3     node *p=root;  
 4     while(str[i]){  
 5         index=str[i]-'a';  
 6         while(p->next[index]==NULL && p!=root) p=p->fail; 
 7         p=p->next[index]; 
 8         p=(p==NULL)?root:p; 
 9         node *temp=p; 
10         while(temp!=root && temp->count!=-1){ 
11             cnt+=temp->count; 
12             temp->count=-1
13             temp=temp->fail; 
14         } 
15         i++;                 
16     }    
17     return cnt; 
18 }
    對照圖-2,看一下模式匹配這個詳細的流程,其中模式串為yasherhs。對于i=0,1。Trie中沒有對應的路徑,故不做任何操作;i=2,3,4時,指針p走到左下節點e。因為節點e的count信息為1,所以cnt+1,并且講節點e的count值設置為-1,表示改單詞已經出現過了,防止重復計數,最后temp指向e節點的失敗指針所指向的節點繼續查找,以此類推,最后temp指向root,退出while循環,這個過程中count增加了2。表示找到了2個單詞she和he。當i=5時,程序進入第5行,p指向其失敗指針的節點,也就是右邊那個e節點,隨后在第6行指向r節點,r節點的count值為1,從而count+1,循環直到temp指向root為止。最后i=6,7時,找不到任何匹配,匹配過程結束。

    到此為止AC自動機算法的詳細過程已經全部介紹結束,看一道例題:http://acm.hdu.edu.cn/showproblem.php?pid=2222
Problem Description
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

 1 #include <iostream> 
 2 using namespace std; 
 3   
 4 const int kind = 26
 5 struct node{  
 6     node *fail;       //失敗指針
 7     node *next[kind]; //Tire每個節點的26個子節點(最多26個字母)
 8     int count;        //是否為該單詞的最后一個節點
 9     node(){           //構造函數初始化
10         fail=NULL; 
11         count=0
12         memset(next,NULL,sizeof(next)); 
13     } 
14 }*q[500001];          //隊列,方便用于bfs構造失敗指針
15 char keyword[51];     //輸入的單詞
16 char str[1000001];    //模式串
17 int head,tail;        //隊列的頭尾指針
18   
19 void insert(char *str,node *root){ 
20     node *p=root; 
21     int i=0,index;  
22     while(str[i]){ 
23         index=str[i]-'a'
24         if(p->next[index]==NULL) p->next[index]=new node();  
25         p=p->next[index];
26         i++;
27     } 
28     p->count++
29 
30 void build_ac_automation(node *root){
31     int i;
32     root->fail=NULL; 
33     q[head++]=root; 
34     while(head!=tail){ 
35         node *temp=q[tail++]; 
36         node *p=NULL; 
37         for(i=0;i<26;i++){ 
38             if(temp->next[i]!=NULL){ 
39                 if(temp==root) temp->next[i]->fail=root;                 
40                 else
41                     p=temp->fail; 
42                     while(p!=NULL){  
43                         if(p->next[i]!=NULL){ 
44                             temp->next[i]->fail=p->next[i]; 
45                             break
46                         } 
47                         p=p->fail; 
48                     } 
49                     if(p==NULL) temp->next[i]->fail=root; 
50                 } 
51                 q[head++]=temp->next[i];  
52             } 
53         }   
54     } 
55 
56 int query(node *root){ 
57     int i=0,cnt=0,index,len=strlen(str); 
58     node *p=root;  
59     while(str[i]){  
60         index=str[i]-'a';  
61         while(p->next[index]==NULL && p!=root) p=p->fail; 
62         p=p->next[index]; 
63         p=(p==NULL)?root:p; 
64         node *temp=p; 
65         while(temp!=root && temp->count!=-1){ 
66             cnt+=temp->count; 
67             temp->count=-1
68             temp=temp->fail; 
69         } 
70         i++;                 
71     }    
72     return cnt; 
73 
74 int main(){ 
75     int n,t; 
76     scanf("%d",&t); 
77     while(t--){  
78         head=tail=0
79         node *root=new node(); 
80         scanf("%d",&n); 
81         getchar(); 
82         while(n--){ 
83             gets(keyword); 
84             insert(keyword,root); 
85         } 
86         build_ac_automation(root); 
87         scanf("%s",str); 
88         printf("%d\n",query(root));  
89     } 
90     return 0
91 }

    PS:原創,轉載請注明出處

posted on 2009-04-21 18:22 極限定律 閱讀(68515) 評論(40)  編輯 收藏 引用 所屬分類: ACM/ICPC

評論

# re: AC自動機算法詳解 2009-06-13 09:53 zab08

bfs寫成 頭入尾出...

  回復  更多評論   

# re: AC自動機算法詳解 2009-07-30 15:39 xtu715

您好,對于例題,請測試如下樣例:
1
2
tacab
aca
wqzpacakkk

您程序給出的答案是1.
可根據題意,正確答案應該是2.

您代碼中65行,貌似有誤。

  回復  更多評論   

# re: AC自動機算法詳解 2009-07-30 15:49 xtu715

是我的錯,請無視。不好意思  回復  更多評論   

# re: AC自動機算法詳解 2009-08-25 14:00 zeus

沒想到又到你這里來 呵呵 看看先  回復  更多評論   

# re: AC自動機算法詳解 2009-08-26 15:47 路過

1
5
bhea
her
he
h
ha
bhera
輸出?  回復  更多評論   

# re: AC自動機算法詳解[未登錄] 2009-10-16 11:35 DD

65行的代碼temp->count!=-1這個條件不能要,否則就是錯誤的。  回復  更多評論   

# re: AC自動機算法詳解 2010-01-11 21:46 niubi

是主串在trie上匹配,不是模式串吧。。  回復  更多評論   

# re: AC自動機算法詳解[未登錄] 2010-02-26 13:09 intheway

好東東,樓主辛苦了.  回復  更多評論   

# re: AC自動機算法詳解 2010-07-14 00:38 MJ_LC

@DD
如果temp->count!=-1說明該節點和之后的節點已經計算過了  回復  更多評論   

# re: AC自動機算法詳解 2010-12-07 22:32 周燎明

@MJ_LC

請考慮第66與67 行,考慮將67行加一個執行判斷條件:if count==1 再做賦值操作。。。  回復  更多評論   

# re: AC自動機算法詳解[未登錄] 2010-12-22 20:03 AC

失敗指針構造的描述好模糊。看了半天還是沒看懂。。繼續再看  回復  更多評論   

# re: AC自動機算法詳解 2011-03-10 21:44 dereky

膜拜了  回復  更多評論   

# re: AC自動機算法詳解 2011-04-08 11:19

你的代碼錯了 失敗函數寫得有問題  回復  更多評論   

# re: AC自動機算法詳解 2011-05-28 19:45 anmtcel

您的程序會怎么處理模式串為
abcd和bc這兩個,
主串為abcde的這個問題?
應該是兩個串都出現了
但您的程序應該只會找到第一個串,

因為從a一直順利的走向d,但d的失敗指針直接指向根了,
也就是不會走到bc那條小路里去。

我有個想法,就是需不需要預處理出哪些串是被當前串包含的,
存當前串所包含的串的位置,也就是當當前串被查找出來后,這些位置也標記為已查找  回復  更多評論   

# re: AC自動機算法詳解 2011-06-19 20:15 fotile

我只想說,您的代碼實在不漂亮。  回復  更多評論   

# re: AC自動機算法詳解 2011-06-19 20:23 fotile

講解很淺顯易懂,代碼里一串一串的!=NULL還要很多不必要的判斷實在是配不上文字的高超。  回復  更多評論   

# re: AC自動機算法詳解 2011-07-03 13:46 酷行天下

大牛講的非常透徹,贊一個……  回復  更多評論   

# re: AC自動機算法詳解 2011-07-31 21:23 aa

膜拜  回復  更多評論   

# re: AC自動機算法詳解 2011-08-13 14:24 aaa

各種trie寫成tire  回復  更多評論   

# re: AC自動機算法詳解 2011-08-19 22:15 Evan

@路過
應該是4 吧。  回復  更多評論   

# re: AC自動機算法詳解 2011-10-21 11:04 mmx

好!  回復  更多評論   

# re: AC自動機算法詳解 2011-12-01 01:58 Miu_Y

節點申請了不釋放?  回復  更多評論   

# re: AC自動機算法詳解 2012-02-27 20:55 ITX351

57行為什么要求長度= = 不理解  回復  更多評論   

# re: AC自動機算法詳解 2012-04-09 17:18 himdd

char str[1000001];應該叫目標串吧。。  回復  更多評論   

# re: AC自動機算法詳解 2012-04-26 09:57 Lucian

內容很棒,很容易理解!  回復  更多評論   

# re: AC自動機算法詳解 2012-05-16 11:25 wzq

多組數據的話,每組做完指針是不是應該釋放呢?  回復  更多評論   

# re: AC自動機算法詳解 2012-07-15 23:12 re

代碼bug超多  回復  更多評論   

# re: AC自動機算法詳解 2012-09-13 12:06 cqwelly

頂一下  回復  更多評論   

# re: AC自動機算法詳解 2012-12-24 18:22 陳文康

@xtu715
為啥是2??  回復  更多評論   

# re: AC自動機算法詳解 2013-02-17 16:42 h

temp->count!=-1
注意:1、重復的只算一次;2、初始的count=0
模式串為
abcd和bc這兩個,
主串為abcde的這個問題?
當找到c時,count[c]=0,tmp指針找到串bc的結尾c并統計。
  回復  更多評論   

# re: AC自動機算法詳解 2013-05-02 21:11 xero essential

其實程序上的錯誤無傷大雅,個人感覺看了第一段就明白原理了,剩下的只是驗證。。  回復  更多評論   

# re: AC自動機算法詳解[未登錄] 2013-08-10 21:47 111

好東西,謝了!  回復  更多評論   

# re: AC自動機算法詳解 2014-03-09 10:03 testcc

不會內存泄露么??  回復  更多評論   

# re: AC自動機算法詳解 2014-03-25 10:28 Islo

orz  回復  更多評論   

# re: AC自動機算法詳解 2014-07-29 16:28 lb

先把root加入隊列(root的失敗指針指向自己或者NULL),這以后我們每處理一個點,就把它的所有兒子加入隊列,隊列為空。
這句話什么意思  回復  更多評論   

# re: AC自動機算法詳解 2014-09-12 12:55 Vmurder

@xtu715
為什么是2?  回復  更多評論   

# re: AC自動機算法詳解 2015-05-10 11:23

http://sunmoon-template.blogspot.tw/2015/05/aho-corasick-automation-ac.html
構造的地方可以更簡潔  回復  更多評論   

# re: AC自動機算法詳解 2015-07-26 19:13 @anyi

真好  回復  更多評論   

# re: AC自動機算法詳解 2015-08-20 11:30 fastmatch

@anmtcel
abcd和bc不在一個分支上  回復  更多評論   

<2015年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

導航

統計

常用鏈接

留言簿(10)

隨筆分類

隨筆檔案

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            国产精品天天看| 国产精品户外野外| 亚洲人成77777在线观看网| 免费成人小视频| 欧美高清视频一区二区| 一区二区三区四区国产| 亚洲视频免费在线| 国产午夜精品理论片a级大结局 | 亚洲国产天堂网精品网站| 欧美黄色一级视频| 欧美三级乱码| 久久久久久久久久久久久女国产乱 | 久久久www| 老牛影视一区二区三区| 9色国产精品| 性伦欧美刺激片在线观看| 一区在线观看| 亚洲乱码国产乱码精品精天堂| 欧美视频一区二区三区…| 久久久久久亚洲精品中文字幕| 亚洲在线免费| 最新日韩中文字幕| 国产精品超碰97尤物18| 免费观看在线综合色| 欧美深夜福利| 欧美成人小视频| 欧美伊人久久久久久久久影院 | 欧美性色综合| 美女国产一区| 国产精品麻豆va在线播放| 免费久久99精品国产| 国产精品国产三级国产aⅴ9色| 免费永久网站黄欧美| 国产精品va在线| 欧美高清免费| 狠狠色狠色综合曰曰| 一区二区三区|亚洲午夜| 在线免费观看欧美| 亚洲欧美日韩成人| 亚洲一卡久久| 欧美激情aⅴ一区二区三区 | 一本色道久久综合亚洲精品不卡| 久久电影一区| 欧美资源在线观看| 国产精品久久久久9999吃药| 91久久久久久| 亚洲国产精品电影| 久久亚洲私人国产精品va媚药| 亚洲欧美精品中文字幕在线| 欧美激情欧美激情在线五月| 欧美华人在线视频| 亚洲国产天堂久久国产91| 久久久久一区| 麻豆久久婷婷| 在线日本成人| 久久男女视频| 久久综合伊人| 亚洲成在人线av| 久久久青草青青国产亚洲免观| 久久精品欧洲| 国产一区二区福利| 欧美中文字幕第一页| 久久久国产成人精品| 国产真实精品久久二三区| 性xx色xx综合久久久xx| 久久精品女人| 在线观看不卡| 男人的天堂成人在线| 亚洲国产天堂久久综合网| 亚洲人成网站777色婷婷| 欧美精选一区| 一区二区三区www| 亚洲欧美日韩直播| 国产欧美日韩激情| 欧美激情一区二区三区成人| 亚洲高清影视| 欧美韩日一区二区三区| 日韩视频在线永久播放| 亚洲综合精品自拍| 国产三区二区一区久久 | 91久久精品视频| 亚洲一二三区精品| 国产精品尤物| 老司机成人网| 一区二区高清在线观看| 新67194成人永久网站| 一区二区在线视频| 欧美日韩视频在线一区二区 | 狂野欧美一区| aa级大片欧美| 久久天天躁夜夜躁狠狠躁2022| 在线观看日韩欧美| 欧美三级视频在线播放| 欧美一区二区成人| 亚洲人成亚洲人成在线观看| 亚洲欧美一区二区三区久久 | 国产精品男gay被猛男狂揉视频| 午夜精品国产更新| 亚洲国产三级在线| 久久精品免费| 亚洲永久在线| 在线免费日韩片| 国产精品极品美女粉嫩高清在线| 久久精品导航| 一区二区三区黄色| 欧美国产综合视频| 欧美在线www| 一区二区三区免费网站| 国内精品亚洲| 国产精品久久久久一区二区三区| 美脚丝袜一区二区三区在线观看 | 欧美精品色网| 久久精品综合| 亚洲小视频在线观看| 亚洲国产美女| 性欧美激情精品| 亚洲图片自拍偷拍| 亚洲国产美女精品久久久久∴| 国产精品人成在线观看免费 | 亚洲精品国产精品国自产观看| 国产精品亚洲一区二区三区在线| 欧美va亚洲va香蕉在线| 久久久国产一区二区三区| 亚洲欧美日本日韩| 亚洲视频日本| 一区二区三区**美女毛片| 最新国产成人在线观看| 欧美91精品| 欧美国产第一页| 久久久人人人| 久久精品噜噜噜成人av农村| 亚洲免费一在线| 亚洲调教视频在线观看| 一本色道久久综合狠狠躁篇怎么玩| 欧美激情亚洲自拍| 美女脱光内衣内裤视频久久影院 | 亚洲高清免费视频| 伊人成人在线| 一区二区三区中文在线观看| 国产一区二区三区在线观看免费视频 | 翔田千里一区二区| 欧美亚洲一区二区在线观看| 亚洲一二三区在线观看| 亚洲图片欧美一区| 亚洲欧美中日韩| 欧美一区2区视频在线观看| 性色一区二区三区| 久久久九九九九| 久久综合中文| 欧美高清免费| 欧美性大战xxxxx久久久| 国产精品午夜久久| 国产曰批免费观看久久久| 一区视频在线播放| 91久久精品一区二区别| 99xxxx成人网| 亚洲欧美亚洲| 巨乳诱惑日韩免费av| 亚洲国产高清一区| 亚洲深夜福利网站| 欧美一区二区三区四区在线观看地址 | 好看的日韩av电影| 亚洲激情网站| 亚洲一区二区三区在线播放| 欧美一区三区三区高中清蜜桃| 久久久噜噜噜久久中文字幕色伊伊| 久久夜色精品国产| 欧美激情亚洲精品| 亚洲小视频在线| 久久偷看各类wc女厕嘘嘘偷窃| 欧美精品在欧美一区二区少妇| 国产精品久久九九| 亚洲第一在线| 亚洲欧美99| 欧美jizz19性欧美| 一区二区三区日韩精品| 久久亚洲影音av资源网| 欧美日韩精品国产| 国自产拍偷拍福利精品免费一| 亚洲毛片网站| 在线观看日韩av电影| 亚洲无线视频| 欧美大学生性色视频| 国产精品99久久久久久人| 久久综合五月| 国产精品一区二区三区观看 | 国产精品一区二区你懂得| 91久久国产精品91久久性色| 欧美亚洲综合在线| 国产伦理一区| 亚洲视频一区在线观看| 久久一区二区三区超碰国产精品| 99热在这里有精品免费| 久久一区二区三区四区| 国产精品一区二区久久久| 一本色道88久久加勒比精品 | 亚洲欧洲在线观看| 美日韩免费视频| 激情综合激情| 久久精品亚洲一区二区|