题目链接:https://www.luogu.org/problem/P3808
题意：给n个模式串和一个文本串，求有多少个模式串在文本串中出现过
AC自动机的裸题，AC自动机最难理解的地方在于fail指针，这里借用了博客https://blog.csdn.net/creatorx/article/details/71100840#commentBox以及https://www.cnblogs.com/cjyyb/p/7196308.html的部分讲解
然后这个博客图很多，讲的很清楚：https://www.luogu.org/blog/hicc0305/solution-p3808
fail是失配指针，注意是失配
意味着，如果我此时匹配失败，那么，我们就要到达这个指针指向的位置继续尝试匹配
所以，我们可以将失配指针指向的的节点理解为：
当前节点所代表的串，最长的、能与后缀匹配的，在TrieTrie中出现过的前缀所代表的节点。
所以，fail指针类似于kmp的next数组，只不过由单串变为了多串而已。
举例：插入abcd, bce, abd, cd，构建字典树
首先我们让与根节点直接相连的节点的fail直接指向root,为了让你更好的理解fail指针，我们以节点x,y,z为例，我们让从图中我们可以看出x节点的fail指向了y节点，y节点的fail指向了z节点，为什么会这样指，因为x节点表示字符串abc,而字典树中含有最长，且以c结尾，且是abc的后缀的字符串bc(以y节点结尾的），同理，以y节点表示的字符串是bc,而以c结尾，且是bc的后缀的最长字符串是c（以z节点结尾的）。这就是fail指针指向的目标，那么我们得到了这个fail指针在匹配中有什么用呢，我们还是用上面的那个图来举例说明一下，假设文本串是abce,通过字典树我们可以看出，通过abc,所以我们可以匹配到x节点，但是到后面，我们发现d与e不匹配，这时我们就需要用到当前节点的fail了，因为x的fail指向的是y节点，所以我们直接跳到y节点，这是发现y节点后面有e，匹配上了，所以单词bce就在文本串abce中被检测出来了。当然这只是最简单的一种情况。
这里再解释一下代码中在求fail指针时为什么当前结点不存在就指向当前结点fail指针指向的结点的对应结点处，因为我们在查询有多少个子串的时候是加上所有达到的结点的数目（这个数目是指以这个节点结尾的单词的数目，且只加一次）。当我们遍历文本串时，遍历到了一个不存在的结点，用这种方法就可以直接转向前缀就是当前后缀的字符串了。
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; const int inf=0x3f3f3f3f; typedef long long ll; #define meminf(a) memset(a,0x3f,sizeof(a)) #define mem0(a) memset(a,0,sizeof(a)); struct node{ int fail;//失配指针fail int vis[26];//子节点的位置，也就是字典树的那26个字母 int num;//记录有多少个单词以这个节点结尾 }AC[maxn]; char s[maxn]; int cnt=0;//Trie的指针 void insert(char *s){ int len=strlen(s); int now=0;//字典树的当前指针 for(int i=0;i<len;i++){ //Trie树没有这个子节点 if(AC[now].vis[s[i]-‘a‘]==0) AC[now].vis[s[i]-‘a‘]=++cnt; now=AC[now].vis[s[i]-‘a‘]; } AC[now].num++; } void get_fail(){ queue<int> que; for(int i=0;i<26;i++){//把第二层的fail指针都设为0 if(AC[0].vis[i]!=0) { AC[AC[0].vis[i]].fail=0; que.push(AC[0].vis[i]); } } while(!que.empty()) { int u=que.front();que.pop(); for(int i=0;i<26;i++){ if(AC[u].vis[i]!=0){ //如果当前结点的子节点存在，就将子节点的fail指针指向当前结点fail指针指向的结点的对应子节点处 AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i]; que.push(AC[u].vis[i]); } else AC[u].vis[i]=AC[AC[u].fail].vis[i]; //否则直接将这个不存在的子节点指向当前结点fail指针指向结点的对应子节点处 } } } int AC_query(char* s){ int len=strlen(s); int ans=0,now=0; for(int i=0;i<len;i++){ now=AC[now].vis[s[i]-‘a‘]; for(int t=now;t!=0&&AC[t].num!=-1;t=AC[t].fail){ //能够抵达的结点都将该节点的单词数加上，但记得标记加过一次后就不要再加了 //不加是因为因为这道题并不是统计所有子串出现的总数，而是有多少子串出现了 ans+=AC[t].num; AC[t].num=-1; } } return ans; } int main(){ int n;scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%s",s); insert(s); } AC[0].fail=0;//结束标志 get_fail(); //求出失配指针 scanf("%s",s); printf("%d\n",AC_query(s)); return 0; }
原文：https://www.cnblogs.com/qingjiuling/p/11373907.html