综合 (Ex)KMP 算法学习笔记
$$\huge \rm (Ex)KMP$$
$$\Large \rm Border~\&~\pi 函数$$
$\large \rm 一些定义$
字符串 $S$ 的真 前 / 后 缀为非自身的 前 / 后 缀。
字符串 $S$ 的 $border$ 为 $S$ 的公共真 前 / 后 缀。
字符串 $S$ 的最长 $border$ 为 $\pi$，对于 $S$ 的每个前缀 $S_{1 \sim i}$ 令 $\pi_i$ 为其最长 $border$，$\pi$ 函数就是所谓的前缀函数。
$\large \pi 函数的性质$
- $\forall i,\pi_{i+1}\leqslant \pi_i+1$.
由反证法易知。
- 字符串 $S$ 的所有 $border$ 可以由 $\pi_{|S|}$ 开始不断跳 $\pi$ 由长度从大到小遍历。
只需证明 $S_{1 \sim \pi_{\pi_n}}$ 是 $S$ 的次长 $border$ 即可。
由 $\pi$ 的定义易知。
- 相邻前缀函数满足 $\pi_{i + 1} = \max\limits_{T ~ is ~ the ~ border ~ of ~ S_{1 \sim i}, S_{i + 1} = S_{|T| + 1}} |T| + 1$。
使用反证法易知。
$\large \pi 函数的线性求法$
$\quad$有了上述几条性质，我们可以得到一个求解 $\pi$ 函数的算法：
pi[0] = -1;
for (int i = 1; i <= n; i++)
for (int j = pi[i - 1]; j >= 0; j = pi[j])
if (s[j + 1] == s[i]) { pi[i] = j + 1; break; }
直观感受上这个做法是 $\Theta(n ^ 2)$ 的，但实际上它是线性的，复杂度证明如下：
不难发现复杂度来源在于跳 $\pi$，下面我们将证明跳 $\pi$ 的总次数是线性的。
注意 $\pi_i$ 的位置变化情况，不难发现 $\pi_i$ 只会每次 $+1$ 或往前跳若干次，但往前跳的的总距离不能超过当前 $+1$ 的次数，故总路程也是线性的。
$$\Large \rm \pi 函数的基本应用$$
$\large \rm 字符串匹配$
$\quad$求解模式串 $T$ 在匹配串 $S$ 中的出现位置的问题。
$\quad$构造一个新的字符串 $T\circ S$，其中 $\circ\not\in S\cup T$，它仅作为一个分隔符。
$\quad$对这个新的字符串求其 $\pi$ 函数，不难发现由于分隔符的出现，$\forall i, \pi_i \leqslant |T|$，于是找到 $\pi_i = |T|$ 的位置，$i - |T| + 1 \sim i$ 就是一个匹配。
$\large \rm 统计每个前缀的出现次数$
$\quad$考虑到如果某个前缀在之后的位置里出现过，那么一定是某个前缀的 $Border$，于是我们考虑在每个数的最大 $Border$ 处统计答案，其为更小 $Border$ 的重复次数，并且更小的 $Border$ 一定可以通过跳 $\pi$ 遍历到，这样只需要从后往前扫一遍，复杂度 $\Theta(n)$.
for (int i = 1; i <= n; i++) ans[i] = 1;
for (int i = n; i >= 1; i--) ans[pi[i]] += ans[i];
$\quad$至于这个问题的加强版，统计 $S$ 中的每个前缀在 $T$ 中的出现次数，可以构造 $S#T$，赋初值的时候只需要将 $T$ 中的位置初始化为 $1$ 即可。
$\large \rm 统计本质不同子串的数目$
$\quad$考虑迭代计算，问题转化成：在当前字符串的末尾加入一个新的字符，以这个字符结尾的后缀中有多少个是前面没有出现过的。
$\quad$如果一个子串 $S_{i\sim n}$ 在前面出现过，则 $\forall j\geqslant i,S_{j\sim n}$ 都在前面出现过。
由反证法易知。
$\quad$于是就只需求出加入新字符后的串的反串中的 $\max\pi$ 即可，而这个字符的贡献就是 $|S|+1-\max\pi$，时间复杂度 $\Theta(n^2)$.
$\large \rm 字符串周期相关性质$
$\quad$称 $k$ 为 $S$ 的一个周期且仅当 $\forall i\leqslant |S|-k, S_i = S_{i + k}$，特别地若 $k \nmid S$ 则称 $k$ 为 $S$ 的弱周期。
- 若字符串 $S$ 存在一个 $border ~ T$，当且仅当 $S$ 存在一个长度为 $|S| - |T|$ 的（弱）周期。
必要性显然，充分性递归论证即可。
- 字符串 $S$ 的最短（弱）周期长度为 $n - \pi_n$。
由 $\pi$ 函数的定义易知。
- 若长度不小于 $p + q$ 的字符串 $S$ 存在长度分别为 $p, q$ 的（弱）周期，那么 $\gcd(p, q)$ 也是 $S$ 的一个（弱）周期。
下面首先证明 $p - q(p > q)$ 也是 $S$ 的一个（弱）周期。
分两种情况讨论：
若 $i \leqslant q$，则 $S_i = S_{i + p} = S_{i + p - q}$，可知 $\forall i \leqslant q, p - q$ 是其一个（弱）周期。
若 $i > q$，则 $S_i = S_{i - q} = S_{i + p - q}$，可知 $\forall i > q, p - q$ 是其一个（弱）周期。
证明 $p - q$ 是 $S$ 的一个（弱）周期后，根据更相减损术的性质，最终可以迭代至 $\gcd(p, q)$ 是 $S$ 的一个（弱）周期。
- 所有强周期的长度均为最短强周期长度的倍数。
若存在一个强周期 $x$，显然有 $x\mid n$，若 $n-\pi_n\nmid x$，则 $\gcd(n-\pi_n,x)<n-\pi_n$ 也为一个强周期，与 $n-\pi_n$ 是最小强周期矛盾。
- 字符串 $S$ 存在周期当且仅当 $n - \pi_n$ 为一个周期。
必要性显然。若存在强周期 $x\mid n$，又因为 $n-\pi_n\mid x$，则 $n-\pi_n\mid n$，充分性得证。
$$\Large \rm KMP自动机$$
$\quad$在求 $\pi$ 函数的时候，我们发现这个做法是支持在线插入一个字符在末尾并计算函数值的。
$\quad$并且在做 $\rm KMP$ 的过程中我们发现，在匹配串每一位求 $\pi$ 函数时，并不关心之前匹配串的字符是什么，只关心之前的 $\pi$ 函数值和当前位的字符。
$\quad$这意味着可以对一个模式串建立一个自动机，结点 $i$ 表示当前节点的 $\pi$ 值为 $i$，新加入一个节点的出边 $c$ 指向跳 $\pi$ 时第一个能够匹配的结点。暴力建这个自动机的复杂度为 $\Theta(n^2|\Sigma|)$，因为出边需要遍历 $\Sigma$，所以不存在求 $\pi$ 函数时指针单方向移动的性质。
$\quad$但是实际上之前已经计算了从所有节点开始，以任意一个字符为出边会到哪个节点，故可以直接调用。具体规则为，记 $f_{i,c}$ 表示从 $i$ 号节点开始，字符 $c$ 会到达的节点。如果当前到达了节点 $i$ ，字符为 $c$，则如果 $c=s_{i+1}$，那么当前节点指向 $i+1$，否则指向 $f_{\pi_i,c}$. 时间复杂度 $\Theta(n|\Sigma|)$.
$\quad$同 $\rm KMP$ 算法一样，$\rm KMP$ 自动机也可以用来实现若干文本串和模式串的匹配，文本串从节点 $0$ 开始走，每次走到 $|S|$ 都完成了一次匹配。若模式串长度为 $m$，文本串长度为 $n$，数量为 $t$，则时间复杂度为 $\Theta(m+tn|\Sigma|)$.
$\quad$另一当面，$\rm KMP$ 自动机在完成普通字符串匹配时表现并不优秀，但它可以求解一些特殊的字符串匹配问题，如：
$\quad$定义 $g_1="a"$，$g_2="aba"$，$g_3="abacaba"\cdots \forall i,g_i=g_{i-1}+(char)i+g_{i-1}$. 给定另一字符串 $S$ 和整数 $k$，求 $S$ 在 $g_k$ 中的匹配次数。保证 $|S|\times k\leqslant 10^6$.
$\quad$显然题目是要求从 $0$ 号节点开始对 $g_k$ 进行匹配，经过 $|S|$ 号节点的次数是多少。
$\quad$首先对 $S$ 建立 $\rm KMP$ 自动机，记 $f_{i,j}$ 表示从 $i$ 号节点开始对 $g_j$ 进行匹配后经过 $|S|$ 号节点的次数。记 $k_{i,S}$ 表示从 $i$ 号节点开始，匹配完字符串 $S=g_i+(char)i$ 后停下来的结点，那么有 ：
$$f_{i,j}=f_{i,j-1}+[k_{i,g_{j-1}+(char)(j-1)}=|S|]+f_{k_{i,g_{j-1}+(char)(j-1)},j-1}$$
$\quad$总时间复杂度 $\Theta(|S|\times k)$.
$\quad$另外，由于单次添加结点的复杂度是严格 $\Theta(|\Sigma|)$ 的，所以可以对 $\rm KMP$ 自动机进行可持久化处理，总时间复杂度 $\Theta(n|\Sigma|\log n)$.
$$\Large \rm ExKMP$$
$\quad \rm ExKMP$也被称作 $Z$ 算法，用于求字符串 $S$ 的 $Z$ 函数，即 $z_i=\rm LCP(S,S_{i\sim n})$.
$\quad$这个算法也是类似于前缀函数 $\pi$ 的求法，我们同样是利用之前的信息来减少计算量。
$\quad$从左往右依次求每个 $z$ 函数，令 $[i, i + z_i - 1]$ 为 $i$ 的匹配段，同时维护出右端点最靠右的匹配段 $[l, r]$。
$\quad$那么我们知道有 $S_{1 \sim r - l + 1} = S_{l \sim r}, S_{i \sim r} = S_{i - l + 1, r - l + 1}(i \leqslant r), z_i \geqslant \min(r - i + 1, z_{i - l + 1})$
$\quad$在计算 $z_i$ 时，分以下三种情况：
若 $i \leqslant r, z_{i - l + 1} < r - i + 1$ 那么显然有 $z_i = z_{i - l + 1}$。
若 $i \leqslant r, z_{i - l + 1} \geqslant r - i + 1$，那么我们就从 $r + 1$ 开始暴力匹配前缀。
若 $i > r$，那么直接从 $i$ 开始暴力匹配前缀。
$\quad$不难发现复杂度来源在于 $2, 3$ 情况，但可以发现右端点最靠右的匹配段的右端点总是在这两种情况下向右移动，而总移动量不超过 $n$，因此复杂度是 $\Theta(n)$ 的。
$\quad$如果要求 $z_i = \rm LCP(T, S_{i \sim n})$ 话，就类似于 $\rm KMP$ 的做法，构造一个 $T # S$ 的串去求 $z$ 函数即可。
$$\Large \rm 习题$$
$\large \rm [NOI2014]动物园$
$\quad \rm ExKMP+$ 差分。
$\quad$对于每个 $i$，计算后缀 $S_{i\sim n}$ 与 $S$ 的 $\rm LCP$，考虑在后一个 $\rm Border$ 的左端点 $i$ 处统计答案。
$\quad$令最长公共前缀的四个端点分别为 $L,R,L',R'$，分两种情况讨论：
当 $R<L'$ 时，区间 $[L',R']$ 答案 $+1$.
当 $R\geqslant L'$ 时，区间 $[L',R]$ 答案 $+1$.
$\quad$区间 $+1$ 可以使用差分实现。
$\quad$时间复杂度 $\Theta(n)$.
$\large \rm [CF808G]Anthem~of~Berland$
$\quad$对模式串建立 $\rm KMP$ 自动机。
$\quad$令 $f_{i,j}$ 表示对字符串匹配到第 $i$ 位时，跳到自动机的 $j$ 号点匹配的次数最大值，转移显然。
$\quad$由于 $\rm DP$ 空间开不下，需要使用滚动数组。
$\quad$时间复杂度 $\Theta(|S||T||\Sigma|)$.
$\large \rm [CF1051E]Vasya~and~Big~Integers$
$\quad \rm ExKMP+$前缀和优化 $\rm DP$。
$\quad$记 $f_i$ 表示 $a_{1\sim i}$ 有多少种合法的划分方案，显然有一个 $\Theta(n^2)$ 的暴力 $\rm DP$，即往前枚举转移点 $j$，判断转移是否合法后累加即可。
$\quad$观察到合法的转移点是一段连续的区间，若令 $len_l$ 和 $len_r$ 分别表示两限制字符串的长度，显然对于满足 $len_l<i-j<len_r$ 的转移点 $j$，这个转移都是合法的，现在的问题在于判断当 $j=i-len_l$ 或 $j=i-len_r$ 的时候转移是否合法。
$\quad$考虑用 $\rm ExKMP$ 对任意一个 $i$， 求 $\rm LCP(s_{i\sim n},l)$ 和 $\rm LCP(s_{i\sim n},r)$，这样就可以快速求出 $s_{i-len_l+1\sim i}$ 与 $l$ 的最长公共前缀 $zl_{i-len_l+1}$，并通过比较 $s_{i-len_l+1+z_{i-len_l+1}}$ 与 $l_{z_{i-len_l+1}+1}$ 的大小判断当 $j=i-len_l$ 时转移是否合法，同理，当 $j=i-len_r$ 时转移是否合法也可以通过相同方式判断。
$\quad$这样，合法转移点的区间就在 $\Theta(1)$ 的时间内求出来了，剩下的用前缀和记录一下即可。需要注意的是，由于不能出现前导零，所以当转移点的后一位为 '$0$' 时不能将其加入前缀和数组。
$\quad$总时间复杂度 $\Theta(n)$.