前缀函数，Z 函数，字符串问题

Z 函数

一些定义

字符串下标以 $0$ 为起点，$Z(i)$ 表示 $s$ 和 $s[i\cdots]$ （ $s$ 以下标 $i$ 开始的后缀）的最长公共前缀长度
$z(0) = 0$，并且 $s[0\cdots z(i)-1]$ 和 $s[i\cdots i+z(i)-1]$ 构成最长公共前缀
$s$ 从 $i$ 下标开始能和原串 $s$ 匹配上的最长子串就是 $s[i\cdots i + z(i) - 1]$

朴素算法

朴素算法根据定义暴力来求即可
暴力扩展的代码是

while (i + z[i] < n && s[z[i]] == s[i+z[i]]) z[i] += 1;

线性算法

思想，在计算 $z(i)$ 的时候，利用好已经计算好的 $z(0), z(1), \cdots z(i-1)$

对于 $i$，我们称区间 $[i, i+z(i)-1]$ 是 $i$ 的匹配段
算法实现的时候，我们尝试维护右端点最靠右的匹配段，不妨记这样的匹配段是 $[l, r]$

根据定义，我们有
$s[l\cdots r] = s[0\cdots r-l]$ （即 $s[l\cdots r]$ 是 $s$ 的前缀）

对于当前匹配段 $[i, i+z(i)-1]$

• 如果 $i \leqslant r$，那么 $s[i, r] = s[i-l, r-l]$，因此我们可以考虑已经算出来的 $z(i-l)$
  $z(i) \geqslant \min \left(z(i-l), r-i+1 \right)$

  • 如果 $z(i-l) < r-i+1$，直接令 $z(i) = z(i-l)$
  • 否则的话，$z(i-l) \geqslant r-i+1$，令 $z(i) = r-i+1$，此时意味着当前匹配段可能可以再往前扩展
    暴力扩展 $z(i)$ 直到不能扩展为止

• 如果 $i > r$，从 $s[i]$ 开始比较，暴力求出 $z(i)$

• 求出 $z(i)$ 之后，当前的匹配段是 $s[i, i+z(i)-1]$，如果 $i+z(i)-1 > r$，那么令
  $l = i, r = i+z(i)-1$

应用

匹配所有子串
记 $t$ 为文本串，$p$ 为模式串，求文本串 $t$ 中模式串 $p$ 所有出现的位置

• 构造一个新的字符串 $s = p + \# + t$，其中 $\#$ 不能出现在 $s, t$ 中
• 计算 $s$ 的 $z$ 函数，对于 $t$ 中的位置 $i \in [0, |t|-1]$
  在 $s$ 中得到 $\text{lcp} = z[|p|+1+i]$，如果 $\text{lcp} = |p|$
  那么就有一个 $p$ 出现在 $t$ 的第 $i$ 个位置

本质不同子串数
给定一个长度为 $n$ 的字符串 $s$，求 $s$ 的本质不同子串的数目

算法分析
考虑递推，假设已经知道当前 $s$ 的本质不同的子串数，考虑在 $s$ 末尾添加字符 $c$
此时本质不同子串数

首先，令 $t = (s+c)^{-1}$，表示 $s+c$ 的反串
那么新增加的子串，我们需要考虑以 $c$ 结尾的子串（其他子串我们递推之前考虑过了）
对应到 $t$ 中，就是以 $c$ 开头的前缀

很显然，这样的前缀有 $|t|$ 个，长度分别是 $\{1, 2, \cdots, |t|\}$
除此之外，我们还要扣除一部分前缀
如果一些前缀在 $t$ 的其他位置出现了，这些前缀是不需要计算的

计算 $t$ 的 $z$ 函数并且找到其最大值 $z_{\max}$
那么有一个最长的前缀出现在某一个长度为 $z_{\max}$ 的子串 $[p, p+z_{\max}-1]$ 中
同时，这个前缀所对应的子前缀，即长度 $\leqslant z_{\max}$ 的前缀也都会出现

所以有 $z_{\max}$ 个前缀不需要计算
答案应该是 $|t| - z_{\max}$

字符串的整周期
给定一个长度为 $n$ 的字符串 $s$，找一个最短的整数周期
即寻找一个最短的字符串 $t$，使得 $s$ 可以被若干个 $t$ 拼接而成

• 计算 $s$ 的 $z$ 函数，其整周期的长度为
  最小的 $n$ 的因子 $i$，满足 $i+z(i) = n$

前缀函数

先看一些定义
真前缀是指 $s$ 除了其本身的前缀，真后缀指 $s$ 除了其本身的后缀

前缀函数是一个长度为 $n$ 的数组 $\pi$，$\pi(i)$ 表示

• 如果子串 $s[0\cdots i]$ 有一对相等的真前缀和真后缀，不妨设 $S[0, k-1]$ 和 $s[i-k+1, i]$
  $\pi(i)$ 就是这个相等的真前缀和真后缀的长度，$\pi(i) = k$
• 如果有不止一对相等的，那么 $\pi(i)$ 就是其中最长的那一对的长度
• 如果没有相等的，那么 $\pi(i) = 0$

$\pi(i)$ 就是子串 $s[0\cdots i]$ 最长的相等的真前缀和真后缀的长度
特别的，$\pi(0) = 0$

计算前缀函数的朴素算法

• 一开始令 $\pi(0) = 0$，$i \in [1\to n-1]$ 开始遍历
• 然后尝试真前缀长度 $j$，从大往小了尝试, $j = i$ 看看行不行，不行就减小
  如果当前 $j$ 真前缀和真后缀相等，我们记 $\pi(i) = j$，然后退出循环
  否则 $j \leftarrow j-1$，继续尝试直到 $j = 0$
• 如果 $j = 0$ 并且仍然没有匹配，那么令 $\pi(i) = 0$，继续迭代下一个 $i$

高效算法

第一个优化
相邻的前缀函数值最多增加 $1$
注意到第 $i$ 次迭代，最长公共真前缀和真后缀为
$s[0\cdots \pi(i) - 1]$，当 $i \leftarrow i+1$ 时
最好的情况就是 $s[\pi(i)] = s[i+1]$，此时 $\pi(i+1) = \pi(i) + 1$

所以 $i \leftarrow i+1$ 时，前缀函数的值要么增加 $1$，要么不变，要么减少
在迭代到 $i$ 的时候
$j \in [\pi(i-1) + 1 \to 0]$ 开始迭代

for (int i = 1; i < n; i++) {
    for (int j = pi[i-1] + 1; j >= 0; j--) {
        // ...
    }
}

这个算法的复杂度取决于最大字符串比较次数，$j = \pi(i-1) + 1$
而 $\pi(i)$ 只有在最好的情况下才会增长，什么是最好的情况？
就是 $s[\pi(i)] = s[i+1]$，此时 $j \in [\pi(i-1)+1 \to 0]$ 只需要执行 $1$ 次

而如果比较次数超过 $1$ 次呢？实际上 $\pi(i)$ 并不会增加，所以总的比较次数为 $O(n)$
算法的时间复杂度为 $O(n^2)$

第二个优化
第一个优化我们考虑了
$s[0\cdots \pi(i)-1] + s[\pi(i)]$
$s[0\cdots i] + s[i+1]$
此时有 $s[\pi(i)] = s[i+1]$ 时候的情况，下面来看 $s[i+1] \neq s[\pi(i)]$ 的情况

从递推的角度来考虑
失配的时候，对于子串 $s[0\cdots i]$，尝试去找到仅次于 $\pi(i)$ 的第二大的长度 $j$
使得 $s[0\cdots j-1] = s[i-j+1\cdots i]$
如果 $s[j] = s[i+1]$，那么令 $\pi(i+1) = j$
如果 $s[j] \neq s[i+1]$，那么我们尝试去找到仅次于 $j$ 的次大长度 $j^{(2)}$，以此类推
直到 $j = 0$，如果仍然有 $s[i+1] \neq s[0]$，那么 $\pi(i+1) = 0$

下面考虑 $j$ 如何求
注意到此时我们失配位置是 $s[\pi(i)] \neq s(i+1)$，同时我们已经有
$s[0\cdots \pi(i)-1] = s[i-\pi(i)+1\cdots i]$，而我们要找的 $j$ 满足
$s[0\cdots j-1] = s[i-j+1\cdots i]$，同时 $[i-j+1, i]$ 对应到 $[0, \pi(i)-1]$ 的后一半长度为 $j$ 的段
从而有 $s[0 \cdots j-1] = s[i-j+1\cdots i] = s[\pi(i) - j \cdots \pi(i) - 1]$

换句话说，$j$ 等价于 $s[\cdots \pi(i) - 1]$ 的前缀函数值，即 $j = \pi\left(\pi(i) - 1 \right)$
同理，$j^{(2)} = \pi(j-1)$

$j$ 的状态转移方程如下
$\displaystyle j^{(n)} = \pi\left(j^{(n-1)} - 1 \right), \ (j^{(n-1)} > 0)$

应用

kmp算法

给定一个文本串 $t$ 和字符串 $s$，尝试在 $t$ 中找到 $s$ 所有出现的位置

构造一个字符串 $s + \# + t$，其中 $\#$ 是既不在 $s$ 中也不在 $t$ 中出现的分隔符
其中 $n$ 表示 $s$ 的长度，$m$ 表示 $t$ 的长度，下标从 $0$ 开始

我们考虑 $i \in [n+1 \to n+m]$ 这些位置，如果在某个位置有 $\pi(i) = n$ 成立，根据前缀函数定义
那么说明 $t$ 和 $s$ 配上了，匹配段的终点是 $r = i-(n+1)$，起点呢？只需要终点往前走 $n$ 的长度
匹配位置是 $l = i - (n+1) - n + 1 = i - 2n$

字符串的周期

对字符串 $s$ 和 $0 < p \leqslant |s|$，如果 $s[i] = s[i+p]$ 对所有 $i \in [0, |s|-p-1]$ 成立
那么称 $p$ 是 $s$ 的周期

对字符串 $s$ 和 $0 \leqslant r < |s|$，如果 $s$ 长度为 $r$ 的前缀和长度为 $r$ 的后缀相等
就称 $s$ 长度为 $r$ 的前缀是 $s$ 的 border

那么可以推出
$s$ 如果有长度为 $r$ 的 border，那么 $|s| - r$ 就是 $s$ 的周期

注意，如果 $|s|$ 除去前后缀中还空出来一段，那么这一段也是周期的一部分）
这样其实不会违背周期的定义，周期是检查所有 $i \in [0, |s|-p-1]$ 的位置，空出来的位置不需要检查）
此时仍然能保证 $[0, r-1]$ 中的所有位置满足 $s[i] = s[i+p]$

根据前缀函数的定义，可以得到 $s$ 所有 border 的长度
$\displaystyle \pi(n-1), \pi \left(\pi(n-1) - 1 \right), \cdots$

那么 $s$ 最长的 border 长度是 $\pi(n-1)$，所以 $s$ 最小周期是
$n - \pi(n-1)$

统计每个前缀出现次数

第一个问题
给定一个长度为 $n$ 的字符串 $s$，我们希望统计每个前缀 $s[0\cdots i]$ 在同一个字符串的出现次数

考虑位置 $i$，其前缀函数值为 $\pi(i)$
意味着字符串一个长度为 $\pi(i)$ 的前缀以 $i$ 为右端点
同时，一定不存在更长的前缀以 $i$ 为右端点，可能存在更短的前缀以 $i$ 为右端点

那么这个问题就转换成为
给定一个长度为 $j$ 的前缀，同时也是一个右端点位于 $i$ 的后缀
那么下一个更小的前缀长度 $j^{(2)} < j$ 是多少？
同时这个前缀也必须是一个以 $i$ 为右端点的后缀

因此，以 $i$ 为右端点的前缀，长度从大到小依次是
$\displaystyle \pi(i), \pi \left(\pi(i) - 1 \right), \pi \left(\pi\left(\pi(i)-1 \right) - 1 \right), \cdots$

假设我们已经知道了 $x = \pi(i)$ 这个前缀出现的次数 $ans(x)$
那么 $\{\pi(x-1)\cdots \}$ 和 $x$ 有着相同的右端点，所以 $x$ 出现了
那么 $\{\pi(x-1), \pi(pi(x-1) - 1), \cdots \}$ 也都会出现

由此从后往前扫描每一个可能的 $\pi = x$，$ans(\pi(x-1)) += ans(x)$

vector<int> ans(n+1, 0);
for (int i = 0; i < n; i++) ans[ pi[i] ] += 1;
for (int x = n-1; x > 0; x--) ans[ pi[x-1] ] += ans[x];
for (int i = 0; i <= n; i++) ans[i]++;

第二个问题
统计每一个前缀 $s[0\cdots i]$ 在另一个给定文本串 $t$ 中出现次数

构造一个字符串 $s + \# + t$，对 $i \geqslant n+1$ 的位置的 $\pi(i)$
执行第一个问题对应的算法即可

一个字符串中本质不同的子串数目

一个长度为 $n$ 的字符串 $s$，希望计算其本质不同的子串的数目
还是用迭代的思路来解决，假设我们已经知道了当前计算出的本质不同子串数目、
考虑在 $s$ 末尾添加一个字符后，这些子串数目会如何变化

假设我们已经知道了当前 $s$ 本质不同的子串数量 $res$，在 $s$ 末尾添加一个新字符 $c$
我们希望，考虑以 $c$ 结尾的，并且之前没有遇到过的子串，对这些子串计数

构造字符串 $t = s+c$，将其反转得到 $t^{-1}$
我们需要统计有多少 $t^{-1}$ 的前缀未在 $t^{-1}$ 的其他地方出现

我们计算 $t^{-1}$ 每一个位置的前缀函数并取最大值 $\pi_{\max}$
那么 $t^{-1}$ 中最长的已出现的前缀长度就是 $\pi_{\max}$，自然更短的前缀也都会出现

因此新添加一个字符后，新出现的子串数目为
$\displaystyle |s| + 1 - \pi_{\max}$

字符串压缩

给定一个长度为 $n$ 的字符串 $s$，我们希望找到 $s$ 的压缩表示
即寻找一个最短的字符串 $t$，使得 $s$ 可以被 $t$ 的一份或者多份拷贝的拼接来表示出来

显然我们只需要知道 $t$ 的长度即可，知道 $t$ 的长度之后
答案就是 $s$ 中长度为 $|t|$ 的前缀

计算 $s$ 的前缀函数，对于该函数的 $\pi(n-1)$，定义 $k = n - \pi(n-1)$
下面我们尝试证明
如果 $k \mid n$，那么 $k$ 就是答案，否则不存在有效的压缩，答案就是 $n$

先证必要性
如果 $k \mid n$，意味着字符串可以被划分成长度为 $k$ 的若干块
$n - k = \pi(n-1)$，也就是说，长度为 $n - k$ 的前缀等于长度为 $n-k$ 的后缀

$\displaystyle \overbrace{ \underbrace{ s_0s_1s_2 }_{k}s_3\cdots\cdots s_{\pi(n-1)-1} }^{n-k= \pi(n-1)}\overbrace{ s_{n-3}s_{n-2}s_{n-1} } ^{k}$

从图中可以发现，长度为 $k$ 的串被前缀 $[0, \pi(n-1)-1]$ 所包含
再根据前缀函数的性质，最后一个块和倒数第二个块相等，以此类推
这样所有的长度为 $k$ 的块都是相等的，因此可以将字符串 $s$ 压缩成长度 $k$
充分性用反证法很容易得到

再证明这个解是最优的
如果有一个比 $k$ 更小的压缩表示，那么就意味着前缀函数的最后一个值 $\pi(n-1) > n-k$
我们仍然取 $k = n - \pi(n - 1)$，这就是答案

如果 $k \nmid n$，我们用反证法证明答案是 $n$

Educational Codeforces Round 118

D. MEX Sequences
题目大意
给定一个整数序列 $\left<x_1, x_2, \cdots, x_k \right>$ 定义为 $\text{mex-correct}$
当且仅当对于每一个 $1 \leqslant i \leqslant k$，都有 $|x_i - \text{mex}(x_1, x_2, \cdots, x_i)| \leqslant 1$
给定一个由 $n$ 个非负整数组成的数组 $a$，计算给定数组的非空 $\text{mex-correct}$ 子序列的数量
并且对 $998244353$ 取模
注意，子序列只要 $a_{i1}a_{i2}\cdots a_{im}$ 至少一个下标不同，就被认为是不同的子序列
值相同与否无所谓

算法分析
注意到 $\text{mex}$ 数组一定是单调非降的

如果一个序列的前缀 $\text{mex} = x$，那么这个序列要么是 $[0, 1, \cdots x]$ 单调不降的
要么是末尾几个数在 $< x$ 和 $> x$ 的数之间来回横跳
$dp$ 的时候要综合考虑两种情况

现在我们考虑第 $i$ 个位置，$\text{mex}[0\cdots i] = x$，此时序列有两种情况
$[0, i] :\left<\underline{0,\cdots, 0}, \underline{1, \cdots, 1}, \cdots, \underline{x-1,\cdots, x-1} \right>$
$[0, i]: \left<\underline{0, \cdots, 0}, \underline{1, \cdots, 1}, \cdots, \underline{x-1, \cdots, x-1}, \underline{x+1, \cdots, x+1} \right>$

$dp_i(x)$ 表示考虑第 $i$ 个位置，前缀 $\text{mex}[0\cdots i] = x$ 时的方案数
这两种情况必须分开来 $dp$，因为第一种情况 $dp_{i}(x)$ 可以转移到 $dp_{i+1}(x+1)$
第二种情况，添加 $a_i = x$ 之后，$dp_{i}(x)$ 会转移到 $dp_{i+1}(x+2)$，而这是不合法的，因为此时 $|\text{mex} -x| = 2$

情形1 单调不降
记 $dp1(i, x)$ 表示当前考虑第 $i$ 位（考虑的意思是，将要把 $a[i]$ 添加到序列末尾，但还未添加）
目前已得到序列的前缀 $\text{mex}$ 值是 $x$，此时对应的方案数

• $a[i] < x-1 \ \textbf{or} \ a[i] > x+1$，那么 $a[i]$ 不能添加到末尾，否则 $|\text{mex} - a[i]| \geqslant 2$ 不合法
• $a[i] = x-1$，添加 $a[i]$ 之后，$\text{mex}$ 值不会变化，存在转移 $dp1(i+1, x) \leftarrow dp1(i, x)$
• $a[i] = x$，添加 $a[i]$ 之后，$\text{mex} = x+1$，存在转移 $dp1(i+1, x+1) \leftarrow dp1(i, x)$
• $a[i] = x+1$，添加 $a[i]$ 之后，$\text{mex}$ 值还是 $x$，但是就变成了第二种情形了
  存在转移 $dp2(i+1, x) = dp1(i, x)$

情形2 来回横跳
同样记 $dp2(i, x)$ 表示第二种情形

• $a[i] < x-1 \ \textbf{or} \ a[i] > x+1$，此时 $a[i]$ 同样不能添加到末尾
• $a[i] = x-1$，添加 $a[i]$ 后，$\text{mex}$ 值不变，存在转移 $dp2(i+1, x) \leftarrow dp2(i, x)$
• $a[i] = x$，添加 $a[i]$ 之后，$\text{mex} = x+2$，（因为这种情况我们考虑序列中已经有 $x+1$ 了）
  那么 $|\text{mex} - a[i]| = |x+2 - x| = 2$ 不符合题意
• $a[i] = x+1$，添加 $a[i]$ 之后，同样 $\text{mex}$ 值不会变化，存在转移 $dp2(i+1, x) \leftarrow dp2(i, x)$

综上所述
遍历整个序列，令 $x = a[i]$
对于情形 $1$ 存在转移
$dp1_{i+1}(x+1) += dp1_{i}(x+1), \quad dp1_{i+1}(x+1) += dp1_{i}(x), \quad dp2_{i+1}(x-1) += dp1_{i}(x-1)$

对于情形 $2$ 存在转移
$dp2_{i+1}(x+1) += dp2_{i}(x+1), \quad dp2_{i+1}(x-1) += dp2_{i}(x-1)$

在实现的时候，可以省略第一维，但是要注意 $dp$ 的顺序
$dp2_{i+1}(x-1) += dp1_i(x-1)$ 一定要放在 $dp2_{i+1}(x-1) += dp2_i(x-1)$ 之后
因为我们更新 $dp2(x-1) += dp1(x-1)$ 的时候，所希望的一定是 $dp2_{i+1}(x-1)$ 而不是 $dp2_{i}(x-1)$
所以应该先把 $dp2_{i+1}(x-1)$ 全部更新了，那么对应的 $dp2(x-1)$ 就是新的 $dp2_{i+1}(x-1)$