题目：戳这里
题意：输出主串中出现的模式串以及该模式串出现的次数。
思路：ac自动机，匹配的时候对应的vis[]+1即可
代码：
#include<stdio.h>View Code
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
const int maxw = 26;
const int maxn = 55;
const int time = 1010;
const int maxs = 2000005;
struct Tire
{
int tire[maxn*time][maxw];
int fail[maxn*time];
int tag[maxn*time];
int vis[time];
int P, root;
int New()
{
for(int i=0; i<maxw; i++) tire[P][i]=-1;
tag[P]=0;
return P++;
}
void init()
{
P=0;
root =New();
}
void Insert(char ch[], int id)
{
int now = root;
for(int i=0; ch[i]; i++)
{
if(tire[now][ch[i]-'A']==-1) tire[now][ch[i]-'A'] = New();
now = tire[now][ch[i]-'A'];
}
tag[now] = id;
}
void build()
{
queue<int>Q;
for(int i=0; i<maxw; i++)
{
if(tire[root][i]!=-1)
{
fail[tire[root][i]] = root;
Q.push(tire[root][i]);
}
else tire[root][i] = root;
}
while(!Q.empty())
{
int now = Q.front();
Q.pop();
for(int i=0; i<maxw; i++)
{
if(tire[now][i]!=-1)
{
fail[tire[now][i]] = tire[fail[now]][i];
Q.push(tire[now][i]);
}
else tire[now][i] = tire[fail[now]][i];
}
}
}
void match(char ch[])
{
int now = root;
memset(vis,0,sizeof(vis));
for(int i=0; ch[i]; i++)
{
if(ch[i]<'A'||ch[i]>'Z') now = root;
else
{
now = tire[now][ch[i]-'A'];
int tmp = now;
while(tmp!=0)
{
if(tag[tmp]) vis[tag[tmp]]++;
tmp = fail[tmp];
}
}
}
}
};
char ch[time][maxn], def[maxs];
int n;
Tire ac;
int main()
{
while(~scanf("%d",&n))
{
ac.init();
for(int i=1; i<=n; i++)
{
scanf("%s",ch[i]);
ac.Insert(ch[i],i);
}
ac.build();
scanf("%s",def);
ac.match(def);
for(int i=1; i<=n; i++)
{
if(ac.vis[i]!=0)
printf("%s: %d\n",ch[i],ac.vis[i]);
}
}
}