（AC自动机）C

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

题目大意：中文题

具体思路：首先取ascii码0-130是肯定不行的了，会超时。然后就开始简化，如果是按照0-30来的话，会出现负值，这个时候我们就可以单独对每个合法的子串求符合他的子串。

注意：

1，不能一次把所有合法的子串一起搞，比如这个样例 aa-..aaa，如果把所有合法的搞在一起的话，会变成 aaaaa，这样合法情况就会变多了，所以对每个子串分别求就可以了。

2，每一次截取的时候，我们可以在这个字符串的尾部加上一个 ‘'（字符串结束符），这样的话，就可以按照子串进行了。

AC代码：

  1 #include<iostream>
  2 #include<stack>
  3 #include<stdio.h>
  4 #include<cstring>
  5 #include<string>
  6 #include<map>
  7 #include<cmath>
  8 #include<queue>
  9 #include<algorithm>
 10 using namespace std;
 11 # define ll long long
 12 const int maxn = 5e4+100;
 13 const int maxm = 1e6+100;
 14 char str1[1000+100][55],str2[2000000+100],tmp[2000000+100];
 15 int tot,ch[maxn][30],val[maxn];
 16 int fail[maxn],last[maxn],vis[maxn];
 17 void add(int t)
 18 {
 19     int p=0;
 20     int len=strlen(str1[t]);
 21     for(int i=0; i<len; i++)
 22     {
 23         int u=str1[t][i]-'A';
 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<30; 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<30; 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       vis[val[t]]++;
 61    //     val[t]=0;
 62         t=last[t];
 63     }
 64 }
 65 void getans()
 66 {
 67     int len=strlen(tmp);
 68     int p=0;
 69     for(int i=0; i<len; i++)
 70     {
 71         int u=tmp[i]-'A';
 72         while(p&&ch[p][u]==0)
 73             p=fail[p];
 74         p=ch[p][u];
 75         if(val[p])
 76            cal(p);
 77         else if(fail[p])
 78             cal(fail[p]);
 79     }
 80 }
 81 void init()
 82 {
 83     memset(ch,0,sizeof(ch));
 84     memset(val,0,sizeof(val));
 85     memset(fail,0,sizeof(fail));
 86     memset(last,0,sizeof(last));
 87     memset(vis,0,sizeof(vis));
 88     tot=0;
 89 }
 90 int main()
 91 {
 92     int n;
 93     while(~scanf("%d",&n))
 94     {
 95         init();
 96         for(int i=1; i<=n; i++)
 97         {
 98             scanf("%s",str1[i]);
 99             add(i);
100         }
101         getfail();
102         scanf("%s",str2);
103         int p=0;
104         int len=strlen(str2);
105 
106         for(int i=0; i<=len; i++)//注意这个地方结束条件是等于，这样的话就可以不用讨论最后一个字符串是合法的但是需要特殊对待的。
107         {
108             if(str2[i]>='A'&&str2[i]<='Z')
109             {
110                 tmp[p++]=str2[i];
111             }
112             else
113             {
114                 tmp[p]='';
115                 getans();
116                 p=0;
117             }
118         }
119         for(int i=1; i<=n; i++)
120         {
121             if(vis[i]==0)
122                 continue;
123             printf("%s: %d
",str1[i],vis[i]);
124         }
125     }
126     return 0;
127 }