这个讲义讲得非常清楚了
https://www.luogu.com.cn/blog/3383669u/qiang-shi-tu-xie-ac-zi-dong-ji
https://blog.csdn.net/weixin_40317006/article/details/81327188
视频讲义：https://www.bilibili.com/video/BV1uJ411Y7Eg/?spm_id_from=333.788.videocard.2
（里面没太讲明白走到某个点，要不断跳FAIL指针的过程，整体还好了）
视频讲义： https://www.bilibili.com/video/BV1gs411t767/?spm_id_from=333.788.videocard.12
给你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])
//u结点下面有一个这样的i字母
//则ch[u][i]这个点的fail指针指向ｕ的ｆail指针下面的ｉ结点（这个结点可能存在，也可能不存在）
//如果不存在的话，则必然是指向从前曾出现过的一个ｉ结点
//如果通篇都没有出现i结点，则指向根结点
fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]);
else
//将父亲点的fail指针所指向的i这个字母点，做为当前点
//如果那个点不存在，则指向0，即根结点
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
",query(s));
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int n,q[1000100],fail[1000100],son[1000100][26],sum[1000100],cnt,ans;
char t[60],s[1000100];
void build(char *t){
int p=0;
for (int i=0;i<strlen(t);i++)
{
int now=t[i]-'a';
if (!son[p][now]) son[p][now]=++cnt;
p=son[p][now];
}
sum[p]++;
}
void getfail(){
int head=1,tail=1,p;
q[head]=0,fail[0]=-1;
while (head<=tail)
{
int now=q[head++];//当前结点,
for (int ch=0;ch<26;ch++)
if (son[now][ch])
//如果now的ch子结点存在的话
{
q[++tail]=son[now][ch];
int p=fail[now];
while (p!=-1 && son[p][ch]==0)
//沿着fail指针一直走，直到找到某个点它下面有ch这个子结点
//注意是可以走到根结点的
p=fail[p];
if (p==-1) //如果根结点下面都没有ch这个子结点，则指向根
fail[son[now][ch]]=0;
else
fail[son[now][ch]]=son[p][ch];
}
}
}
void work(char *s)
{
int p=0;
for (int i=0;i<strlen(s);i++)
{
while (p>0 && !son[p][s[i]-'a'])
//一直走P的FAIL指针，直到找到某个点，它下面有字符串第i个字符
p=fail[p];
p=son[p][s[i]-'a'];
for (int j=p;j;j=fail[j])
ans+=sum[j],sum[j]=0;
}
}
int main(){
// freopen("hustoj2772.in","r",stdin);
// freopen("hustoj2772.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%s",t);
build(t);
}
getfail();
scanf("%s",s);
work(s);
printf("%d",ans);
}