前一篇文章已经比较详细地说过fail树的应用了。

这里从一道题目（BZOJ 3881）来更深地谈fail树的应用。

首先看题目：

Alice和Bob在玩游戏，Alice有一个字符串集合S包含n个字符串，Bob往它的集合里添加字符串，并间歇询问：当前S集合的第i个字符串被T中的几个串包含？

$n, q \leq 10^5, all~in~S \leq 10^6, all~in~T \leq 10^6$

第一遍看题，需要注意的是，本题与BZOJ2434阿狸的打字机不同，是统计匹配的个数，而不是匹配的次数！

如果是匹配次数的话，我们处理出来每条链到哪里，然后加起来就行了。

但是统计个数呢？考虑同样处理出每条链到哪里，然后呢？

求树链的并！

那怎么办呢？树链剖分？No！DFS序！

上篇文章说过，DFS序+fail树是常见的方法。那么本题考虑采用DFS序，然后呢？

我们把每个点找出来，然后单点加即可。

那么重复的呢？按照DFS序的进入顺序排个序，然后呢？每两个找LCA，LCA处-1即可。

这里找LCA要用RMQ方法（zkw线段树），其他会TLE。

（P.S. 这里的zkw线段树是从wyfcyx那里copy的，有空学学）

就是用一种类似于虚树的方法来解决问题。

如果是求答案，只要输出[in[x],out[x]]内的和即可。

代码很长……用namespace来结构化。

# include <queue>
# 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 = 2000010;
const int N = 27;

// ==== Graph ==== //
# define next NEXT
int head[M<<1], next[M<<2], to[M<<2];
int in[M], out[M], dep[M], tDFN=0, 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) {
//	printf("add edge: u, v %d %d\n", u, v);
	add(u, v); add(v, u);
}
inline void dfs(int x, int fa) {
	in[x] = ++tDFN;
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fa) continue;
		dep[to[i]] = dep[x]+1;
		dfs(to[i], x);
	}
	out[x] = tDFN;
}
// ==== ACAuto ==== //
int n, sz=0;
char str[M];
int ch[M][N], fail[M];
queue<int> q;
int ACend[M];

inline void ACbuild() {
	scanf("%d", &n);
	for (int i=1; i<=n; ++i) {
		scanf("%s", str);
		int p = 0;
		for (int j=0; str[j]; ++j) {
			int c = str[j]-'a';
			if(!ch[p][c]) ch[p][c]=++sz;
			p=ch[p][c];
		}
		ACend[i] = p;
	}
	for (int c=0; c<26; ++c)
		if(ch[0][c]) q.push(ch[0][c]);
	while(!q.empty()) {
		int top=q.front(); q.pop();
		for (int c=0; c<26; ++c) {
			if(!ch[top][c]) ch[top][c] = ch[fail[top]][c];
			else q.push(ch[top][c]), fail[ch[top][c]] = ch[fail[top]][c];
		}
	}
//	printf("sz = %d\n", sz);
	for (int i=1; i<=sz; ++i) adde(i, fail[i]);
	dep[0] = 1;
	dfs(0, -1);
}
// ==== LCA ==== //
namespace LCA {
	int seq[M<<1], pos[M], a[M<<2], Max, DFN=0;
	inline void build(int x, int fa) {
		pos[x] = ++DFN;
		seq[DFN] = x;
		for (int i=head[x]; i; i=next[i]) {
			if(to[i] == fa) continue;
			build(to[i], x);
			seq[++DFN] = x;
		}
	}
	inline int Min(int x, int y) {
		if(x == -1 || y == -1) return x == -1 ? y : x;
		return dep[x]<dep[y]?x:y;
	}
	inline int ask(int tl, int tr) {
		int ret = -1;
		for (tl+=Max-1, tr+=Max+1; tl^tr^1; tl>>=1, tr>>=1) {
			if(~tl&1) ret = Min(ret, a[tl^1]);
			if(tr&1) ret = Min(ret, a[tr^1]);
		}
		return ret;
	}
	inline void init() {
		build(0, -1);
		for (Max=1; Max<=DFN+1; Max<<=1);
		memset(a, -1, sizeof(a));
		for (int i=1; i<=DFN; ++i) a[Max+i] = seq[i];
		for (int i=Max-1; i>=1; --i) a[i] = Min(a[i<<1], a[i<<1|1]);
	}
	inline int lca(int x, int y) {
		x=pos[x], y=pos[y];
		if(x>y) swap(x, y);
		return ask(x, y); 
	}
}

namespace BIT {
	int c[M];
	inline int lb(int x) {
		return x&(-x);
	}
	inline void init() {
		memset(c, 0, sizeof(c));
	}
	inline void change(int x, int d) {
		for (; x<=sz+1; x+=lb(x)) c[x]+=d;
	}
	inline int ask(int x) {
		int ret=0;
		for (; x; x-=lb(x)) ret+=c[x];
		return ret;
	}
	inline int ask(int l, int r) {
		return ask(r)-ask(l-1);
	}
}

int s[M], sn=0;
inline int cmp(int x, int y) {
	return in[x]<in[y];
}

int main() {
	ACbuild();
	LCA::init();
	BIT::init();
	int T; scanf("%d", &T);
	while(T--) {
		int opt; scanf("%d", &opt);
		if(opt==1) {
			scanf("%s", str);
			int p=0; sn=0;
			for (int j=0; str[j]; ++j) {
				int c=str[j]-'a';
				while(p && !ch[p][c]) p = fail[p];
				p=ch[p][c];
				if(p) s[++sn]=p;
			}
			sort(s+1, s+sn+1, cmp);
			for (int i=1; i<=sn; ++i) BIT::change(in[s[i]], 1);
			for (int i=1; i<sn; ++i) BIT::change(in[LCA::lca(s[i], s[i+1])], -1);	
		} else {
			int x; scanf("%d", &x);
			printf("%d\n", BIT::ask(in[ACend[x]], out[ACend[x]]));
		}
	}
	
	return 0;
}

那么从这题我们能得出什么启示呢？

仔细阅读题目，然后得出结论（要在fail树上干什么）

然后习惯性联想DFS序寻找解决办法。

适当运用数据结构简化复杂度。

哦本题复杂度忘记分析啦！

令$all~in~S=|S|, all~in~T=|T|$，复杂度即为$O(|S|log|S|+|T|log|T|)$