AcWing 2811. 最长公共子串（后缀自动机 fa 指针的性质）

题意：

给定 n 行字符串，求出所有字符串的 最长公共子串。

思路：

先想想如果是 两个串 的话，如何解决这个问题？

现在我们有 A、B 两个串，我们 先把 A 串建成后缀自动机（相当于 将 A 的所有子串 都扔进一个 哈希表 中，即 快速查询 A 的每个子串），

想想 暴力 怎么做：

• 枚举 B 串中每个子串的起点 i，从 起点 i 开始 往后走，边走边 在后缀自动机 A 中查询，直到走到 某一个位置 发现 “加上一个字符之后，A 的自动机中不存在该串”，就说明此时我们找到了一个 以 i 为起点，长度最大的一个公共子串，停下来即可。这样一来，我们就枚举了 其中一个起点。之后我们 将起点往后挪动一位，再 往后 进行 枚举，以此类推，这样的算法是一定可以将 所有的情况（任意起点在 A 中出现的最长子串）枚举到的。最后，对于每个起点求出来的最长子串长度取 max，即为答案。

现在考虑如何 优化这个算法，这就要用到 SAM 的性质 了，

• 当我们在 SAM 中走到 状态 p（节点），我们知道 节点 p 是具有一些子串（后缀）的，且都是 连续的，且为 最长子串的后缀。p 之后不存在一个字符，意味着 其包含的所有子串后方都不能接新的字符。此时，我们试着 将起点往后挪一位，但这样可能还是会在 SAM 中走到 p 节点，且 没有新的出边（此时 得到的新的公共子串长度还没有上一轮得到的长度更长，且属于 p 节点代表的同类子串集合）。思考一下，起点 挪动到什么时候才会有 质变 呢？可以想到，当 起点 为 p 节点代表子串集合中最短串首字符时，将起点 往后挪一位，这时才会有 质变，即 走到 p 时有了新的出边，也就是可能将 答案更新，相当于 将 p 代表子串集合中最短串首位删除，删除之后的状态我们应该很熟悉了，其实就是 p 用绿色链接边连向的节点。
• 总结一下：优化之处 在于，可以直接 将起点跳转至 p 绿色链接边连向的点 p' = fa[p]，如果 跳转至 p' 之后 后方还是 没有出边，那么 继续跳转至 fa[p'] 即可，显然这个过程时会 结束 的（跳转至 有出边的节点 或 空字符串），这样一来我们就 省去了挨个暴力枚举，起到了将时间复杂度优化的效果（优化成了 O(n)），这一连串的 匹配过程 和 KMP 有惊人的相似之处。

考虑如何 将答案记录，

• 显然可以 在 SAM 中的每个状态 p 中都记录一个最大值 now[p]，表示 当前在 B 和 状态 p 中都出现过的最长子串长度，由于 A 的子串必然被划分到了每一个状态 p 中，那么，对于 每个状态的 now[p] 联合起来取最大值，就可以 将 A 的所有子串的遍历一遍，即求出 A 的所有子串中，哪一个子串 是 在 B 中出现过 且 长度最长 的。

至此，对于 两串求最长公共子串的做法 已经分析完毕，现在想想对于 n 个字符串 该如何处理？

• 先将 第 1 个串 建成 SAM，之后对于 第 2 个串 进行一遍刚刚分析的操作，这样一来，对于 每一个状态 p，都可以 求出其 now2[p]，当求 第 3 个串 时，我们可以求出 所有 now3[p]，当求 第 n 个串 时我们可以求出 nown[p]，对于 状态 p 的最长公共子串 我们取的应为 ans_p = min(now1[p], now2[p], ..., nown[p])，而对于 最终答案（n 个串 的 最长公共子串），我们是 以状态 p 为变量，取 ans = max(ans_p1, ans_p2, ..., ans_pm)。

代码：

#include <bits/stdc++.h>

using namespace std;
//#define map unordered_map
//#define int long long
const int N = 1e4 + 10, M = N << 1;
char s[N];
int fa[M], ch[M][26], len[M], cnt[M];
int tot = 1, np = 1;
int n;
int h[M], e[M], ne[M], idx;
int now[M], ans[M];

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u) {
	for (int i = h[u]; ~i; i = ne[i]) {
		int j = e[i];
		dfs(j);
		now[u] = max(now[u], now[j]);
	}
}

void extend(int c) {
	int p = np; 
	np = ++tot;
	len[np] = len[p] + 1, cnt[np] = 1;
	while (p && !ch[p][c]) {
		ch[p][c] = np;
		p = fa[p];
	}
	if (!p) {
		fa[np] = 1;
	}
	else {
		int q = ch[p][c];
		if (len[q] == len[p] + 1) {
			fa[np] = q;
		}
		else {
			int nq = ++tot;
			len[nq] = len[p] + 1;
			fa[nq] = fa[q], fa[q] = fa[np] = nq;
			while (p && ch[p][c] == q) {
				ch[p][c] = nq;
				p = fa[p];
			}
			memcpy(ch[nq], ch[q], sizeof ch[q]);
		}
	}
}

signed main()
{
	cin >> n;
	cin >> s;
	for (int i = 0; s[i]; ++i) {
		extend(s[i] - 'a');
	}
	for (int i = 1; i <= tot; ++i){
	    ans[i] = len[i];
	}
	memset(h, -1, sizeof h);
	for (int i = 2; i <= tot; ++i) {
		add(fa[i], i);
	}
	for (int i = 0; i < n - 1; ++i) {
		cin >> s;
		memset(now, 0, sizeof now); //每次存的是 当前枚举到的串 与 A串 匹配时，所有在p状态上的答案情况，所以得清0
		int p = 1, t = 0;   //从起点p=1开始，t为当前长度
		for (int j = 0; s[j]; ++j) {
			while (p > 1 && !ch[p][s[j] - 'a']) {    //当p不是头结点，且p没有c这个儿子
			  //p往后挪 t取跳转到的状态的最长值
				p = fa[p];
				t = len[p];
			}
			if (ch[p][s[j] - 'a']) p = ch[p][s[j] - 'a'], ++t;    //如果p有c这条边，那么跳过去，当前长度+1
			now[p] = max(now[p], t);
		}
		dfs(1); //处理特殊情况，需要先自下而上传递标记
		
		//当前串求完所有now后，枚举所有状态ans存储所有状态最小值
		for(int i=1; i<=tot; ++i){
			ans[i] = min(ans[i], now[i]);
		}
	}
	int res = -1;
	for (int i = 1; i <= tot; ++i) {
		res = max(res, ans[i]);
	}
	printf("%d\n", res);

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96