前缀函数

前缀函数通常称为 border，一个字符串 $S$ 的 border 定义为它的一个前缀子串 $t(t \ne S)$ ，满足 $t$ 既是 $S$ 的前缀，也是 $S$ 的后缀。下文的 border 均为 $S$ 的最长 border 长度。

简单来说，对于一个字符串 $S = \texttt{abcabcd}$ （下标从 $1$ 开始），它的前缀函数为 $[0, 1, 0, 1, 2, 2, 3]$ 。

计算方法

单纯暴力

从左向右遍历一遍，每次循环一次长度，每次检查遍历一遍子串，复杂度为 $O(n^3)$ 。

边界优化

从左向右遍历的过程中，子串的大小每次只会增加 $1$ ，而原先的前缀不会改变，因此 $border_i$ 的长度最多只会比 $border_{i - 1}$ 大 $1$ ，在这种情况下：

$S[i] = S[border_{i - 1} + 1] \Rightarrow S[1 \dots border_{i - 1}] = S[i - 1 - border_{i - 1} + 1 \dots i - 1] \\ \Rightarrow S[1 \dots border_{i - 1} + 1] = S[i - 1 - border_{i - 1} + 1 \dots i] \\ \Rightarrow border_i = border_{i - 1} + 1$

可见这种优化下，字符串比较次数与 border 有关，border 越长，字符串越长，而比较次数越短，根据势能分析可知，在这种情况下，字符串比较的时间复杂度为 $O(n)$ ，总共的时间复杂度为 $O(n^2)$ 。

遍历优化

不难发现，每一次失配之后，我们都会将 $border_i$ 减 $1$ ，从而造成了大量的浪费，考虑从这方面入手。

目标就是找到一个下标 $j$ ，满足 $S[1 \dots j] = S[i - j + 1 \dots i]$ ，我们可以惊奇的发现，在之前的子串 $S[1 \dots border_{i - 1}]$ 之中也存在一个 $k = border_{border_{i - 1}}$ ，满足：

$S[1 \dots k] = S[i - 1 - k + 1 \dots i - 1]$

这个 $k$ 值一定是除了 $border_{i - 1}$ 之外最大的 $j$ ，因为他本身是子串 $S[1 \dots border_{i - 1}]$ 的最大的 border，到这里操作就十分简单了，每次失配后让 $j \leftarrow border_{j}$ ，直到 $S[i] = S[j + 1]$ 或者 $j = 0$ 即可。

实现代码

for (int i = 2, j = 0; i <= m; i ++)    // i == 1 时 t 不是 s 的真子串
{
    while (j && b[i] != b[j + 1]) j = nxt[j];
    if (b[i] == b[j + 1]) j ++;
    nxt[i] = j;
}

KMP 算法

P3375 【模板】KMP - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

KMP 算法是前缀函数的典型应用。

算法思路

我们定义 $S$ 为文本串， $T$ 为模式串，要求找到 $S$ 中所有 $T$ 的位置。

这个问题可以简单地进行转化：定义 $f_i$ 表示满足 $T[1 \dots f_i] = S[i - f_i + 1 \dots i]$ 的最大值，不难发现，如果 $f_i = |T|$ ，那么 $S$ 中的位置 $i - |T| + 1$ 便是 $T$ 的一个位置。

思路十分简单，先求出 $T$ 的前缀函数，在用 $T$ 的前缀函数 $nxt[]$ 用来更新 $f_i$ 。

代码实现

// a：文本串 b：模式串 n：|a| m：|b| 下标为 1
for (int i = 2, j = 0; i <= m; i ++)
{
    while (j && b[i] != b[j + 1]) j = kmp[j];
    if (b[i] == b[j + 1]) j ++;
    kmp[i] = j;
}

for (int i = 1, j = 0; i <= n; i ++)
{
    while (j && a[i] != b[j + 1]) j = kmp[j];
    if (a[i] == b[j + 1]) j ++;
    if (j == m) cout << i - m + 1 << '\n';
}

Z 函数 / exKMP

P5410 【模板】扩展 KMP/exKMP（Z 函数） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Z 函数与前缀函数的定义相似，关于字符串 $S$ 的 Z 函数中 $z_i$ 表示满足 $S[1 \dots z_i] = S[i \dots i + z_i - 1]$ 的最大值。

计算方法

由于不同的性质，Z 函数的求法与前缀函数完全不同，采取的是类似 Manacher 的双指针递推方法。

假设我们处理完了前 $i - 1$ 个，令 $r$ 表示前 $i - 1$ 满足 Z 函数定义的最右边界， $l$ 则是与 $r$ 相对应的左边界（也就是满足 $r$ 的下标）。对于第 $i$ 个子串，有如下几种情况：

$i \gt r$ ：说明前面的处理与第 $i$ 个无关，直接暴力遍历即可。
$i \le r$ ：根据定义， $S[1 \dots z_l = S[l \dots r]$ ，然而 $i \le r$ ，那么推出 $S[i - l + 1 \dots z_l = S[i \dots r]$ ，既然如此，我们让 $z_i \leftarrow \min (z_{i - l + 1}, r - i + 1)$ ，取 $\min$ 的原因是无法保证 $r$ 的右边字符串是否仍然相等。

和 Manacher 算法一样，指针 $r$ 只会向右移动，每次更新也会更新 $r$ ，时间复杂度为 $O(n)$ 。

代码实现

void Z_Function()    // 下标为 1
{
    z[1] = m;	// i == 1 时子串是其本身
    for (int i = 2, l = 0, r = 0; i <= m; i ++)
    {
        int k = i > r ? 0 : min(z[i - l + 1], r - i + 1);	// 分类讨论
        while (i + k <= m && b[i + k] == b[k + 1]) k ++;
        z[i] = k;
        if (i + k - 1 > r) l = i, r = i + k - 1;	// 更新 l 和 r
    }
}

exKMP

求出字符串 $S$ 与字符串 $T$ 中每一个后缀的 LCP（Longest Common Prefix）。

采取与 KMP 算法类似的思想，先预处理出 $T$ 与其本身的 Z 函数，再用这个 Z 函数更新 $S$ 串即可。

代码实现

// a：S b：T n：|S| m：|T|
void exKMP()
{
    for (int i = 1, l = 0, r = 0; i <= n ; i ++)
    {
        int k = i > r ? 0 : min(z[i - l + 1], r - i + 1);
        while (i + k <= n && a[i + k] == b[k + 1]) k ++;
        p[i] = k, ansp ^= (p[i] + 1) * i;
        if (i + k - 1 > r) l = i, r = i + k - 1;
    }
}