分享丨【算法题单】字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组）

灵茶山艾府

82474

2024.10.08

14 小时前

发布于浙江

字符串字符串匹配后缀数组 C++Java Python3 周赛数据结构数据结构与算法双周赛滚动哈希力扣竞赛学习分享

字符串题单字符串算法灵神灵茶山艾府

一、KMP（前缀的后缀）

KMP 原理讲解

定义 $s$ 的真前缀为不等于 $s$ 的前缀， $s$ 的真后缀为不等于 $s$ 的后缀。

定义 $s$ 的 $border$ 为既是 $s$ 的真前缀又是 $s$ 的真后缀的字符串。例如在 $s = aabcaa$ 中， $a$ 和 $aa$ 都是 $s$ 的 $border$ 。

对于模式串 $p$ 的每个前缀 $p [: i]$ ，计算这个前缀的最长 $border$ 长度，记在 $π$ 数组中。

利用 $π$ 数组，可以快速计算模式串 $p$ 出现在文本串 $t$ 的哪些位置上。

注： $π$ 数组的定义参考《算法导论》，国内数据结构教材通常定义为 $next$ 数组。以严蔚敏那本为例，二者的关系是 $next [i + 1] = π [i] + 1$ ，即 $π$ 数组整体右移一位，元素值加一。

模板：

Python3

Java

C++

# 在文本串 text 中查找模式串 pattern，返回所有成功匹配的位置（pattern[0] 在 text 中的下标）
def kmp(text: str, pattern: str) -> List[int]:
    m = len(pattern)
    pi = [0] * m
    cnt = 0
    for i in range(1, m):
        b = pattern[i]
        while cnt and pattern[cnt] != b:
            cnt = pi[cnt - 1]
        if pattern[cnt] == b:
            cnt += 1
        pi[i] = cnt

    pos = []
    cnt = 0
    for i, b in enumerate(text):
        while cnt and pattern[cnt] != b:
            cnt = pi[cnt - 1]
        if pattern[cnt] == b:
            cnt += 1
        if cnt == len(pattern):
            pos.append(i - m + 1)
            cnt = pi[cnt - 1]
    return pos

二、Z 函数（后缀的前缀）

注：在国内算法竞赛圈，这个算法也叫扩展 KMP。

对于字符串 $s$ ，定义 $z [i]$ 表示后缀 $s [i :]$ 与 $s$ 的 LCP（最长公共前缀）的长度，其中 $s [i :]$ 表示从 $s [i]$ 到 $s [n - 1]$ 的子串。

常用技巧是构造字符串 $pattern + s$ ，如果发现 $z [m + i] \geq m$ （ $m$ 是 $pattern$ 的长度），则说明从 $s [i]$ 开始的子串与 $pattern$ 匹配。

所以上面的一些 KMP 题目（子串匹配相关的），也可以用 Z 函数解决。读者可以尝试用 Z 函数解决 28. 找出字符串中第一个匹配项的下标。

模板：

Python3

Java

C++

# 计算并返回 z 数组，其中 z[i] = |LCP(s[i:], s)|
def calc_z(s: str) -> List[int]:
    n = len(s)
    z = [0] * n
    box_l = box_r = 0
    for i in range(1, n):
        if i <= box_r:
            z[i] = min(z[i - box_l], box_r - i + 1)
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            box_l, box_r = i, i + z[i]
            z[i] += 1
    z[0] = n
    return z

LCP 数组

三、Manacher 算法（回文串）

Manacher 算法可以计算以 $s [i]$ （或者 $s [i]$ 和 $s [i + 1]$ ）为回文中心的最长回文子串的长度。

此外，还可以：

判断任意子串是否为回文串。
计算从 $s [i]$ 开始的最长回文子串的长度。
计算以 $s [i]$ 结尾的最长回文子串的长度。

Z 函数和 Manacher 算法都会用到类似 Z-box 的概念，在学习时，可以对比体会。

模板代码

用到中心扩展法（及其思想）的算法题：

模板代码

四、字符串哈希

本题单的大多数题目都可以用字符串哈希解决。

推荐先把 2156. 查找给定哈希值的子串和 3756. 连接非零数字并乘以其数字和 II 做了，对理解多项式哈希的计算方法有帮助。

模板代码见我的题解，包含单模哈希和双模哈希。

小技巧：我们可以用字符串哈希比较两个子串的字典序大小。做法是二分长度，计算最长公共前缀（LCP），然后比较 LCP 的下一个字母。时间复杂度： $O (lo g n)$ 。见 3722 题。

五、最小表示法

定义循环左移操作：把字符串 $s$ 的第一个字符 $s [0]$ 移除，添加到 $s$ 的末尾。例如 $abcd$ 操作一次后得到 $bcda$ 。

问题：你可以执行任意次循环左移操作，计算你能得到的字典序最小的字符串。

注：任意次循环左移操作后，得到的字符串叫做 $s$ 的循环同构串。

// 返回 s 的字典序最小的循环同构串
// 时间复杂度 O(n)，证明见末尾
func smallestRepresentation(s string) string {
    n := len(s)
    s += s
    // 注：如果要返回一个和原串不同的字符串，初始化 i=1, j=2
    i := 0
    for j := 1; j < n; {
        // 暴力比较：是 i 开头的字典序小，还是 j 开头的字典序小？
        // 相同就继续往后比，至多循环 n 次（如果循环 n 次，说明所有字母都相同，不用再比了）
        k := 0
        for k < n && s[i+k] == s[j+k] {
            k++
        }
        if k >= n {
            break
        }

        if s[i+k] < s[j+k] { // 注：如果求字典序最大，改成 >
            // 比如从 i 开始是 "aaab"，从 j 开始是 "aaac"
            // 从 i 开始比从 j 开始更小（排除 j）
            // 此外：
            // 从 i+1 开始比从 j+1 开始更小，所以从 j+1 开始不可能是答案，排除
            // 从 i+2 开始比从 j+2 开始更小，所以从 j+2 开始不可能是答案，排除
            // ……
            // 从 i+k 开始比从 j+k 开始更小，所以从 j+k 开始不可能是答案，排除
            // 所以下一个「可能是答案」的开始位置是 j+k+1
            j += k + 1
        } else {
            // 从 j 开始比从 i 开始更小，更新 i=j（也意味着我们排除了 i）
            // 此外：
            // 从 j+1 开始比从 i+1 开始更小，所以从 i+1 开始不可能是答案，排除
            // 从 j+2 开始比从 i+2 开始更小，所以从 i+2 开始不可能是答案，排除
            // ……
            // 从 j+k 开始比从 i+k 开始更小，所以从 i+k 开始不可能是答案，排除
            // 所以把 j 跳到 i+k+1，不过这可能比 j+1 小，所以与 j+1 取 max
            // 综上所述，下一个「可能是答案」的开始位置是 max(j+1, i+k+1)
            i, j = j, max(j, i+k)+1
        }
        // 每次要么排除 k+1 个与 i 相关的位置（这样的位置至多 n 个），要么排除 k+1 个与 j 相关的位置（这样的位置至多 n 个）
        // 所以上面关于 k 的循环，∑k <= 2n，所以二重循环的总循环次数是 O(n) 的
    }
    return s[i : i+n]
}