AC自动机（病毒侵袭）

题目链接：https://cn.vjudge.net/contest/280743#problem/B

题目大意：中文题目

具体思路：AC自动机模板题，编号的时候注意，是按照给定的id进行编号的。然后输出的时候注意去重，虽然按道理来讲通过last数组是不会有重复的，但是如果是这种情况，病毒模板aaa,然后给你一个模板串aaaaa,这样的话，就肯定会有重复的了，所以需要去重，其次输出的时候按照升序输出。

AC代码：

  1 #include<iostream>
  2 #include<stack>
  3 #include<stdio.h>
  4 #include<cstring>
  5 #include<string>
  6 #include<cmath>
  7 #include<queue>
  8 #include<algorithm>
  9 using namespace std;
 10 # define ll long long
 11 const int maxn = 2e5+50000;
 12 const int maxm = 1e6+100;
 13 char str1[200+20],str2[10000+100];
 14 int tot,ch[maxn][130],val[maxn];
 15 int fail[maxn],last[maxn],sto[500+10],vis[500+10];
 16 int ans;
 17 void add(int t)
 18 {
 19     int p=0;
 20     int len=strlen(str1);
 21     for(int i=0; i<len; i++)
 22     {
 23         int u=(int)str1[i];
 24         if(!ch[p][u])
 25             ch[p][u]=++tot;
 26         p=ch[p][u];
 27     }
 28     val[p]=t;
 29 }
 30 void getfail()
 31 {
 32     queue<int>q;
 33     for(int i=0; i<130; i++)
 34     {
 35         if(ch[0][i])
 36             q.push(ch[0][i]);
 37     }
 38     while(!q.empty())
 39     {
 40         int top=q.front();
 41         q.pop();
 42         for(int i=0; i<130; i++)
 43         {
 44             int u=ch[top][i];
 45             if(u==0)
 46                 continue;
 47             q.push(u);
 48             int v=fail[top];
 49             while(v&&ch[v][i]==0)
 50                 v=fail[v];
 51             fail[u]=ch[v][i];
 52             last[u]=val[fail[u]] ? fail[u] : last[fail[u]];
 53         }
 54     }
 55 }
 56 void  cal(int t)
 57 {
 58     while(t)
 59     {
 60         if(val[t]&&vis[val[t]]==0)//去重的过程。
 61       sto[++ans]=val[t],vis[val[t]]=1;
 62    //     val[t]=0;// 注意这个地方，不能改成0，因为不只有一个字符串需要去匹配。
 63         t=last[t];
 64     }
 65 }
 66 void getans()
 67 {
 68     int len=strlen(str2);
 69     int p=0;
 70     for(int i=0; i<len; i++)
 71     {
 72         int u=(int)str2[i];
 73         while(p&&ch[p][u]==0)
 74             p=fail[p];
 75         p=ch[p][u];
 76         if(val[p])
 77            cal(p);
 78         else if(fail[p])
 79             cal(fail[p]);
 80     }
 81 }
 82 int main()
 83 {
 84     int n;
 85     scanf("%d",&n);
 86     for(int i=1; i<=n; i++)
 87     {
 88         scanf("%s",str1);
 89         add(i);
 90     }
 91     getfail();
 92     int m;
 93     scanf("%d",&m);
 94     int num=0;
 95     for(int i=1; i<=m; i++)
 96     {
 97         memset(vis,0,sizeof(vis));
 98         ans=0;
 99         scanf("%s",str2);
100         getans();
101         if(ans==0)
102             continue;
103         num++;
104         printf("web %d:",i);
105         sort(sto+1,sto+ans+1);//按照升序输出。
106         for(int j=1; j<=ans; j++)
107         {
108             printf(" %d",sto[j]);
109         }
110         printf("
");
111     }
112     printf("total: %d
",num);
113     return 0;
114 }

AC自动机（病毒侵袭 ）

AC自动机（病毒侵袭）