AC自动机-hdu2222 hdu2896

hdu2222 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2222

题目大意：给定一堆模式串和一个匹配串，问匹配串中包含多少模式串

AC自动机板子中的板子题。AC自动机的前需知识是KMP和trie树（字典树），需要的KMP的思想就是失配之后的最优化处理。事实上，AC自动机是在trie树上做一个失配最优化，也就是在trie树的基础上建立fail树。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 #include<queue>
 5 using namespace std;
 6 
 7 #define maxn 1000005
 8 
 9 int trie[maxn][26];
10 int fail[maxn];
11 int cntword[maxn];
12 int cnt;
13 
14 void insertWords(char s[])
15 {
16     int root=0;
17     int len=strlen(s);
18     for(int i=0;i<len;i++)
19     {
20         int next=s[i]-'a';
21         if(!trie[root][next]){
22             trie[root][next]=++cnt;
23         }
24         root=trie[root][next];
25     }
26     cntword[root]++;
27 }
28 
29 void getFail()
30 {
31     queue<int>q;
32     while(!q.empty()) q.pop();
33     int now=0;
34     for(int i=0;i<26;i++){
35         if(trie[now][i]){
36             fail[trie[now][i]]=0;
37             q.push(trie[now][i]);
38         }
39     }
40     while(!q.empty()){
41         now = q.front();
42         q.pop();
43         for(int i=0;i<26;i++){
44             if(trie[now][i]){
45                 fail[trie[now][i]]=trie[fail[now]][i];
46                 q.push(trie[now][i]);
47             }
48             else trie[now][i]=trie[fail[now]][i];
49         }
50     }
51 }
52 
53 int query(char s[])
54 {
55     int ans=0,now=0,len=strlen(s);
56     for(int i=0;i<len;i++){
57         now=trie[now][s[i]-'a'];
58         for(int j=now;j&&cntword[j]!=-1;j=fail[j])
59         {
60             ans+=cntword[j];
61             cntword[j]=-1;
62         }
63     }
64     return ans;
65 }
66 
67 int main()
68 {
69     int n;
70     int t;
71     scanf("%d",&t);
72     char s[maxn];
73     while(t--)
74     {
75         memset(fail,0,sizeof(fail));
76         memset(trie,0,sizeof(trie));
77         memset(cntword,0,sizeof(cntword));
78         cnt=0;
79         scanf("%d",&n);
80         while(n--)
81         {
82             scanf("%s",s);
83             insertWords(s);
84         }
85         fail[0]=0;
86         getFail();
87         scanf("%s",s);
88         printf("%d
",query(s));
89     }
90     return 0;
91 }

hdu2222

hdu2896 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2896

题目大意：给定n个模式串，m个匹配串，求每个匹配串中有哪写模式串，所有匹配串中有多少匹配到模式串。

这题也是一道AC自动机板子题，比上面hdu2222稍有些难度，这里我们先将模式串构建好树，然后去跑匹配串，要注意的是这里不在是仅有小写字母，题目中说到：以上字符串中的字符都是ASCII码可见字符（不包括回车）。由于我们需要记录每个匹配串匹配结果信息，我们可以开一个存储空间存储这些信息。

  1 #include<stdio.h>
  2 #include<algorithm>
  3 #include<string.h>
  4 #include<queue>
  5 using namespace std;
  6 
  7 #define maxn 100005
  8 
  9 char a[505][205];
 10 int trie[maxn][130];
 11 int fail[maxn];
 12 int idword[maxn];
 13 int cnt=0;
 14 
 15 void insertWords(int id)
 16 {
 17     int len=strlen(a[id]);
 18     int now=0;
 19     for(int i=0;i<len;i++)
 20     {
 21         int next=a[id][i];
 22         if(!trie[now][next])
 23             trie[now][next]=++cnt;
 24         now=trie[now][next];
 25     }
 26     idword[now]=id;
 27 }
 28 
 29 void getFail()
 30 {
 31     queue<int> q;
 32     while(!q.empty()) q.pop();
 33     for(int i=0;i<130;i++)
 34     {
 35         if(trie[0][i]){
 36             fail[trie[0][i]]=0;
 37             q.push(trie[0][i]);
 38         }
 39     }
 40     int now=0;
 41     while(!q.empty()){
 42         int now=q.front();
 43         q.pop();
 44         for(int i=0;i<130;i++){
 45             if(trie[now][i]){
 46                 fail[trie[now][i]]=trie[fail[now]][i];
 47                 q.push(trie[now][i]);
 48             }
 49             else trie[now][i]=trie[fail[now]][i];
 50         }
 51     }
 52 }
 53 int an[505];
 54 int anss=0;
 55 void getans(char s[])
 56 {
 57     int len=strlen(s);
 58     int now=0;
 59     for(int i=0;i<len;i++){
 60         now=trie[now][s[i]];
 61         for(int j=now;j&&idword[j]!=0;j=fail[j]){
 62             if(!an[idword[j]])
 63             {
 64                 an[idword[j]]=1;
 65             anss++;
 66             }
 67         }
 68     }
 69 }
 70 
 71 int main()
 72 {
 73     int n,m;
 74     scanf("%d",&n);
 75     for(int i=1;i<=n;i++)
 76     {
 77         scanf("%s",a[i]);
 78         insertWords(i);
 79     }
 80     getFail();
 81     fail[0]=0;
 82     scanf("%d",&m);
 83     char s[10005];
 84     int ans=0;
 85     for(int i=1;i<=m;i++)
 86     {
 87         anss=0;
 88         memset(an,0,sizeof(an));
 89         scanf("%s",s);
 90         getans(s);
 91         if(anss!=0){
 92             //printf("anss=%d
",anss);
 93             ans++;
 94             printf("web %d: ",i);
 95             for(int j=1;j<=n;j++)
 96             {
 97                 if(an[j]){
 98                     anss--;
 99                     if(anss)
100                         printf("%d ",j);
101                     else {
102                         printf("%d
",j);break;
103                     }
104                 }
105             }
106         }
107     }
108     printf("total: %d
",ans);
109     return 0;
110 }

hdu2896