问题描述
有一个有趣的定理：无限猴子定理（infinite monkey theorem），它的表述如下：让一只猴子在打字机上随机按键，当按键次数达到无穷时，几乎必然能够打出任何给定的文字。 给出一篇猴子打出的“文章”，并给定一个由若干个词组成的词典，问猴子一共打出了多少个在词典中出现的词。 输入格式 第一行一个整数 n(1≤n≤10000)，表示词典中单词的个数。 接下来 n 行，每行一个仅由小写字母组成的单词，长度不超过 50。 最后一行是一篇仅由小写字母组成的文章，长度不超过 1000000。 输出格式 一行一个整数，表示答案。 样例输入 5 jsk jisuan suantou love program jisuantouisprogramming 样例输出 3
AC代码
#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 1000005
#define maxm 1000005
using namespace std;
int n,tot,head,tail,son[maxm][
26],fai[maxm],sum[maxm],
list[maxm];
char s[maxn];
void clear(){
tot=
0;
memset(son,
0,
sizeof(son));
memset(sum,
0,
sizeof(sum));
}
void insert(
char *s){
int p=
0;
for (
int i=
1;s[i];p=son[p][s[i]-
'a'],i++)
if (!son[p][s[i]-
'a']) son[p][s[i]-
'a']=++tot;
sum[p]++;
}
void failed(){
head=
0,tail=
1,
list[
1]=
0,fai[
0]=-
1;
while (head!=tail){
int x=
list[++head];
for (
int ch=
0;ch<
26;ch++)
if (son[x][ch]){
list[++tail]=son[x][ch];
int p=fai[x];
while (p!=-
1&&!son[p][ch]) p=fai[p];
if (p==-
1) fai[son[x][ch]]=
0;
else fai[son[x][ch]]=son[p][ch];
}
}
}
void work(
char *s){
int ans=
0;
for (
int i=
1,p=
0;s[i];i++){
while (p&&!son[p][s[i]-
'a']) p=fai[p];
p=son[p][s[i]-
'a'];
for (
int t=p;t;t=fai[t]) ans+=sum[t],sum[t]=
0;
}
printf(
"%d\n",ans);
}
int main()
{
cin>>n;
for (
int i=
1;i<=n;i++)
scanf(
"%s",s+
1),insert(s);
failed();
scanf(
"%s",s+
1),work(s);
return 0;
}
