首页 > 代码库 > ac自动机基本

ac自动机基本

2024-11-03 08:59:39   208人阅读

　　今天研究了一下ac自动机，感觉学了些入门的知识，什么可持久化自动机、有限状态自动机，还有自动机上的DP还不是很懂。所以今天先贴基本代码，以后补充其他知识。

　　参考资料：http://blog.csdn.net/niushuai666/article/details/7002823。里面介绍很详细了，特别是构造fail指针那幅图特别经典。注意到KMP的有两种写法：第i位fail指针指向前面某个具有相同元素的最近位置j；或第i位fail指针指向前面最近的具有不同元素的位置j，但要求i-1与j-1元素相同。（两种KMP匹配时稍有差异，第一种会好处理，第二种速度更快因为避免了很多重复但匹配不到的情况）。而ac自动机虽基于KMP，但一般会写第一种即fail指向元素相同而非不同的位置（那幅图明显体现了），至于为什么，第二种不好处理我也不大会写orz。

　　直接上代码，功能的是判断若干个给定字符串是否在字符串str中出现过。

　　

技术分享 
 1 #include<iostream>
 2 #include<string.h>
 3 #include<queue>
 4 using namespace std;
 5 
 6 struct trie_node
 7 {
 8     trie_node *fa,*next[26],*fail;
 9     char cc;
10     bool end;
11 }*root;
12 
13 void mdy(trie_node* now,trie_node* fa,char cc)//mordify
14 {
15     long i;
16     now->fa=fa;
17     for (i=0;i<26;i++)now->next[i]=NULL;
18     now->cc=cc;
19     now->end=false;
20 }
21 
22 void update(string ss,trie_node* now)//insert strings into Trie
23 {
24     char cc;
25     cc=ss[0];
26     if (now->next[cc-‘a‘]==NULL){
27         now->next[cc-‘a‘]=new trie_node;
28         mdy(now->next[cc-‘a‘],now,cc);
29     }
30     if (ss.length()==1){
31         now->next[cc-‘a‘]->end=true;
32         return;
33     } else update(ss.substr(1),now->next[cc-‘a‘]);
34 }
35 
36 void build_fail()//BFS
37 {
38     queue<trie_node*>v;
39     trie_node *fail,*now;
40     long i;
41     char cc;
42     v.push(root);
43     while (!v.empty()){
44         now=v.front();
45         v.pop();
46         fail=now->fa->fail,cc=now->cc;
47         while (fail!=NULL){
48             if (fail->next[cc-‘a‘]!=NULL){
49                 fail=fail->next[cc-‘a‘];
50                 break;
51             } else fail=fail->fail;
52         }
53         if (fail==NULL)fail=root;
54         now->fail=fail;
55         for (i=0;i<26;i++)if (now->next[i]!=NULL)v.push(now->next[i]);
56     }//root‘s fail->root
57 }
58 
59 bool ac_automachine(string str)//matching,to find if those string in trie have appeared in str(also you can change into different function)
60 {
61     trie_node* now;
62     long i;
63     char cc;
64     now=root;
65     for (i=0;i<str.length();i++){
66         cc=str[i];
67         while (now!=NULL)
68             if (now->next[cc-‘a‘]!=NULL){
69                 now=now->next[cc-‘a‘];
70                 break;
71             } else now=now->fail;
72         if (now==NULL)now=root;
73             else if (now->end)return true;
74     }
75     return false;
76 }
77 
78 int main()
79 {
80     string s1,str;
81     long n,i;
82     cin>>n;
83     mdy(root,NULL,‘ ‘);
84     for (i=1;i<=n;i++){
85         cin>>s1;
86         update(s1,root);
87     }
88     build_fail();
89     cin>>str;
90     if (ac_automachine(str))cout<<"YES there is."<<endl;
91         else cout<<"NO there isn‘t."<<endl;
92     return 0;
93 }
ac_automachine

 

ac自动机基本


联系
我们