摘抄、修改课件：
- AC自动机就是在Trie上进行类似KMP的过程，可以进行多模板匹配
1.如何得到多个匹配模板的fail函数？(建立AC自动机)
KMP是从左到右进行，那么在Trie上进行时，需要从根结点开始按BFS的顺序进行。
BFS到一个节点时，求它的孩子的fail函数
求x->ch[i]->fail时，先令now=x->fail。
若存在now->ch[i]，就使
x->ch[i]->fail = now->ch[i]
否则令now=now->fail，继续这个过程。
如果now=root后仍不存在now->ch[i]，
就使x->ch[i]->fail = root- 2.如何匹配一段文本？
初始在root，依次枚举B中每一个字符。
假设现在在now，当前字符为c。
若存在now->ch[c]，到达now->ch[c]。
否则令now=now->fail，继续这个过程。
如果now=root后仍不存在now->ch[c]，就停留在root点。- AC自动机中，fail指针仍然会形成一个树结构，称之为fail树。(要将指向翻转)
Fail树的一个性质是，某个结点所对应的字符串肯定是其后代结点所对应的字符串的后缀。
- 也就是说，B的前i个字符在AC自动机上跑完之后，如果到达点x，不仅x对应的字符串是B[1,i]的一个后缀，所有x在fail树中的祖先结点对应的字符串都是B[1,i]的一个后缀。
- 3.如何求A在B中出现了多少次?
如果B的前i个字符在AC自动机中跑完之后到达点x，A对应的点是y。那么只要在fail树中y是x的祖先(x失配会向y方向走)结点，A就是B[1,i]的后缀。
B在AC自动机中每跑完一个字符，都在当前点上记录访问次数+1。
A的对应点y在fail树中的子树中所有结点的访问次数之和就是A在B中出现的次数。
- 4.一个小优化：(链接)
- 我们可以看出，fail是用来寻找失配时走到的位置的，走一个点fail的他的ch[i]一定是没有的。那么我们为什么不用这些ch指针直接指向它的fail的ch[i]呢，可以发现这样操作之后，每个点的ch[i]直接指向了原本沿着失配边不停走的最终结果，这样的话，匹配时每次用ch指针的对象即可，不用一直沿fail边走看看这个点有没有ch[i]了。这个被称作Trie图。
- 更简洁的说，t[u].ch[i] 就是从节点u走ch[i]应该到的位置
hdu2222 统计模式串在文本串中出现总次数，相同的算一个，处理到文本的前i个字符时，把当前位置fail树到根的路径上的节点的单词个数(都是B[1,i]的后缀)全部统计，同时置vis[i]=1(防止下一次重复统计，同时节省时间)
不加优化 402ms
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e6+,M=5e5+;
int n;
struct node{
int ch[],f,val;
}t[M];
int root,sz;
char s[N];
void ins(char s[]){
int u=root,n=strlen(s+);
for(int i=;i<=n;i++){
int c=s[i]-'a';
if(!t[u].ch[c]) t[u].ch[c]=++sz;
u=t[u].ch[c];
}
t[u].val++;
}
int q[N],head=,tail=;
void getAC(){
head=tail=;
q[tail++]=root;
while(head!=tail){
int u=q[head++];
for(int i=;i<;i++){
int v=t[u].ch[i];
if(v){
if(u==root) t[v].f=root;
else{
int now=t[u].f;
while(now!=root&&!t[now].ch[i]) now=t[now].f;
if(t[now].ch[i]) now=t[now].ch[i];
t[v].f=now;
}
q[tail++]=v;
}
}
}
}
int ans,vis[N];
void AC(char s[]){
int now=root,n=strlen(s+);
for(int i=;i<=n;i++){
int c=s[i]-'a';
while(now!=root&&!t[now].ch[c]) now=t[now].f;
if(t[now].ch[c]){
now=t[now].ch[c];
for(int _=now;_!=root&&!vis[_];_=t[_].f)
ans+=t[_].val,vis[_]=;
}
}
}
void init(){
memset(t,,sizeof(t));
memset(vis,,sizeof(vis));
root=sz=ans=;
}
int main(){
//freopen("in.txt","r",stdin);
int T; scanf("%d",&T);
while(T--){
scanf("%d",&n);
init();
for(int i=;i<=n;i++) scanf("%s",s+),ins(s);
getAC();
scanf("%s",s+);
AC(s);
printf("%d\n",ans);
}
}
加优化 343ms
注意getAC()通过把root的所有有的孩子加入队列减少了一种边界讨论(即因为t[0].fail=0造成的那个)，因为root的孩子的fail就是0（root）
注意引用v
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e6+,M=5e5+;
int n;
struct node{
int ch[],f,val;
}t[M];
int sz;
char s[N];
void ins(char s[]){
int u=,n=strlen(s+);
for(int i=;i<=n;i++){
int c=s[i]-'a';
if(!t[u].ch[c]) t[u].ch[c]=++sz;
u=t[u].ch[c];
}
t[u].val++;
}
int q[N],head=,tail=;
void getAC(){
head=tail=;
for(int i=;i<;i++)
if(t[].ch[i]) q[tail++]=t[].ch[i];
while(head!=tail){
int u=q[head++];
for(int i=;i<;i++){
int &v=t[u].ch[i];
if(!v) {v=t[t[u].f].ch[i];continue;}//meiyou ch,zhijie tiaodao fail
t[v].f=t[t[u].f].ch[i];
q[tail++]=v;
}
}
}
int ans,vis[N];
void AC(char s[]){
int now=,n=strlen(s+);
for(int i=;i<=n;i++){
int c=s[i]-'a';
now=t[now].ch[c];
for(int _=now;_!=&&!vis[_];_=t[_].f)
ans+=t[_].val,vis[_]=;
}
}
void init(){
memset(t,,sizeof(t));
memset(vis,,sizeof(vis));
sz=ans=;
}
int main(){
//freopen("in.txt","r",stdin);
int T; scanf("%d",&T);
while(T--){
scanf("%d",&n);
init();
for(int i=;i<=n;i++) scanf("%s",s+),ins(s);
getAC();
scanf("%s",s+);
AC(s);
printf("%d\n",ans);
}
}