next数组在子序列计数、最优化问题中的应用

pb_ds

摘要

在OI比赛（特别是FJOI）中，常常会出现一类和子序列有关的计数、最优化问题。在以前，这类问题并没有一些比较通用的思考方法，导致了较大的思维复杂度，也使得状态数优化较为困难。
而一类子串问题中，我们引入和后缀自动机（SAM）这一有限状态自动机。在这类问题中，我们左有后缀自动机的简单构造，右有自动机和后缀树的优美性质，SAM常常能所向披靡，轻而易举的解决各类和子串有关的问题。
本文提出了next数组这一能识别一个串所有子序列的“序列自动机”，描述了它的 $O(n|alpha|)$ 构造算法，并从一些例题展开讨论。

定义及构造

设next[i][w]表示在原串 $s$ 第i位后面的第一个w出现的位置（如果没有，则next[i][w] = -1）。则以0为初始节点，next[i][w]转移函数，所有节点为接受状态的有限状态自动机为 $s$ 的序列自动机。
显然，最简单的构造方法是 $O(n|alpha|)$ 的：

def build(s, next):
    n = |s|
    next[n][*] = -1
    for i = n -> 1:
        for j in A:
            next[i - 1][j] = next[i][j]
        next[i - 1][s[i]] = i

构造完毕后，我们就可以开始使用了。
这里也明显的突出了next数组的缺点：不适合 $|alpha|$ 太大的应用。

单串问题

这里将介绍一些经典的单串问题（不一定是DP）。

0 最小字典序子序列

给一个串，求一个字典序最小的子序列。显然这是一个非常简单的问题，但我们考虑用next数组来做。
next数组可以看作是一棵缩成DAG的trie树（其实就是trie图），因此我们按照最小字典序在next数组上走就行了。
时间复杂度： $O(|输出规模||alpha|)$ 。

1 子序列计数

给一个串，求它不同子序列计数。其实就是求next数组扩展成trie树的节点数。
暴力统计显然不行，比如一个1~n的排列，任何子序列均不同，因此答案达到 $2^n$ 。
考虑另一种思路，next数组可以看成DAG，任何一条从0到任意节点的路径都是一个不同的子序列，因此我们统计的就是从0开始的路径条数，DAG上DP即可。并且由于点的编号就是拓扑序，实现起来十分方便，可以不用显式的建出数组。
时间复杂度： $O(n|alpha|)$ 。
注意到这里的路径和子序列是一一对应的，而DAG上的DP又是我们熟悉的，因此我们能这样不重不漏的统计子序列，这给了我们一个不错的计数方式。

2 最长上升子序列

公共子序列相关

一个串是两个串的公共子序列，当且仅当它在两个序列自动机中都有对应的节点。
我们用一个 $(a, b)$ 表示一个串在 $s0$ 的序列自动机的节点 $a$ ，在 $s1$ 的序列自动机的节点 $b$ ，则对于一个字母 $w$ ，如果 $next0[a][w] \ne -1$ 且 $next1[b][w] \ne -1$ ，则可以在这个串后面加一个字母 $w$ ，转移到状态 $(next0[a][w], next1[b][w])$ 。
那么其实我们在做的事就是求一个自动机的并了。可以看作是一个DAG的并，一条边存在当且仅当这条边在两个DAG中都存在。这个新的自动机中，起始状态为 $(0, 0)$ ，接受状态为任意 $(i \ne -1, j \ne -1)$ 。

3 最小字典序公共子序列

给定两个串，求它们的字典序最小的公共子序列。
在合并了的自动机中，每次按照最小字典序走。
时间复杂度： $O(n|alpha|)$ 。

4 公共子序列计数（FJOI2016）

给定两个串，求它们的所有公共子序列个数。
我们就在这个新的DAG中做路径条数的DP即可。
时间复杂度： $O(|s0||s1||alpha|)$ 。
”可是这个复杂度过不了啊？“
注意到一个状态 $(i, j)$ 存在，当且仅当 $s0_i = s1_j$ ，因此实际状态数不会超过相等的位置对数。
并且若 $s0 = s1$ 且 $s0 = aaaa...aaaa$ ，这样的状态数只有 $n$ 个，因为初始状态为 $(0, 0)$ ，且位置 $(i, j)$ 只会转移到 $(i + 1, j + 1)$ 或空。
唯一能卡到接近上界的是一种随机的01串，不过这样相等对数也大概为 $nm\over 4$ 。
为了能只取有效状态，避免扩展无效状态，大力资磁用记忆化搜索实现DP。

5 最长公共子序列

给你两个串，求它们的最长公共子序列。
转化为DAG之后，我们要求的就是DAG最长路。仍然是熟知的DAG上DP。
时间复杂度： $O(|s0||s1||alpha|)$ 。
这个时间复杂度是劣于经典做法的 $O(nm)$ 。但注意到相等对数的限制，实际的状态数其实很少，记忆化搜索的运行时间往往快于经典做法。但仍然要注意这个算法只能胜任 $|alpha|$ 不大的情况。

6 带单串作为子序列包含约束的LIS（FJOI2013）

给三个串 $A$ 、 $B$ 、 $C$ ，求一个最长的 $A$ 、 $B$ 的公共子序列 $s$ ，要求 $C$ 是 $s$ 的子序列。
这时，如果只记录二元组 $(i, j)$ 是不行的，我们考虑仍然用自动机识别“包含 $c$ 作为子序列”的串。
这个自动机的构造也相当显然。设 $c$ 为 $C$ 串的这种自动机的转移函数，则：

$c[i][j \ne C_{i+1}] = i$
$c[i][C_{i+1}] = i + 1$
起始状态为 $0$ ，接受状态仅为 $|c|$

然后，我们利用三元组 $(i, j, k)$ 记录状态，则我们要求的是 $(0, 0, 0)$ 到任意形如 $(i \ne -1, j \ne -1, |c|)$ 的节点的最长路。DP！
时间复杂度： $O(|A||B||C||alpha|)$ 。
同样存在严格 $O(|A||B||C|)$ 的经典算法，但仍然由于状态合法性的原因只比此算法快 $14\%$ 。并且只有此算法可以推广到这个问题的计数版本。

7 最短不公共子序列（HEOI2015）

给定 $A$ 、 $B$ 两个串串，求：

一个最短的 $A$ 的子串，不是 $B$ 的子串
一个最短的 $A$ 的子序列，不是 $B$ 的子串
一个最短的 $A$ 的子串，不是 $B$ 的子序列
一个最短的 $A$ 的子序列，不是 $B$ 的子序列

先考虑第4个子问题。如果仍用二元组记录，那么这样的接受状态就是任意 $(i \ne -1, -1)$ ，而我们的答案就是 $(0,0)$ 到任意这样点的最短路。因此构造出两个串的next数组，就可以利用BFS求出答案。这样同样不会扩展到不必要的状态。
考虑其他子问题。能接受所有子串的自动机就是后缀自动机（并把所有节点标记为接受），那么我们就可以推广到一个一般的问题：给出两个自动机，求出被第一个自动机接受而不被第二个自动机接受的最短串。显然上面那个方法可以推广，因此这个问题就这样被解决了。
时间复杂度： $O(|A||B||alpha|)$ 。
这个算法同样可以被推广到这一类计数问题上

8 多个串的公共子序列

给出 $k$ 个串 $s_1...s_k$ ，求出它们的最长公共子序列和不同的公共子序列个数。
既然我们能做2个串，我们就也能做k个串：把k个自动机合并起来就OK了。但复杂度不是很优美，也没有什么好的替代方法。
注意到多个串会导致有效状态数大大减小，因此可以用记忆化搜索和哈希表来保存状态。
时间复杂度： $O(|alpha|\prod_{i=1}^k |s_i|)$ 。
如果加入“至少是 $k$ 个串的公共子序列”这一约束，则我们可以允许状态中存在不少于 $k$ 个非0位置。复杂度不变。

9 两个串带多串作为子串包含的公共子序列（FJOI2015）

给出两个串 $a,b$ ，再给出 $k$ 个串 $l_1...l_k$ ，要求求出一个最长的 $a,b$ 的公共在序列 $s$ ，使得所有 $l_i$ 是 $s$ 的子串。
解决子串问题需要用到AC自动机，由于这里需要是所有串的子串，我们还得记录一个 $2^k$ 的状压。这样我们就为限制建了一个状态数为 $2^k\sum_{i=1}^k |l_i|$ 的自动机，状态形如 $(节点，0...2^k)$ 。把它和 $a、b$ 的next数组放在一起DP即可（求 $(0, 0, 0, 0)$ 到任意 $(i \ne -1, j \ne -1, *, 2^k)$ 的最长路）。
这题的状态相当多，因此我们仍然需要记忆化+哈希存状态。除此之外，我们还可以加一些剪枝，比如如果当前长度就算后面忽略了限制都无法超过答案，就停止扩展此状态。另一个剪枝就是预处理 $a[i...|a|]$ 和 $b[j..|b|]$ 的LIS，在所有限制都满足的时候直接取用，但其实记忆化就已经暗藏了这个剪枝。
时间复杂度： $O(\min\{|a||b||2^k||alpha|\sum_{i=1}^k |s_i|,玄学\})$ 。
如果转为计数问题，就不能加最优性剪枝。

10 多个串的公共上升子序列

给出 $k$ 个串 $s1...sk$ ，求出它们的最长公共上升子序列和公共上升子序列的个数。
同样可以使用上升序列自动机的组合进行DP。如果字符集太大，需要离散化字符集。
我们知道对于 $k=2$ 的情况有一个 $O(n^2)$ 的求LCIS的算法（YZOJ1235），可以推广到更多串的情况，但有且仅有借助了next数组的方法可以进行计数。
时间复杂度： $O(|alpha|\sum_{i=1}^k |si|)$ 。

11 回文子序列计数

给出一个串，求其不同回文子序列个数。
考虑从左右两端构造回文串。构造原串及反串的序列自动机，DP。
对于状态 $(i, j)$ ，若 $i+j\le n$ ，则此状态能表示一个长度为偶数的回文串；若 $i+j-1\le n$ ，则能表示一个长度为奇数的回文串。
时间复杂度： $O(n^2|alpha|)$ 。

字典序及长度相关

作为自动机，next数组解决字典序问题是浑然天成的。同样，增加一维状态表示长度也可以用来做和长度有关的题目。

12 子序列长度之和

给出一个串，求其所有不同的子序列长度之和。
一个比较naive的做法，就是增加长度这一维，把状态记为 $(位置, 长度)$ ，则答案就是每个状态的出现次数乘上长度之和。
时间复杂度： $O(n^2|alpha|)$ 。
考虑转化为DAG模型，则答案就是每条边走的次数之和乘上边长（这里都是1）。假设当前在节点i，且以next[i][w]开头的串的个数为 $x$ ，那么就有 $x$ 个不同的子串经过next[i][w]。
时间复杂度： $O(n|alpha|)$

13 长度区间范围内计数

给出一个串，求其长度在 $[l, r]$ 内的不同子序列个数。
这下就必须记录长度作为一维状态了。
时间复杂度： $O(nr|A|)$ 。

14 长度范围内最小字典序子序列

给出一个串，求其长度在 $[l, r]$ 内的最小字典序子序列。
考虑一子序列，它的任意前缀的字典序均比它小，因此 $r$ 是没用的，我们真正的任务是求长度为 $l$ 的最小字典序子序列。
考虑当前在节点i，已有长度为 $a$ ，则下一个节点不能超过 $n - l + a$ （否则就算全取满都无法达到 $l$ ）。由于next数组取的就是（尽量靠前的）下一个位置，因此我们要取的是 $\min_w next[i][w] \ne -1 且next[i][w] \le n - l + a$ 作为下一个字符。从0开始，按照此规则走 $l$ 步即可。
时间复杂度： $O((n+l)|alpha|)$ 。

15 长度范围内最小字典序公共子序列

给出两个串，求一个长度在 $[l, r]$ 内的最小字典序公共子序列。
同样，只需考虑限制 $l$ 。但是我们并不能 $O(1)$ 得出一个状态 $(i, j)$ 能扩展出的最长长度，因此我们需要预处理一些东西。预处理什么呢？从 $(i, j)$ 出发的最长路！也就是从 $(i, j)$ 开始的最长公共子序列！
设 $f(i, j)$ 为从 $(i, j)$ 出发的最长路，则我们从状态 $(i, j)$ 出发，已有长度为 $a$ ，走的字母就是 $\min_w next[i][w] \ne -1 且 next[j][w] \ne -1 且 f(next[i][w], next[j][w]) \ge l - a$ 。按照此规则从 $(0, 0)$ 出发，走 $l$ 步即可得到答案。
时间复杂度： $O((nm + l)|alpha|)$ 。

16 k小字典序子序列（相同的算一个）

给出一个串，求其第k小字典序子序列。
相同的子序列算一个，则就相当于在next数组上走，每次考虑走字母w能获得的子序列个数是否不超过k，如果不超过，则这一位为w；否则，令k减去该个数，并考虑下一个字母。如果k为0，则停止并输出答案。
时间复杂度： $O(n|alpha|)$ 。

17 长度范围内的k小字典序子序列（相同的算一个）

给出一个串，求其长度在 $[l, r]$ 之间的k小字典序子序列。
考虑修改问题15的统计个数的方式。其实我们只需要用问题12的计数方法即可解决此问题。
注意当 $k=0$ 的时候，如果长度不足 $l$ ，要沿着最小字典序走到长度 $l$ 。
时间复杂度： $O(nr|alpha|)$ 。

总结

序列自动机给了我们一个强有力的理论支撑，让我们可以更加系统的处理一类关于子串的最优化问题，也提供了唯一可以用于子串计数的工具，甚至送给了我们一个绝妙的附属品：关于字典序的处理。