ThinkLab

KMP 算法（Knuth-Morris-Pratt 算法）是一种高效的字符串匹配算法。相较于传统的暴力匹配方法，KMP 算法的核心优势在于：在发生不匹配时，主串（被搜索的文本）的指针不需要回退。通过充分利用模式串（待搜索的字符串）自身的结构信息，算法能够计算出模式串应该回退到的最佳位置，从而将匹配过程的时间复杂度降低至线性级别。

以下是基于 KMP 算法核心思想、匹配规则、数据表构建以及代码实现的详细学习笔记。

1. 传统暴力匹配的痛点与 KMP 的改进思路

在传统的字符串匹配过程中（例如在主串 abbaabbaaba 中寻找模式串 abbaaba），采取的是逐字符比对的策略。

当主串和模式串在第 7 个字符发生不匹配时，传统做法会将主串的指针回退到第 2 个字符，模式串的指针回退到开头，然后重新开始下一轮比较。
这种“发生不匹配，双双回退”的机制导致了大量重复且不必要的字符比较，效率低下。

KMP 的核心改进目标：发生不匹配时，主串自身不回退。为了实现主串不回退，模式串必须回退得尽可能少，并且模式串回退后的前置部分必须与主串当前位置之前的部分完全重合。

2. 核心概念：真前缀与真后缀的最大匹配

为了找到模式串发生不匹配时应该回退的最佳位置，需要分析已经成功匹配的子字符串。KMP 算法引入了“真前缀”与“真后缀”的概念：

真前缀：包含首字符但不包含尾字符的所有子字符串。
真后缀：包含尾字符但不包含首字符的所有子字符串。

原理解析示例：假设在模式串的某个字符处发生不匹配，而前面已经成功匹配的子字符串为 abbaab。为了让主串不回退，需要用 abbaab 的头部去匹配 abbaab 的尾部，找到最长的相同片段：

abbaab 的真前缀有：a, ab, abb, abba, abbaa
abbaab 的真后缀有：b, ab, aab, baab, bbaab
最长匹配：真前缀和真后缀中最长的相同字符串是 ab，长度为 2。

这意味着，当在 abbaab 之后的字符发生不匹配时，模式串可以安全地回退到第 3 个字符（即索引为 2 的位置），因为前面的 ab 已经与主串天然对齐。

3. 构建最大匹配数表（Next 数组）

由于发生不匹配时，主串前方已经匹配的片段就是模式串的前缀，因此“寻找回退位置”这一计算过程仅与模式串本身有关。在实际执行搜索之前，可以对模式串进行预处理：针对模式串的每一个子字符串 [0...i]，计算出其“相匹配的真前缀与真后缀中，最长的字符串的长度”。这张表通常被称为部分匹配表（Partial Match Table）或 Next 数组。

查表与状态转移推导示例：以模式串 abababzabababa 为例，手动推导其最大匹配数表：

子字符串尾字符	a	b	a	b	a	b	z	a	b	a	b	a	b	a
最大匹配数	0	0	1	2	3	4	0	1	2	3	4	5	6	?

如何计算最后一个 ? 的值？

观察其前一个子字符串 abababzababab，它的真前缀和真后缀最大匹配了 6 个字符（即 ababab）。
现在加入末尾的新字符 a，需要判断它是否能和前缀的第 7 个字符（z）匹配。显然 a 不等于 z，匹配断裂。
此时不能直接重新开始，而是寻找次大匹配。次大匹配必定存在于最大匹配 ababab 的内部。
直接查表可知，ababab（表索引为 5）的最大匹配数是 4（即 abab）。
继续用这个次大匹配 abab 之后的字符（即模式串索引为 4 的 a）与新字符 a 进行比较。两者相等！
因此，? 处的值为次大匹配数 4 加上 1，即 5。

这个寻找“次大匹配”的过程，本质上就是 KMP 算法中最核心的回溯思想，通过查已生成的表来避免重复计算。

4. 算法代码实现

以下是 Java 版本的代码实现，分为匹配表构建和主搜索逻辑两部分。

4.1 预处理：计算最大匹配数表

// 构造模式串 pattern 的最大匹配数表
int[] calculateMaxMatchLengths(String pattern) {
    int[] maxMatchLengths = new int[pattern.length()];
    int maxLength = 0;
    
    // 从索引 1 开始，因为单字符的真前缀和真后缀为空，匹配数必然为 0
    for (int i = 1; i < pattern.length(); i++) {
        // ① 发生不匹配时，利用已构建的表进行回退，寻找次长匹配
        while (maxLength > 0 && pattern.charAt(maxLength) != pattern.charAt(i)) {
            maxLength = maxMatchLengths[maxLength - 1]; 
        }
        // ② 如果字符匹配成功，最大匹配长度加 1
        if (pattern.charAt(maxLength) == pattern.charAt(i)) {
            maxLength++; 
        }
        // 记录当前子字符串的最大匹配数
        maxMatchLengths[i] = maxLength;
    }
    return maxMatchLengths;
}

4.2 搜索匹配逻辑

主匹配过程与表的构建过程高度相似。

// 在文本 text 中寻找模式串 pattern，返回所有匹配的位置开头
List<Integer> search(String text, String pattern) {
    List<Integer> positions = new ArrayList<>();
    // 获取模式串的匹配表
    int[] maxMatchLengths = calculateMaxMatchLengths(pattern);
    int count = 0; // 记录当前已经匹配的模式串长度
    
    for (int i = 0; i < text.length(); i++) {
        // 不匹配时，模式串指针根据匹配表回退，主串指针 i 不变
        while (count > 0 && pattern.charAt(count) != text.charAt(i)) {
            count = maxMatchLengths[count - 1];
        }
        // 字符匹配时，匹配长度加 1
        if (pattern.charAt(count) == text.charAt(i)) {
            count++;
        }
        // 当完整匹配到整个模式串时，记录起始位置，并重置模式串指针以寻找下一个匹配
        if (count == pattern.length()) {
            positions.add(i - pattern.length() + 1);
            count = maxMatchLengths[count - 1];
        }
    }
    return positions;
}

4.3 复杂度分析

KMP 算法的性能极其优秀，其时间复杂度为线性关系。

在 calculateMaxMatchLengths 函数中，maxLength 在整个 for 循环中最多增加 pattern.length() - 1 次。
由于 maxLength 不能为负数，因此控制回退的 while 循环（导致 maxLength 减小）在整个外层 for 循环的生命周期内，总共执行的次数也不可能超过 pattern.length() - 1 次。
同理，search 搜索函数中的 count 增减逻辑也遵循同样的规律。
综合得出，匹配算法的时间复杂度为线性级别（$O(N + M)$，其中 $N$ 为主串长度，$M$ 为模式串长度）。

5. 总结与延伸

无回退机制：当匹配失败时，算法总能根据预先计算的信息，让模式串回退到合理的位置，从而彻底避免了被搜索文本的回退。
信息利用换取效率：在字符串比较领域，模式串预处理提供的信息越多，后续搜索过程的计算复杂度就越低。
技术延伸：KMP 侧重于挖掘模式串自身的信息；如果在某些场景下，能够提供更多关于 被搜索文本（主串） 的信息，同样可以极大降低计算复杂度。例如 Trie 树（字典树） 就是一种通过对海量文本数据建立前缀索引，从而实现高效多模式匹配的经典数据结构。

KMP算法