AC自动机123.doc

窗体底端

首先简要介绍一下AC自动机：Aho-Corasick automation，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法之一。一个常见的例子就是给出n个单词，再给出一段包含m个字符的文章，让你找出有多少个单词在文章里出现过。要搞懂AC自动机，先得有模式树（字典树）Trie和KMP模式匹配算法的基础知识。AC自动机算法分为3步：构造一棵Trie树，构造失败指针和模式匹配过程。
     如果你对KMP算法和了解的话，应该知道KMP算法中的next函数（shift函数或者fail函数）是干什么用的。KMP中我们用两个指针i和j分别表示，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来看，首先root的fail指针指向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，这时退出循环，并把节点e的fail指针指向root，对应图-2中的(3)，然后节点e进入队列；第3次循环时，弹出的第一个节点a的操作与上一步操作的节点e相同，把a的fail指针指向root，对应图-2中的(4)，并入队；第4次进入循环时，弹出节点h(图中左边那个)，这时操作略有不同。在程序运行到14行时，由于p->next[i]!=NULL(root有h这个儿子节点，图中右边那个)，这样便把左边那个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自动机算法的详细过程已经全部介绍结束，看一道例题：
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 极限定律 阅读(5617) 评论(9)  编辑 收藏 引用 所属分类: 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说明该节点和之后的节点已经计算过了  回复  更多评论   
字符串多模匹配算法之AC自动机理解心得
absolute8511 总结于 2009-2-26
AC自动机算法全称Aho-Corasick算法，是一种字符串多模式匹配算法。用于在一段文本中查找多个模式字符串。最近看到这个算法的一些文章，由于理解能力有限，琢磨了许久才有一些眉目，故记下此时的理解过程，防止过久了又要琢磨许久才能理解，也希望能帮助其他人加深理解，如有理解不当之处还望指出修正。^_^
总结如下：
该算法有两个主要步骤，一个是字典树的构造，一个是搜索路径的确定。
1. 字典树的构造
这个比较好理解，就是把要匹配的一些字符串添加到树结构中去，树边就是单词中的字符，单词中最后一个字符的连接节点添加标志，以表示改节点路径包含1个字典中的字符串，搜索到此节点就表示找到了字典中的某个单词，可以直接输出。
例子：某字典P=｛he,she,his,hers｝对应的字典树如下图：

图中有数字的节点到根节点的路劲正好对应字典中的字符串，数字表述单词在字典中的顺序，也可以是其他标志。
【转载请注明出处：
2. 搜索路径的确定
就是这部分我琢磨了很久，我的理解是 利用后缀字符串来确定。后缀字符串就是某个字符串的后面的一部分。比如abcde的后缀字符串有bcde,cde,de和e。
假定目标字符串为ushers，字典为上图所示。
搜索过程目标字符串指针指向的字符和字典中的字符会有以下几种情况：
a. 当前字符匹配，表示从当前节点沿着树边有一条路径可以到达目标字符，此时只需沿该路径走向下一个节点继续匹配即可，目标字符串指针移向下个字符继续匹配；
如：当指针指到s处，此时字典树指针处于根，要从根到s处，可以看到图中有一条从 根经s连接到的节点，因此字典树节点指针指向此节点，目标字符串指针移动到下一字符h继续匹配；显然当前节点有一条经h连接到的节点，于是重复操作到有数 字标志的节点2处，表示已找到，该匹配字符串就是"she"，输出该字符串的位置后，目标字符串指针增1指向"r"，字典指针指向数字2节点，进行下次匹 配。
b. 当前字符无匹配，表示当前节点的任何一条边都无法达到要匹配的字符，此时不能沿现有路径前进，只能回溯，回溯到存在的最长的后缀字符串处，如果没有任何后缀字符串匹配则回溯到树根处。然后从当前回溯节点判断是否可以到达目标字符串字符。
如：接上，由于数字2节点无经"r"的连接，因此回溯，she的后缀字符串he在字典树中，因此字典树指针指向带有数字1的标志节点，由于带有标志，直接输出该节点"HE"(存疑，很多文章没有提到此处需要输出，正常路径移动的字典指针节点要判断是否可以输出，那么由回溯路径改变的字典指针指向的节点要不要判断是否输出？)，然后从数字1节点判断是否有经"r"到下一节点的路径，显然图中有。因此字典树节点指向下一节点，重复以上操作，最后找到"hers"，此时匹配搜索也结束了。
以上两种情况直到目标字符串指针直到末尾结束匹配。在匹配过程中遇到有标志的节点说明找到了字典中的某个词，可以直接输出。
更新：输出说明：每次目标串指针移动前都需要判断当前节点是否可以输出，并递归的判断当前节点回溯路径上的节点是否可以输出（其实就是判断所有后缀字符串，she匹配时，其后缀he也会匹配，即使she不匹配，其后缀he也可能匹配，因此需递归判断后缀字符串），直到树根结束递归。
由于固定字典的字符串的后缀字符串都是已知的，因此可以在字典树结构中存储匹配失败的路径方向，因此只要字典树构造完毕，就可以根据字典树的路径进行匹配了，效率非常快。以上就是我对该算法的全部过程的理解，疏漏之处在所难免。
附1：含匹配失败的情况的路径选择的字典树，实线表示匹配成功的正常路径，虚线表示失败的回溯路径

附2：伪代码实现
T为目标字符串，长度为m，q为字典树的节点指针，g函数返回从节点q经过路径T[i]到达的下一节点指针，f函数返回节点q的回溯节点指针。flag判断节点是否为标志节点
q := 0; // initial state (root)
for i := 1 to m do
    while g(q,T[i]) = NULL do
        q := f(q); // 回溯
    q := g(q,T[i]); // 前进
    node:=q;
    while(node!=root){
        if flag(node) exist ; then print i, out(node);
        node = f(node);   //查找回溯节点
    }
endfor;
参考资料：Biosequence Algorithms, Spring 2005 Lecture 4: Set Matching and
Aho-Corasick Algorithm. Pekka Kilpelainen
【转载请注明出处：
关键词：AC多模式字符串匹配算法，字符串搜索，查找字典中出现的字符串，字符串多模式匹配算法，多个字符串查找

////////////////////////////////////////////////////
/*
程序说明：多模式串匹配的AC自动机算法
此题通过hdu 2222
自动机算法可以参考《柔性字符串匹配》里的相应章节，讲的很清楚
*/
#include <stdio.h>
#include <string.h>

const int MAXQ = 500000+10;
const int MAXN = 1000000+10;
const int MAXK = 26; //自动机里字符集的大小
struct TrieNode
{
TrieNode* fail;
TrieNode* next[MAXK];
bool danger; //该节点是否为某模式串的终结点
int cnt; //以该节点为终结点的模式串个数
TrieNode()
{
fail = NULL;
memset(next, NULL, sizeof(next));
danger = false;
cnt = 0;
}
}*que[MAXQ], *root;
//文本字符串
char msg[MAXN];
int N;
void TrieInsert(char *s)
{
int i = 0;
TrieNode *ptr = root;
while(s[i])
{
int idx = s[i]-'a';
if(ptr->next[idx] == NULL)
ptr->next[idx] = new TrieNode();
ptr = ptr->next[idx];
i++;
}
ptr->danger = true;
ptr->cnt++;
}

void Init()
{
int i;
char s[100];
root = new TrieNode();
scanf("%d", &N);
for(i = 0; i < N; i++)
{
scanf("%s", s);
TrieInsert(s);
}
}

void Build_AC_Automation()
{
int rear = 1, front = 0, i;
que[0] = root;
root->fail = NULL;
while(rear != front)
{
TrieNode *cur = que[front++];
for(i = 0; i < 26; i++)
if(cur->next[i] != NULL)
{
if(cur == root)
cur->next[i]->fail = root;
else
{
TrieNode *ptr = cur->fail;
while(ptr != NULL)
{
if(ptr->next[i] != NULL)
{
cur->next[i]->fail = ptr->next[i];
if(ptr->next[i]->danger == true)
cur->next[i]->danger = true;
break;
}
ptr = ptr->fail;
}
if(ptr == NULL) cur->next[i]->fail = root;
}
que[rear++] = cur->next[i];
}
}
}

int AC_Search()
{
int i = 0, ans = 0;
TrieNode *ptr = root;
while(msg[i])
{
int idx = msg[i]-'a';
while(ptr->next[idx] == NULL && ptr != root) ptr = ptr->fail;
ptr = ptr->next[idx];
if(ptr == NULL) ptr = root;
TrieNode *tmp = ptr;
while(tmp != NULL && tmp->cnt != -1)
{
ans += tmp->cnt;
tmp->cnt = -1;
tmp = tmp->fail;
}
i++;
}
return ans;
}

int main()
{
int T;
scanf("%d", &T);
while(T--)
{
Init();
Build_AC_Automation();
//文本
scanf("%s", msg);
printf("%d\n", AC_Search());
}
return 0;
}