串上DP

前言

总结一系列在字符串上通过动态规划实现渐进最优的算法。

为了形式化描述定义以下几个概念：

朴素算法： 不使用 DP 思想，暴力比较的算法。

匹配： 符合算法要求的一个子串，一般追踪地是最右边的一个匹配。

模式串： 作为算法运行目标的串，有时候相对于其他子串，也叫它母串。

同时：

1. 用 $n$ 表示母串的长度；
2. 用 $i_0$ 表示追踪的（最右）匹配所属的坐标，用 $s[l..r]$ 它所代表的子串。

Z 函数

后缀函数，母串与（真）后缀子串的前缀相等的部分。

特别规定： $z[0] = 0$

举例：

\[\begin{array}{l} \text{patstr}: s[0..6]=\text{abcabca}\\ &- &z[0] = 0\\ \text{suffix}[1]= s[1.. 6]=\text{bcabca} &\varnothing &z[1] = 0\\ \text{suffix}[2]=s[2..6]=\text{cabca} &\varnothing &z[2]=0\\ \text{suffix}[3]=s[3..6]=\text{abca} &abca &z[3]=4\\ \text{suffix}[4]=s[4..6]=\text{bca} &\varnothing &z[4]=0\\ \text{suffix}[5]=s[5..6]=\text{ca} &\varnothing &z[5]=0\\ \text{suffix}[6]=s[6..6]=\text{a} &a &z[6]=1\\ \end{array}\]

形式化表示：

$z[i] = \displaystyle \max_{k=0..i} {k: s[0.. k-1]=s[i..i+k-1]}$

DP过程：

寻找最右边的匹配，这里就应该是最右边的，与母串前缀相等的子串。

这个子串必然是之前的位置 $i_0$ 计算过的一个匹配，它的范围是 $s[i_0..r]$ ，首先确保了当前位置 $i$ 不会落到它的左边，这时如果发现 $i < r$ ，那么根据匹配的性质 $s[i_0..r]=s[0..r-i_0]$ ，就有：

$s[i..r]=s[r-i_0-(r-i)..r-i_0]=s[i-i_0..r-i_0]$ ，这样可以利用 $z[i-i_0]$ ：

1. 如果 $z[i-i_0] \lt r-i+1$，那么实际上 $z[i]$ 就是等于 $z[i-i_0]$ ，因为它们不仅与母串前缀相等的部分是一样的，与母串前缀不相等的失配字符也是一样的；
2. 如果 $z[i-i_0] \geqslant r-i+1$，那么z[i] 可以知道大于等于 $r-i+1$ ，之后可以遂行朴素算法逐字符匹配。

复杂度分析：

对每个位置 $i$ 运用朴素算法进行比较时，最多有 $1$ 次字符失配，在此之间的比较结果都是字符匹配，而每一次字符匹配都会使得最右匹配的 $r$ 加一，而 $r$ 不会超过 $n$ ，这样实际上总共的字符比较次数是 $O(n)$ 。

KMP 前缀函数

前缀函数，子串（真）前缀与子串后缀相等的部分。

特别规定： $\pi[0] = 0$

举例：

\[\begin{array}{l} \text{patstr}: s[0..6]=\text{abcabca}\\ &- &\pi[0] = 0\\ \text{prefix}[1]= s[0..1]=\text{ab} &\varnothing &\pi[1] = 0\\ \text{prefix}[2]=s[0..2]=\text{abc} &\varnothing &\pi[2]=0\\ \text{prefix}[3]=s[0..3]=\text{abca} &a &\pi[3]=1\\ \text{prefix}[4]=s[0..4]=\text{abcab} &ab &\pi[4]=2\\ \text{prefix}[5]=s[0..5]=\text{abcabc} &abc &\pi[5]=3\\ \text{prefix}[6]=s[0..6]=\text{abcabca} &abca &\pi[6]=4\\ \end{array}\]

形式化表示：

$z[i] = \displaystyle \max_{k=0..i} {k: s[0.. k-1]=s[i-(k-1)..i]}$

和上面 Z-函数比较，可以发现，它俩一个与模式串的前缀做比较，不过一个比较得是后缀的前缀，而另一个是前缀的后缀，这种相似性可能就是Z-函数被叫做拓展 KMP 的原因。

DP 过程：

这里的最右匹配是最右边的，与前缀相等的后缀子串，实际上也就是前一个位置的相等后缀，即 $i_0=i-1$ ，

记 $\pi[i-1]$ 为 $\pi_0^{(0)}$，则根据 $\pi$ 函数的性质，有 $s[0..\pi_0-1]=s[i_0-\pi_0+1..i_0]$ ，并且 $\pi[i] \leqslant \pi[i-1] + 1 = \pi_0+1$ ，

当 $s[i]=\pi_0$ 时，$\pi[i]$ 取到最大值 $\pi_0+1$ ，否则寻找下一个可能匹配，但是我们不能简单地缩小长度，因为比较的“基”发生了变化，KMP 前缀函数比通常其他串上 DP 更难想的点在于，它的失败匹配并不是一个简单过程，而是递归的，下一个可能的 $\pi_0^{(n)}$ 是从当前长度 $\pi_0^{(n-1)}$ 计算出的：$\pi_0^{(n)} = \pi[\pi_0^{(n-1)}-1]\ (n \geqslant 1)$ 。

如此这般，直到找到一个匹配，或者发现没有匹配。

复杂度分析：

求解每个位置 $i$ 的 $\pi[i]$ 时，最多有一次字符匹配，而每一次字符失配都会使得最右匹配的长度减少 $1$；同时匹配的长度一次最多增加 $1$ ，因此字符比较次数是 $O(n)$ 。

串哈希找最长回文

前缀函数，作为回文串的后缀部分。

背景：

使用串哈希的方法¹ 寻找模式串中最长的回文串。

举例：

\[\begin{array}{l} \text{patstr}: s[0..6]=\text{abaabaa}\\ \text{prefix}[0]= s[0..0]=\text{a}&a &R[0]=1\\ \text{prefix}[1]= s[0..1]=\text{ab} &b &R[1]=1\\ \text{prefix}[2]=s[0..2]=\text{aba} &aba &R[2]=3\\ \text{prefix}[3]=s[0..3]=\text{abaa} &aa &R[3]=2\\ \text{prefix}[4]=s[0..4]=\text{abaab} &baab &R[4]=4\\ \text{prefix}[5]=s[0..5]=\text{abaaba} &abaaba &R[5]=6\\ \text{prefix}[6]=s[0..6]=\text{abaabaa} &aa &R[6]=2\\ \end{array}\]

形式化表示：

$R[i] = \displaystyle \max_{k=0..i} {k: s[i-(k-1)..i]\ \in \text{Palindrome}}$

DP过程：

和 KMP 前缀数组的计算非常类似，而且更简单，首先最右匹配是前一个位置的后缀上的最长回文，$i_0=i-1$ 。

记 $R[i-1]$ 为 $R_0$ ，不管是奇数回文还是偶数回文，总有 $R[i] \leqslant R_0 + 2$ ，然后遂行朴素算法从长度为 $R_0 + 2$ 开始的后缀子串开始检查，如果不是回文，就一步步缩小长度直到 $1$ ²。

复杂度分析：

每一轮，回文检查成功最多一次，而检查如果失败，每失败一次就减少 $1$ ；同时 $R$ 每轮最多增加 $2$ ，这样暴力匹配的次数仍然是 $O(n)$ 。

Manacher 算法

以某个位置为对称轴的回文半径，分奇数轴和偶数轴两种情况，分别用 $d_1$ 和 $d_2$ 表示 。

特别规定：

1. 奇数回文的半径包含轴点本身，因此最小长度为 1；
2. 由于偶数回文的轴是两点间的空而不是点，因此这里规定空的坐标表示是它后面点的坐标，也就是和插入序³一样，这样 $d_2[0]$ 就是未定义的，不妨规定 $d_2[0]=0$ ，$0$ 也是偶数回文的最小长度。

背景：

求解所有本质不同的回文串

举例：

\[\begin{array}{l} \text{patstr}: s[0..6]=\text{abaabaa}\\ \\ \texttt{Odd:}\\ s[0]=\text{a}&a &d_1[0]=1\\ s[1]=\text{aba} &aba &d_1[1]=2\\ s[2]=\text{ababa} &a &d_1[2]=1\\ s[3]=\text{abaabaa} &a &d_1[3]=1\\ s[4]=\text{aabaa} &aba &d_1[4]=2\\ s[5]=\text{baa} &a &d_1[5]=1\\ s[6]=\text{a} &a &d_1[6]=1\\ \\ \texttt{Even:}\\ &- &d_2[0]=0\\ s[1]=\text{a-b} &\varnothing &d_2[1]=0\\ s[2]=\text{ab-aa} &\varnothing &d_2[2]=0\\ s[3]=\text{aba-aba} &abaaba &d_2[3]=3\\ s[4]=\text{baa-baa} &\varnothing &d_2[4]=0\\ s[5]=\text{ab-aa} &\varnothing &d_2[5]=0\\ s[6]=\text{a-a} &aa &d_2[6]=1\\ \end{array}\]

形式化表示：

$d_1[i] = \displaystyle \max_{k=0..i} {k: s[i-(k-1)..i+k-1]\ \in \text{Palindrome}}$

$d_2[i] = \displaystyle \max_{k=0..i} {k: s[i-k..i+k-1]\ \in \text{Palindrome}}$

DP过程：

类似于Z-函数的过程，最右匹配是最右边的回文半径，如果 $i < r$ ，由于肯定有 $i > i_0$ ，那么根据回文串的性质：

1. 轴的两侧是对称的；
2. 对称的两边交换位置，仍然是对称的

因此有对称的两个子串

$s[i..r] \leftrightarrow s[l..l+r-i]$

对奇数轴：$d_1[i]$ 初始值为 $\min(d_1[l+r-i], r-i+1)$ ；

对偶数轴：关于空的对称，采取插入序，$d_2[i]$ 初始值为 $\min(d_2[l+r-i+1], r-i+1)$

然后逐个字符比较，直到匹配或者字符串长度耗尽。

复杂度分析：

每轮的字符对称匹配最多失败一次，而每成功一次， $r$ 就要增加 $1$ ；而 $r$ 最多增加到 $n-1$ ，因此字符比较复杂度是 $O(n)$ 。

概念澄清

后缀树组（SA）

后缀函数，串所有后缀的排名。

注解