最近学了学fail树，感觉挺傻逼高级的……

原来AC自动机的代码（getfail）长这样

queue<int> q;
inline void getfail() {
	while(!q.empty()) q.pop();
	fail[0] = 0;
	for (int c=0; c<26; ++c) {
		int p = ch[0][c];
		if(p) {
			fail[p] = lst[p] = 0;
			q.push(p);
		}
	}
	while(!q.empty()) {
		int top = q.front(); q.pop();
		for (int c=0; c<26; ++c) {
			int p = ch[top][c];
			if(!p) continue;
			q.push(p);
			int v = fail[top];
			while(v && !ch[v][c]) v = fail[v];
			fail[p] = ch[v][c];
			lst[p] = isend[fail[p]] ? fail[p] : lst[fail[p]];
		}
	}
}

然后我们发现，我们可以在找的过程中把fail顺便赋上去，这样后来也方便。

只要改动2处地方即可QAQ

queue<int> q;
inline void getfail() {
	while(!q.empty()) q.pop();
	fail[0] = 0;
	for (int c=0; c<26; ++c) {
		int p = ch[0][c];
		if(p) {
			fail[p] = lst[p] = 0;
			q.push(p);
		}
	}
	while(!q.empty()) {
		int top = q.front(); q.pop();
		for (int c=0; c<26; ++c) {
			int p = ch[top][c];
			if(!p) {
				ch[top][c]=ch[fail[top]][c];
				continue;
			}
			q.push(p);
			fail[p] = ch[fail[top]][c];
			lst[p] = isend[fail[p]] ? fail[p] : lst[fail[p]];
		}
	}
}

然后呢，我们发现这样会比较快的处理出fail，而且对于dp的时候也更好用（这当然不是本文内容）

其实不说上面这些也是可以的。。。

因为我们发现，一个AC自动机节点的fail节点是其后缀，所以我们考虑把fail节点和当前节点连边这样就形成了一棵树对吧（根节点不要连自环）。那么这棵树叫做fail树。

那么fail树有啥用呢？

是xxx的后缀，而且AC自动机每个节点都表示一个字符串的一部分，那么如果走到了这个点，所有这个点代表的字符串的后缀都被走到啦！这有啥关系？？？fail树是把fail[p]和p连边。所以！就只要区间加法即可！把根到p的路径整体+1即可。那么查询呢？？单点查询啊！什么你说你不会链的加？？？DFS序啊！

所以按照阿杜的说法，常态就是fail树+DFS序+RMQ。当然RMQ可以高级可以低级，有的时候还要LCT。

【例题】bzoj 3172 单词

这题已经被做烂了，我写了三遍了（SA，AC自动机，AC自动机+fail树）。。。

直接在插入的时候区间加即可。然后一遍dfs统计。

# include <stdio.h>
# include <algorithm>
# include <string.h>
# include <queue>
# include <vector>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 1600010;
const int N = 27;
int ch[M][N], fail[M], cnt[M], sz=0, idx[M];
int isend[M];
char t[M];

# define next nxt
int head[M], next[M<<1], to[M<<1], tot=0;

inline void add(int u, int v) {
	++tot; next[tot]=head[u]; head[u]=tot; to[tot]=v;
}

inline void insert(int j) {
	int len = strlen(t), p=0;
	for (int i=0; i<len; ++i) {
		int c = t[i] - 'a';
		if(!ch[p][c]) ch[p][c] = ++sz;
		p = ch[p][c];
		cnt[p] ++;
	}
	isend[p] ++;
	idx[j] = p;
}

queue<int> q;
inline void getfail() {
	while(!q.empty()) q.pop();
	fail[0] = 0;
	for (int c=0; c<26; ++c) {
		int p = ch[0][c];
		if(p) {
			fail[p] = 0;
			add(fail[p], p);
			add(p, fail[p]);
			q.push(p);
		}
	}
	while(!q.empty()) {
		int top = q.front(); q.pop();
		for (int c=0; c<26; ++c) {
			int p = ch[top][c];
			if(!p) {
				ch[top][c] = ch[fail[top]][c];
				continue;
			}
			q.push(p);
			int v = fail[top];
			while(v && !ch[v][c]) v = fail[v];
			fail[p] = ch[v][c];
			add(fail[p], p);
			add(p, fail[p]);
		}
	}
}

inline void dfs(int x, int fa) {
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fa) continue;
		dfs(to[i], x);
		cnt[x] += cnt[to[i]];
	}
}

int n, T;

int main() {
	sz = 0;
	scanf("%d", &n);
	for (int i=1; i<=n; ++i) {
		scanf("%s", t);
		insert(i);
	}
	getfail();
	dfs(0, -1);
	for (int i=1; i<=n; ++i)
		printf("%d\n", cnt[idx[i]]);
	return 0;
}

【附】bzoj 2434 阿狸的打字机

这题多了'B'和'P'，那么怎么办？

'B'相当于回到父节点。'P'打标记就行了（后面处理到询问的时候知道是哪一个标记在哪个节点上）

然后考虑询问x字符串在y字符串里出现的次数。那么我们可以考虑重现操作。

我们再“插入”一遍字符串，然后到'B'或正常字符的时候正常插入即可，并且修改点权（-1/+1）（这样我们就可以省去区间加操作了）。然后等到了y字符串处理完，对于每个y是当前y的询问，回答即可，回答的答案呢？就是x这棵子树的和啦（这应该很好理解吧，因为x子树是x的后缀，也可以包含y）。然后呢，就变成修改点，子树加的题目了！

什么？你不会？按照正常的DFS序+树状数组就行了啊！！！

2A。。模板敲错了一次。

# include <queue>
# include <vector>
# include <stdio.h>
# include <string.h>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 500010;
const int N = 27;

int ch[M][N], fail[M], fa[M], sz=0;
int b[M], bn=0, pos[M];
queue<int> q;
vector< pair<int,int> > v[M];
char str[M];
# define next NEXT
int head[M], next[M], to[M], tot=0;

inline void add(int u, int v) {
	++tot; 
	next[tot]=head[u]; 
	head[u]=tot; 
	to[tot]=v;
}
inline void adde(int u, int v) {
	add(u, v);
	add(v, u);
}

inline void build() {
	scanf("%s", str);
	int p=0;
	for (int i=0; str[i]; ++i) {
		if(str[i] == 'B') p = fa[p];
		else if(str[i] == 'P') {
			b[p] = ++bn;
			pos[bn] = p; 
		} else {
			int c = str[i]-'a';
			if(!ch[p][c]) ch[p][c]=++sz, fa[ch[p][c]] = p;
			p = ch[p][c];
		}
	}
	while(!q.empty()) q.pop();
	fail[0] = 0;
	for (int c=0; c<26; ++c) {
		int p = ch[0][c];
		if(p) fail[p] = 0, q.push(p);
	}
	while(!q.empty()) {
		int top = q.front(); q.pop();
		for (int c=0; c<26; ++c) {
			int p = ch[top][c];
			if(!p) {
				ch[top][c] = ch[fail[top]][c];
				continue;
			}
			q.push(p);
			fail[p] = ch[fail[top]][c];
		}
	}
	for (int i=0; i<=sz; ++i) adde(i, fail[i]);
}

int st[M], ed[M], DFN=0;
inline void dfs(int x, int fa) {
	st[x] = ++DFN;
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fa) continue;
		dfs(to[i], x);
	}
	ed[x] = DFN;
}

int ans[M];

int c[M<<1];
inline int lowbit(int x) {
	return x&(-x);
}
inline void change(int x, int del) {
	for (; x<=DFN; x+=lowbit(x)) c[x]+=del;
}
inline int ask(int x) {
	int ret=0;
	for (; x; x-=lowbit(x)) ret+=c[x];
	return ret;
}
inline int query(int l, int r) {
	return ask(r)-ask(l-1);
}

int main() {
	build(); dfs(0, -1);
	int T; scanf("%d", &T);
	for (int i=1; i<=T; ++i) {
		int a, b; scanf("%d%d", &a, &b);
		v[b].push_back(make_pair(a, i));
	}
	int p=0;
	for (int i=0; str[i]; ++i) {
		if(str[i] == 'P') {
			int ps = b[p];
			for (int j=0, jto=v[ps].size(); j<jto; ++j) 
				ans[v[ps][j].second] = query(st[pos[v[ps][j].first]], ed[pos[v[ps][j].first]]);
		} else if(str[i] == 'B') {
			change(st[p], -1);
			p = fa[p];
		} else {
			int c = str[i] - 'a';
			p = ch[p][c];
			change(st[p], 1);
		}
	}
	for (int i=1; i<=T; ++i) 
		printf("%d\n", ans[i]);

	return 0;
}