后缀数组

在文本串中寻找子串

在文本串 $T$ 中寻找模式串 $S$，那么 $S$ 一定是 $T$ 的某个后缀的前缀，后缀排序后，在 $SA$ 中二分 $S$ 的位置，每次 $check$ 比较时间 $O (|S|)$，总时间复杂度 $O (|S| \log |T|)$

比较两个子串的大小关系

比较 $S$ 的子串 $A = S[l_1…r_1], B = S[l_2…r_2]$ 的大小关系

若 $lcp (l_1, l_2) \ge \min (|A|, |B|)$，则 $A < B \Longleftrightarrow |A| < |B|$，反之 $A < B \Longleftrightarrow rk_{l_1} < rk_{l_2}$

本质不同子串数目

设字符串 $S$ 长度为 $n$

$ans = \frac{n(n + 1)}2 - \sum\limits_{i = 2}^n height[i]$

从字符串首或尾取字符构成最小字典序的字符串

[USACO07DEC]Best Cow Line G

最基本贪心，若两端字符不同，优先取大的，那么问题就在于两端相同

设 $pre_i, suf_i$ 分别表示字符串 $i$ 开始的前、后缀，那么每次只要比较 $pre_i$ 和 $suf_i$ 的大小就可以决定，但是这样是 $O (n^2)$ 的

考虑将反串隔一个特殊字符插在原串后，跑一边后缀数组，假设此时原串剩余 $[l, r]$ 没处理，那么只要比较 $SA[2n - l + 2]$ 和 $SA[r]$ 即可（串以 $1$ 为起始位置）

判断字符串中是否存在某子串不重叠地出现了两次

二分子串长度 $L$，则 $height$ 数组能被分为若干满足段内 $height$ 数组大小都 $\ge L$ 的段，再利用 $RMQ$ 求出段内最大与最小的 $SA$ 值，判断其插值与 $L$ 的关系

后缀自动机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void append (int c) {
	int fa = last, p = ++ m;
	last = p;
	len[p] = len[fa] + 1, subsize[p] = 1;
	while (fa && ! tr[fa][c])
		tr[fa][c] = p, fa = father[fa];
	if (! fa) { father[p] = 1; return ; }
	int x = tr[fa][c];
	if (len[x] == len[fa] + 1) { father[p] = x; return ; }
	int np = ++ m;
	len[np] = len[fa] + 1, father[np] = father[x];
	father[x] = father[p] = np;
	memcpy (tr[np], tr[x], sizeof (tr[x]));
	while (fa && tr[fa][c] == x)
		tr[fa][c] = np, fa = father[fa];
}

本质不同子串个数

建立后缀自动机，在 $parent$ 树上对所有状态 $u$，统计 $\sum\limits_u len(u) - fa(len(u))$ 即可

所有不同子串的总长度

建立后缀自动机，在 $parent$ 树上一个点 $u$ 代表的所有后缀的贡献为 $\frac{(1 + len(u))len(u)}2$，然后再减去 $fa(u)$ 相应的贡献即是其净贡献

字典序第 $k$ 大子串

[TJOI2015]弦论

其中 $T$ 为 $0$ 则表示不同位置的相同子串算作一个，$T$ 为 $1$ 则表示不同位置的相同子串算作多个

咱按着路径来走，那么此时走到的每个状态对应唯一一个后缀，设 $sum_i$ 表示节点 $i$ 能够到达的所有子串个数，初始化 $sum_i$，若 $T = 0$ 则 $sum_i = 1$，若 $T = 1$ 则 $sum_i = size(i)$，然后再求个和，即 $sum_i += \sum\limits_c sum_{trans(i, c)}$

然后按位判断走一下就好了

1
2
3
4
5
6
7
for (int i = 1; i <= nodes; i ++)
	T == 0 ? Size[i] = Sum[i] = 1 : Sum[i] = Size[i];
Size[1] = Sum[1] = 0;
for (int i = nodes; i >= 1; i --)
	for (int j = 0; j < 26; j ++)
		if (Tree[Topo[i]][j])
			Sum[Topo[i]] += Sum[Tree[Topo[i]][j]];
1
2
3
4
5
6
7
8
9
10
11
void solve (int x, int k) {
	if (k <= Size[x]) return ;
	k -= Size[x];
	for (int i = 0; i < 26; i ++) {
		int t = Tree[x][i];
		if (! t) continue;
		if (k > Sum[t]) { k -= Sum[t]; continue; }
		putchar (i + 'a'), print (t, k);
		return ;
	}
}

最小循环移位

给定一个字符串 $S$，求其字典序最小的循环移位

不难发现 $S + S$ 一定包含 $S$ 的最小循环移位，那么构造出 $S + S$ 的后缀自动机，然后贪心访问最小的字符即可

模式串第一次出现的位置

给定一个文本串 $T$，多组查询。每次查询字符串 $P$ 在字符串 $T$ 中第一次出现的位置（$P$ 的开头位置）

设 $firstpos(i)$ 表示状态 $i$ 代表后缀第一次出现的位置

在 $parent$ 树上考虑，显然底层节点的 $endpos$ 一定是唯一的，那么它们的 $firstpos$ 也可直接确定，那么对一个不在底层的状态 $i$，有 $firstpos(i) = \min\limits_{j \cap fa(j) = i}\{firstpos(j)\}$

实际上上述过程可以在构造时做完（以下操作前提为 $T$ 位置编号从 $1$ 开始）

在新加入一个点 $p$ 时，有 $firstpos(p) = len(p)$

在将节点 $q$ 复制到 $np$ 时，有 $firstpos(np) = \min(firstpos(q), firstpos(p)) = firstpos(q)$

令 $t$ 表示 $P$ 在 $T$ 中走到的状态，那么答案便为 $firstpos(t) - |P| + 1$

最短的没有出现过的字符串

给定一个字符串 $S$ 和一个特定的字符集 $M$，我们要找一个长度最短的由 $M$ 中字符构成的没有在 $S$ 中出现过的字符串

在后缀自动机上动态规划，令 $f_u$ 表示已经处理了一段子串，当前在状态 $u$，为找到不连续转移还需要添加的最少字符数量，转移也比较简单
$$
f_u = 1 + \min\limits_{c \in M \cap trans(u, c) \in SAM} f_{trans(u, c)}
$$
那么最终答案为 $f_0$，输出字符串则逆推回去即可

两个字符串的最长公共子串

给定字符串 $S$ 和 $T$，求它们的最长公共子串

对 $S$ 构造后缀自动机

对 $T$ 的每个前缀，设当前前缀 $[1, i]$，求出该前缀的在 $S$ 上的最长后缀长度 $l_i$，那么答案即为 $\max\limits_i \{l_i\}$

将每个前缀放在后缀自动机上跑，设当前前缀 $i$ 最终走到状态 $u$，那么现在扩展到前缀 $i + 1$，多出字符 $T_{i + 1} = c$，有两种情况

  • 如果存在 $trans(u, c)$，那么 $u = trans(u, c), l_{i + 1} = l_i + 1$
  • 如若不然，则在后缀自动机找到前缀 $i$ 第一个点 $p$，使其满足 $trans (p, c)$ 存在，就是 $p$ 在 $parent$ 上是 $u$ 的祖先，同时 $l_{i + 1} = len(p)$，如果最终找不到，那就返回源点，同时 $l_{i + 1} = 0$

$l_n$ 最多为 $|T|$，而每位又最多被删一次，故最终时间复杂度 $O (|S| + |T|)$

多个字符串间的最长公共子串

给定 $k$ 个字符串 $S$。我们需要找到它们的最长公共子串，即作为子串出现在每个字符串中的字符串 $X$

Longest Common Substring II

这和求两个的实际上是差不多的

先对第一个字符串建一个后缀自动机，剩下的串在上面匹配

对于每个节点 $i$，设 $mx_i$ 表示当前匹配串走到状态 $i$ 可匹配的最长长度，$pl_i$ 表示走到状态 $i$ 的所有串在该处留下的最长匹配长度的最小值

当然 $mx_i$ 要先对它的子树的所有 $mx$ 取一个最大值，这样方便统计答案

那么最后答案便是 $\max\limits_i \{pl_i\}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
while (~ scanf ("%s", str + 1)) {
		n = strlen (str + 1);
		int p = 1, l = 0;
		for (int i = 1; i <= n; i ++) {
			int c = str[i] - 'a';
			while (p && ! tr[p][c])
				p = father[p], l = len[p];
			if (! p) p = 1, l = 0;
			else {
				l ++, p = tr[p][c];
				mx[p] = max (mx[p], l);
			}
		}
		for (int i = m; i >= 1; i --) {
			int x = topo[i];
			pl[x] = min (pl[x], mx[x]);
			mx[father[x]] = max (mx[father[x]], min (len[father[x]], mx[x]));
			mx[x] = 0;
		}
	}
	int ans = 0;
	for (int i = 1; i <= m; i ++) ans = max (ans, pl[i]);

对另外一种方法，就是把每个字符串隔一个不同的特殊字符拼在一起，然后把拼好的字符串拿去建后缀自动机的方法，本质上是一样的

求两个字符串本质不同的的子串总数

给定字符串 $S$ 和 $T$，并给定 $l, r$，求 $T$ 中不在 $S[l…r]$ 内出现的子串个数

[NOI2018]你的名字

先考虑 $l = 1, r = |T|$ 的情况：

因为任意子串为字符串前缀的某些后缀，那么令 $lim[i]$ 表示 $T[1…i]$ 在 $S$ 上所能匹配的最大长度，$posi[i]$ 表示$T$的后缀自动机上的点 $i$ 的 $endpos$ 集合中最靠前的位置，那么答案即为
$$
ans = \sum\limits_i \max (0, len(i) - min (len(fa(i)), lim[posi[i]]))
$$
其中 $i$ 枚举 $T$ 后缀自动机中的所有点

接下来考虑 $l, r$ 任意的情况：

原来能否在 $S$ 的后缀自动机上往下走的判断依据只有当前节点是否存在 $c$ 边，那么有了 $l, r$ 的限制，就多需要判断向下的这个节点的 $endpos$ 是否有存在于 $[l + len, r]$（$len$ 表示已匹配长度）区间的位置，$endpos$ 集合用动态开点线段树维护一下就好了

代码

求所有长度为 $k$ 的子串的最大出现次数

给定字符串 $S$，求 $S$ 中长度为 $k = 1…n$ 的子串的最大出现次数（对每个 $k$ 单独考虑）

考虑对某个 $k$，显然对它有贡献的只可能是 $minlen(i) \le k \le maxlen(i)$ 的所有状态 $i$

直接算的话得建棵线段树，实际上对某个子串，它的贡献一定是它自己直接给出贡献或是将它作为后缀的子串给出的，所以每次只需在 $maxlen(i)$ 处标记一下，然后再 $parent$ 树上对子树所有的贡献取 $max$ 就好了

广义后缀自动机

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
int append (int c, int last, int id) {
	int fa = last;
	if (tr[fa][c]) { // 与单串后缀自动机不同处
		int x = tr[fa][c];
		if (len[x] == len[fa] + 1) { subsize[x][id] = 1; return x; } // 特判一
		int np = ++ m;
		father[np] = father[x], len[np] = len[fa] + 1;
		father[x] = np;
		memcpy (tr[np], tr[x], sizeof (tr[x]));
		while (fa && tr[fa][c] == x)
			tr[fa][c] = np, fa = father[fa];
		subsize[np][id] = 1;
		return np; // 特判二
	}
	int p = ++ m;
	len[p] = len[fa] + 1, subsize[p][id] = 1;
	while (fa && ! tr[fa][c])
		tr[fa][c] = p, fa = father[fa];
	if (! fa) { father[p] = 1; return p; }
	int x = tr[fa][c];
	if (len[x] == len[fa] + 1) { father[p] = x; return p; }
	int np = ++ m;
	father[np] = father[x], len[np] = len[fa] + 1;
	father[p] = father[x] = np;
	memcpy (tr[np], tr[x], sizeof (tr[x]));
	while (fa && tr[fa][c] == x)
		tr[fa][c] = np, fa = father[fa];
	return p;
}
1
2
3
4
5
int last;
for (int i = 1; i <= 2; i ++) {
	scanf ("%s", str + 1); int n = strlen (str + 1);
	last = 1; for (int j = 1; j <= n; j ++) last = append (str[j] - 'a', last, i - 1);
}

注意 $size$ 要对每个串分开存

线段树合并维护广义后缀自动机 $size$

Forensic Examination

给你一个串 $S$ 以及 $m$ 个字符串数组 $T_1, T_2, …, T_m$，$q$ 次询问，每次问 $S$ 的子串 $S[p_l…p_r]$ 在 $T_l, …, T_r$ 中的哪个串里的出现次数最多，并输出出现次数。如有多解输出最靠前的那一个

对所有串建立广义后缀自动机，开一棵区间为 $[1, m]$ 的线段树，将每个状态的 $size$ 存下来（类似 $\text{modify} (rt[p], 1, m, id)$，其中 $id$ 表示当前插入的是 $m$ 个字符串中的哪个，注意 $S$ 插入后缀自动机时就不用修改线段树了），并进行线段树合并

那么每次只要在 $parent$ 树上倍增跳到包含区间 $S[p_l…p_r]$ 的点，就可以直接统计其对应线段树 $[l, r]$ 区间的最大值（即它子树的答案）

$Parent$ 树上两点间距离

[AHOI2013]差异

给定一个长度为 $n$ 的字符串 $S$，令 $T_i$ 表示它从第 $i$ 个字符开始的后缀，求 $\sum\limits_{1 \le i < j \le n} len(T_i) + len(T_j) - 2 \times LCP(T_i, T_j)$

将串反过来，后缀的最长公共前缀就变成了前缀的最长公共后缀

以 $len(i) - len(fa(i))$ 作为状态 $i$ 在 $parent$ 树上到父亲的边权，那么原式就可以看作 $parent$ 树上两个前缀对应的点 $u, v$ 之间的路径长度

由于只有前缀状态的 $size$ 才可能被初始化为 $1$，那么对点 $i$ 到其父亲的边，其贡献即为 $w_i \times size(i) \times (n - size(i))$，对所有边求和即可