模式匹配是计算机科学的一个基本问题, 在日常的开发工作中非常频繁地使用, 最常见的场景例如在编辑器中进行文本搜索, 当搜索到目标文本时需要定位到目标在文本中的相对位置, 这都属于模式匹配问题, 朴素的模式匹配使用暴力匹配 (Brute-Force) 方式, 即设置两个指针, 分别指向主串和待匹配的子串(我们之后称为「模式串」)的起始字符, 若两个指针指向的字符相等, 则将两个指针分别后移一个位置继续进行比较, 当比较不相等时, 主串的指针需要退回到起始位置的下一个位置, 并将模式串的指针复原到第一个字符的位置, 然后重复上述过程, 直到模式串的指针指向结尾(此时匹配成功)或主串的指针指向结尾(此时匹配失败), 在通常情况下, 使用朴素的暴力匹配方式并没有什么问题, 但在某些情况下, 暴力匹配方式的时间复杂度将会降低到 O(mn), 其中 m、n 分别是主串和模式串的长度, 举例来说, 假设主串为 aaaaaaaaa, 模式串为 aaab, 那么整个匹配过程如下所示

起始时, 两个指针分别指向主串的第一个字符和模式串的第一个字符, 由于二者都是 a, 所以指针分别后移, 直到对比到上图所示的位置, 发现主串和模式串的字符不相等, 于是此次匹配失败. 按照暴力匹配算法, 接下来, 主串的指针退回到上一轮的起始位置的下一个位置, 而模式串的指针退回到模式串的开头, 重复上述比较过程, 如下图所示

在第二轮匹配中, 暴力匹配算法又重复对主串的第二个、第三个、第四个字符进行对比, 而实际上这三个字符在第一轮比较中, 我们已经知道它们分别是 aaa, 暴力匹配算法没有利用已经获取到的信息, 每轮匹配都是从头开始重新进行匹配, 因此对于这个 case, 暴力匹配算法总共需要比较 9 * 4 = 36 次, 效率非常低下, KMP 和 AC 自动机便是对暴力匹配算法的一种改进, 它们的思路都在于利用已经获取到的信息以减少比较的次数, KMP 是 AC 自动机的一种特殊情况, AC 自动机是 KMP 算法的前缀树扩展, 它应用于多模式匹配问题, 相比于暴力匹配算法, KMP 可以在 O(m+n) 的复杂度内完成模式匹配任务, 本文完整讨论 KMP 和 AC 自动机的实现, 并给出 Go 代码示例

10.1 KMP 匹配

KMP 算法 是以三位发明者的名字首字母来命名的, 它可以在 O(m+n) 的复杂度内完成模式匹配任务, 它的设计思路在于利用在前面失败的比较中已经得到的部分信息以减少下一轮匹配的比较次数, 本质上讲, KMP 算法实际上是动态规划的思路, 在 KMP 算法中, 当主串指针指向的字符和模式串指针指向的字符不相等(即 "失配")时, 主串的指针不需要回溯到起始位置的下一个位置, 而是将模式串向右 "滑动" 尽可能长的一段距离, 然后继续进行比较. 举例来说, 假设主串为 ABCDABEABCDABCDABDK, 模式串为 ABCDABD, 起始状态如下所示

两个指针分别指向主串和模式串的第一个字符, 由于它们相等, 所以指针分别后移, 重复上述过程, 直到指针移动到下图所示的位置

此时, 主串和模式串指针对应的字符不相等, 按照暴力匹配算法, 此时主串的指针应该回退到字符 B 上, 而模式串的指针应该回退到模式串的开头, 即字符 A 上, 然后继续进行比较, 而在 KMP 算法中, 我们保持主串的指针不动, 将模式串向右滑动 4 个字符的距离(滑动距离的确定我们将在下文讨论), 如下图所示:

移动过后, E 与 C 仍不相等, 此时将模式串继续向右 "滑动" 2 个字符的距离, 继续进行比较, 如下图所示

此时, 比较仍不相等, 接下来, 将主串的指针后移一位, 继续与模式串进行对比

当字符相等时, 两个指针分别后移, 直到当主串指针指向 C, 模式串指针指向 D 时, 二者不相等

此时, 将模式串向右 "滑动" 4 个字符的继续, 继续进行比较

在这轮比较中, 直到模式串的指针移动到末尾, 模式串与主串的指针指向的字符都是相等的, 此时匹配成功, 匹配任务完成。可以看到 KMP 算法相比于朴素的暴力匹配算法大大减少了比较的次数, 当发生 "失配" 时, 主串的指针不需要回退, 而是将模式串向右 "滑动" 尽可能的距离继续进行比较, 从而提高匹配效率, "滑动" 距离的确定是 KMP 算法的核心

10.2 部分匹配表(Partial Match Table)

上节中我们所提到的 「滑动距离」, 实际上是一种比较形象的说法, KMP 算法对模式串维护了一个部分匹配表 (Partial Match Table) [下面简称为 PMT], PMT 的物理结构是一个数组, 它的长度与模式串的长度相等, 我们以一个实际的例子来说明如何计算与生成 PMT, 假设模式串为 ABCADAB, 那么它的 PMT 值如下

在讨论 PMT 的生成方法之前, 我们非形式化地给出几个有关字符串的定义, 我们将从字符串的某一位开始直到字符串结尾构成的子串称为字符串的后缀, 例如对于 ABCADAB, 它的后缀有 {ABCADAB, BCADAB, CADAB, ADAB, DAB, AB, B}, 特别地, 若字符串的后缀不等于其自身, 那么称该子串为字符串的真后缀, 同理我们也可以得到字符串的前缀和真前缀的概念, 在给定了真前缀和真后缀的概念之后, 我们可以基于此来得到 PMT, PMT 每一项的值实际就是从表开头到当前项构成的字符串的真前缀集合与真后缀集合的交集的最长元素的长度, 若不存在交集, 则其值为 0, 具体来分析:

• 对于第一项, 字符串为 A, 它没有真前缀和真后缀, 因此 PMT[0] = 0
• 对于第二项, 字符串为 AB, 它的真前缀集合为 {A}, 真后缀集合为 {B}, 二者没有交集, 因此 PMT[1] = 0
• 对于第三项, 同理可得, PMT[2] = 0
• 对于第四项, 字符串为 ABCA, 它的真前缀集合为 {A, AB, ABC}, 真后缀集合为 {A, CA, BCA}, 二者的交集为 {A}, 只有一个元素, 其长度为 1, 因此 PMT[3] = 1

...

• 对于最后一项, 字符串为 ABCADAB, 它的真前缀集合为 {A, AB, ABC, ABCA, ABCAD, ABCADA}, 其真后缀集合为 {B, AB, DAB, ADAB, CADAB, BCADAB}, 二者的交集为 {AB}, 其长度为 2, 因此 PMT[6] = 2

因此, 要获得 PMT, 实际上就是计算字符串真前缀集合与真后缀集合交集的最长元素的长度, 有了 PMT, 当字符串匹配过程中发生 "失配" 时, 只需将模式串向后滑动 "已匹配部分的长度 - 最后一个匹配的字符项在 PMT 中的值" (例如匹配的模式串为 ABCABD, 当比较到最后一个字符 D 时发生 "失配", 根据 PMT 的计算规则可以知道, 最后一个匹配的字符 B 对应的 PMT 项的值为 2, 已匹配的字符串为 ABCAB, 长度为 5, 则模式串向右滑动的步长为 5 - 2 = 3), 然后继续进行比较, 可以看到整个过程中, 主串的指针自始至终没有发生回退, 相比于朴素的 BF 匹配, KMP 算法可以减少比较的次数

KMP 算法的正确性证明可以看《算法导论》, 此处不展开讨论, KMP 的思想比较直观, 下面给出代码示例:

package kmp

func GetNext(s string) []int {
    if len(s) == 0 {
        return []int{}
    }
    if len(s) == 1 {
        return []int{-1}
    }
    next := make([]int, len(s), len(s))
    next[0] = -1
    next[1] = 0
    for i, j := 0, 1; j < len(s)-1; {
        if i == -1 || s[i] == s[j] {
            i++
            j++
            // next[j] = i 意味着当主串的某个字符与模式串下标为 j 的字符不相等时, 主串中的该字符应与模式串中的下标为 i 的字符继续比较
            next[j] = i
        } else {
            i = next[i]
        }
    }
    return next
}

// 匹配函数
// s 是主串, p 是模式串
// 函数返回模式串在主串中的第一个位置, 若未匹配到返回 -1
func Search(s, p string) int {
    i, j := 0, 0
    // 生成部分匹配表
    next := GetNext(p)
    // i 指示主串的下标, j 指示模式串的下标
    for i < len(s) && j < len(p) {
        if j == -1 || s[i] == p[j] {
            i++
            j++
        } else {
            // 当主串中下标为 i 的字符与模式串中下标为 j 的字符不相等时
            // 主串中下标为 i 的字符应继续与 next[j] 进行比较(此时, s[i-1], s[i-2], ... s[0] 分别与 p[next[j]-1], p[next[j]-2], ... p[0] 相等)
            j = next[j]
        }
    }
    // 匹配成功
    if j == len(p) {
        return i - j
    } else {
        return -1
    }
}

10.3 AC 自动机

// 时间太晚了, 以后有时间补上