给你N个单词，然后给定一个字符串，问一共有多少单词在这个字符串中出现过（输入相同的字符串算不同的单词，同一个单词重复出现只计一次）。
Input
第一行一个整数N，表示给定单词的个数。
接下来N行，每行输入一个长度不超过50且全由小写字母组成的单词。
最后一行输入一个长度不超过1000000的字符串。
N≤10000
Output
输出一行包含一个整数，表示共在给定字符串中出现过的单词个数。
Sample Input
5
she
he
say
shr
her
yasherhs
?
Sample Output
3
#include<bits/stdc++.h>
using namespace std;
int ch[500005][26],val[500005],fail[500005],cnt;
int n;
char s[1000005];
void ins(char *s)
{
int len=strlen(s),now=0;
for(int i=0;i<len;i++)
{
if(!ch[now][s[i]-‘a‘])
ch[now][s[i]-‘a‘]=++cnt;
now=ch[now][s[i]-‘a‘];
}
val[now]++;
}
void build()
{
queue<int> q;
for(int i=0;i<26;i++)
if(ch[0][i])
q.push(ch[0][i]);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i<26;i++)
if(ch[u][i])
fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]);
else
ch[u][i]=ch[fail[u]][i];
}
}
int query(char *s)
{
int len=strlen(s),now=0,ans=0;
for(int i=0;i<len;i++)
{
now=ch[now][s[i]-‘a‘];
for(int t=now;t;t=fail[t])
ans+=val[t],val[t]=0;
}
return ans;
}
int main()
{
scanf("%d",&n);
while(n--)scanf("%s",s),ins(s);
build();
scanf("%s",s);
printf("%d\n",query(s));
return 0;
}
原文：https://www.cnblogs.com/cutemush/p/12561982.html