AC来自一个大佬的名字，并不是写了就可以自动AC的意思 XD
AC自动机是建立在trie树上的一种优化手段。trie在每次查询一个字符串时，如果在一个子树查不到就会回溯再查，效率会很低。我们考虑在给每个节点加一个如果查不到就跳转的指针fail，那么如果找不到的话直接跳转到fail就可以了。fail代表的是拥有该点的最大后缀的点的位置。
那么怎么寻找这个fail呢？因为我们要寻找最大后缀，深度就是一个比较重要的条件。于是我们bfs。注意了，设一个点now,tmp为now的子节点（从a到z任何一个），有以下推导：
（第一段使用结构体存储了点，第二段是用数组）
e[tmp].fail=e[e[now].fail].nxt[i];
fail[tmp]=ch[fail[now]][i];
首先我们知道trie是有一个0节点的。那么0连接的所有点的fail就连接的是0。如果我们接下来遍历每个点，对于任何点的fail都是其父节点的fail的子字符。因为是bfs，所以这样做一定是正确的而且一定会找到其最长后缀的点。
这里注意一下：如果now点有该字符是按照上面记录的。如果没有（ch[now][i]==0）就需要转移记录一下nxt：
e[now].nxt[i]=e[e[now].fail].nxt[i];
ch[now][i]=ch[fail[now]][i];
这样的话我们查询的时候只需要令now不断等于当前点的nxt就可以快速遍历啦~如果遍历到0，说明就end了。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define register R using namespace std; namespace ysr { inline int read() { int w=0,x=0;char c=getchar(); while(!isdigit(c))w|=c==‘-‘,c=getchar(); while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar(); return w?-x:x; } const int maxn=2333; int cnt=0; int n; char s[1000010]; struct tree{ int nxt[26],fail,cnt; bool vis; void init() { memset(nxt,0,sizeof nxt); fail=cnt=0; vis=0; } }e[maxn]; inline int get(char c) { return c-‘a‘; } inline void insert(char *s) { int now,tmp,t; for(now=0;*s;s++) { t=get(*s); if(!e[now].nxt[t]) { e[++cnt].init(); e[now].nxt[t]=cnt; } now=e[now].nxt[t]; } e[now].cnt++; } int ans=0; inline void match(char *s) { int now,tmp; for(now=0;*s;s++) { int t=get(*s); now=e[now].nxt[t]; for(tmp=now;tmp and !e[tmp].vis;tmp=e[tmp].fail){ ans+=e[tmp].cnt; e[tmp].vis=1; } } } inline void build() { int now=0; queue<int>q; while(!q.empty()) { int t=q.front();q.pop(); for(int i=0;i<26;i++) { if(e[now].nxt[i]){ int tmp=e[now].nxt[i]; if(now) e[tmp].fail=e[e[now].fail].nxt[i]; q.push(tmp); }else e[now].nxt[i]=e[e[now].fail].nxt[i]; } } } inline void work() { n=read(); e[0].init(); while(n--) { scanf("%s",s); insert(s); } scanf("%s",s); match(s); printf("%d\n",ans); } } int main() { ysr::work(); return 0; }
原文：https://www.cnblogs.com/BrotherHood/p/13296309.html