hdu2222 Keywords Search

题目连接

题意：每组数据中有n个子串，给出目标串，求出共有多少个子串在目标串中出现过，输出数量。

题解：妥妥的ac自动机（多模匹配算法），是个模板题。

ac自动机学习参考链接（大佬的图画的太棒了）：

https://blog.csdn.net/weixin_40317006/article/details/81327188

https://blog.csdn.net/creatorx/article/details/7110084

链表版

  1 #include<stdio.h>
  2 #include<algorithm>
  3 #include<string.h>
  4 #include<malloc.h>
  5 using namespace std;
  6 
  7 const int maxn=1e7+10;
  8 
  9 struct node
 10 {
 11     node *next[26];     //下一个字母
 12     node *fail;        //失败指针
 13     int sum;        //几个单词结点
 14 };
 15 
 16 node *root;
 17 node *newnode;
 18 int head,tail;
 19 node *q[maxn];
 20 char pattern[maxn];
 21 char key[100];
 22 int cnt;
 23 
 24 void insert(char *s)
 25 {
 26     node *p=root;
 27     for(int i=0;s[i];i++){
 28         int x=s[i]-'a';
 29         if(p->next[x]==NULL){
 30             newnode=(struct node*)malloc(sizeof(struct node));
 31             for(int j=0;j<26;j++) newnode->next[j]=0;
 32             newnode->sum=0;
 33             newnode->fail=0;
 34             p->next[x]=newnode;
 35         }
 36         p=p->next[x];
 37     }
 38     p->sum++;
 39 }
 40 
 41 void build_fail()
 42 {
 43     head=0;
 44     tail=1;
 45     q[head]=root;
 46     node *p;node *temp;
 47     while(head<tail){
 48         temp=q[head++];
 49         for(int i=0;i<26;i++){
 50             if(temp->next[i]){
 51                 if(temp==root){
 52                     temp->next[i]->fail=root;
 53                 }
 54                 else{
 55                     p=temp->fail;
 56                     while(p){
 57                         if(p->next[i]){
 58                             temp->next[i]->fail=p->next[i];
 59                             break;
 60                         }
 61                         p=p->fail;
 62                     }
 63                     if(!p) temp->next[i]->fail=root;
 64                 }
 65                 q[tail++]=temp->next[i];
 66             }
 67         }
 68     }
 69 }
 70 
 71 void ac_chicken(char *ch)
 72 {
 73     node *p=root;
 74     int len=strlen(ch);
 75     for(int i=0;i<len;i++){
 76         int x=ch[i]-'a';
 77         while(!p->next[x]&&p!=root) p=p->fail;  //找到这个字母
 78         p=p->next[x];   //p到这个节点
 79         if(!p) p=root;  //没有的话就是根节点
 80         node *temp=p;
 81         while(temp!=root){
 82             if(temp->sum){
 83                cnt+=temp->sum;
 84                temp->sum=0;
 85             }
 86             else break;
 87             temp=temp->fail;
 88         }
 89     }
 90 }
 91 
 92 int main()
 93 {
 94     int t,n;
 95     scanf("%d",&t);
 96     while(t--){
 97         root=(struct node*)malloc(sizeof(struct node));
 98         for(int i=0;i<26;i++) root->next[i]=0;
 99         root->fail=0;
100         root->sum=0;
101         cnt=0;
102         scanf("%d",&n);
103         for(int i=0;i<n;i++){
104             scanf("%s",key);
105             insert(key);
106         }
107         build_fail();
108         scanf("%s",pattern);
109         ac_chicken(pattern);
110         printf("%d\n",cnt);
111     }
112     return 0;
113 }

数组版（一定记得初始化！！不初始化会mle 鬼知道为什么-_-!!）

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<string.h>
 4 #include<queue>
 5 using namespace std;
 6 
 7 const int maxn=1e6+10;
 8 int n,cnt=1;
 9 int tree[maxn][26],color[maxn],fail[maxn];
10 char pattern[2*maxn];
11 char key[100];
12 queue<int> q;
13 
14 void init()
15 {
16     memset(tree,0,sizeof(tree));
17     memset(color,0,sizeof(color));
18     memset(fail,0,sizeof(fail));
19     memset(key,0,sizeof(key));
20     memset(pattern,0,sizeof(pattern));
21     cnt=1;
22     while(!q.empty()) q.pop();
23 }
24 
25 void insert(char *s)
26 {
27     int u=1,len=strlen(s);
28     for(int i=0;i<len;i++){
29         int v=s[i]-'a';
30         if(!tree[u][v]) tree[u][v]=++cnt;
31         u=tree[u][v];
32     }
33     color[u]++;
34 }
35 
36 void build_fail()
37 {
38     for(int i=0;i<26;i++) tree[0][i]=1;  //一个非常重要的细节处理，我们加一个虚拟节点0，并将它的所有边都连到1，方便以后的运算
39     q.push(1);      //将根压入队列
40     fail[1]=0;
41     while(!q.empty()){
42         int u=q.front();
43         q.pop();
44         for(int i=0;i<26;i++){   //遍历所有儿子
45             if(!tree[u][i]){               //不存在该节点
46                 tree[u][i]=tree[fail[u]][i];
47                 continue;
48             }
49             fail[tree[u][i]]=tree[fail[u]][i];
50             q.push(tree[u][i]);   //存在实节点才压入队列
51         }
52     }
53 }
54 
55 int ac_chicken(char *ch)
56 {
57     int u=1,ans=0,len=strlen(ch);
58     for(int i=0;i<len;i++){
59         int v=ch[i]-'a';
60         int k=tree[u][v];
61         while(k>1&&color[k]){
62             ans+=color[k];
63             color[k]=0;
64             k=fail[k];
65         }
66         u=tree[u][v];
67     }
68     return ans;
69 }
70 
71 int main()
72 {
73     int t;
74     scanf("%d",&t);
75     while(t--){
76         init();
77         scanf("%d",&n);
78         for(int i=0;i<n;i++){
79             scanf("%s",pattern);
80             insert(pattern);
81         }
82         build_fail();
83         scanf("%s",key);
84         printf("%d\n",ac_chicken(key));
85     }
86     return 0;
87 }