字符串 | Typescript-Algorithms

一、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]≥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. 查找给定哈希值的子串做了，对理解多项式哈希的计算方法有帮助。

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

五、最小表示法

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

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

推荐先完成 1163. 按字典序排在最后的子串。

六、字典树

见数据结构题单第六章。

七、AC 自动机

AC 自动机 = 字典树 + KMP。

由于这些题目也可以用其他算法（字符串哈希等）解决，难度分仅供参考。

八、后缀数组/后缀自动机

由于这些题目也可以用其他算法（字符串哈希等）解决，难度分仅供参考。

九、子序列自动机

上面都是和子串相关的算法，本节是和子序列相关的算法：子序列自动机。

虽然名字有些高大上，但实际上只是预处理 ≥i 的最近字母 c 的下标而已。

见讲解中的「进阶问题」。

十、其他

3485. 删除元素后 K 个字符串的最长公共前缀 2290 LCP 的性质
466. 统计重复个数做到 O(∣s1∣+∣s2∣)

关联题单

数据结构题单中的「六、字典树（trie）」。
滑动窗口与双指针题单中的「§4.2 判断子序列」。
贪心题单中的「三、字符串贪心」。

算法题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

如果你发现有题目可以补充进来，欢迎评论反馈。