复杂度：
查找O(n)，维护O(n)
概要：
应用了kmp的自匹配思想，在trie建图时维护一个fali指针，指向上一个匹配的点，这点是用bfs做到。匹配串的时候同样没匹配到就和kmp一样返回。
应用：单串匹配多模板，维护多模板里边的信息。
技巧及注意：
插入和trie一样，然后是bfs。
在bfs的过程中，注意以根开头的不需要匹配fail，即ch[0][i]不需要匹配他们的fail，即为空。
然后在查找的时候当找到一个时我们要遍历这个节点的整个fail树，然后取出信息后记得将信息清空。
一定要注意！节点数是不超过n个串的总长度！！！一定要切记！！！
注意！！bfs的时候一定要维护信息！！！！
例题：
- 【BZOJ】1030: [JSOI2007]文本生成器（递推+ac自动机）（将自动机的节点作为转移的状态然后递推）
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << #x << " = " << x << endl
#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; }
using namespace std;
const int N=10000000, Type=26;
int T[N][Type], w[N], fail[N], cnt, q[N], front, tail, ans;
char str[1000000], st[1000000];
inline void ins(char s[]) {
int len=strlen(s), now=0;
rep(i, len) {
int t=s[i]-'a';
if(!T[now][t]) T[now][t]=++cnt;
now=T[now][t];
}
++w[now];
}
void bfs() {
int now=0;
q[tail++]=0;
while(tail!=front) {
now=q[front++]; if(front==N) front=0;
rep(i, 26) if(T[now][i]) {
q[tail++]=T[now][i]; if(tail==N) tail=0;
if(now==0) continue;
int p=fail[now];
while(p && !T[p][i]) p=fail[p];
fail[T[now][i]]=T[p][i];
}
}
}
void ac(char s[]) {
int len=strlen(s), now=0;
rep(i, len) {
int t=s[i]-'a';
while(now && !T[now][t]) now=fail[now];
now=T[now][t];
t=now;
while(t) {
ans+=w[t];
w[t]=0;
t=fail[t];
}
}
}
int main() {
scanf("%s", str);
int n=getint();
while(n--) {
scanf("%s", st);
ins(st);
}
bfs();
ac(str);
print(ans);
return 0;
}
没错，就是AC自动机！（可惜不像金坷垃那样～）
不多说，放上模板，不难理解的。
#include <cstdio>
#include <cstring>
#include <queue>
#define for1(i,a,n) for(i=a;i<=n;++i)
#define for2(i,a,n) for(i=a;i<n;++i)
#define for3(i,a,n) for(i=n;i>=a;--i)
#define for4(i,a,n) for(i=n;i>a;--i)
#define CC(i,a) memset(i, a, sizeof(i))
using namespace std;
const int N=10000000, Type=26;
char a[N], b[N];
int ch[N][Type], fail[N], w[N], ans, cnt=1;
queue<int> q;
void ins(char* s) {
int u=0, v, i, len=strlen(s);
for2(i, 0, len) {
v=s[i]-'a';
if(!ch[u][v]) ch[u][v]=cnt++;
u=ch[u][v];
}
w[u]++;
}
void bfs() {
fail[0]=0;
q.push(0);
int u, p, i;
while(!q.empty()) {
u=q.front(); q.pop();
for2(i, 0, Type) if(ch[u][i]) {
q.push(ch[u][i]); //先插入，后判断
if(!u) continue; //不要在这里错了。。
p=fail[u];
while(p && !ch[p][i]) p=fail[p];
fail[ch[u][i]]=ch[p][i];
}
}
}
void ac(char* s) {
int i, u=0, v, len=strlen(s), t;
for2(i, 0, len) {
v=s[i]-'a';
while(u && !ch[u][v]) u=fail[u];
u=ch[u][v];
t=u;
while(t) {
ans+=w[t];
w[t]=0;
t=fail[t];
}
}
}
void init() {
CC(fail, 0);
CC(ch, 0);
CC(w, 0);
}
int main() {
init();
scanf("%s", a);
int n, i;
scanf("%d", &n);
for1(i, 1, n) {
scanf("%s", b);
ins(b);
}
bfs();
ac(a);
printf("%d
", ans);
return 0;
}
注意一些细节即可