上一篇的姊妹篇
没啥好说的 套模板
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 50010
#define M 2000010
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
const int child_num = ;
int o[];
char s[M],vir[][];
bool f[M];
class ACAutomo
{
private:
int ch[N][child_num];
int val[N];
int fail[N];
int Q[N];
int id[];
int sz;
public:
void init()
{
fail[] = ;
for(int i = ; i < child_num ; i++)
id[i] = i;
}
void reset()
{
memset(ch[],,sizeof(ch[]));
sz = ;
}
void insert(char *a,int key)
{
int p = ;
for( ; *a ; a++)
{
int d = id[*a];
if(ch[p][d]==)
{
memset(ch[sz],,sizeof(ch[sz]));
val[p] = ;
ch[p][d] = sz++;
}
p = ch[p][d];
}
val[p]=key;
}
void construct()
{
int i,head=,tail = ;
for(i = ;i < child_num ; i++)
{
if(ch[][i])
{
Q[tail++] = ch[][i];
fail[ch[][i]] = ;
}
}
while(head!=tail)
{
int u = Q[head++];
for(i = ; i < child_num ; i++)
{
if(ch[u][i])
{
Q[tail++] = ch[u][i];
fail[ch[u][i]] = ch[fail[u]][i];
}
else
ch[u][i] = ch[fail[u]][i];
}
}
}
void work(char *s)
{
int i,k = strlen(s);
int p = ;
for(i = ;i < k ; i++)
{
int d = id[s[i]];
p = ch[p][d];
int tmp = p;
while(tmp!=&&val[tmp]!=)
{
o[val[tmp]]++;
tmp = fail[tmp];
}
}
}
}ac;
int main()
{
int n,i;
ac.init();
while(scanf("%d%*c",&n)!=EOF)
{
memset(o,,sizeof(o));
ac.reset();
for(i = ; i <= n; i++)
{
gets(vir[i]);
ac.insert(vir[i],i);
}
ac.construct();
gets(s);
ac.work(s);
for(i = ; i <= n ;i++)
if(o[i])
printf("%s: %d\n",vir[i],o[i]);
}
return ;
}