算法刷题系列（二十）：子串匹配——利用已知前缀信息

算法刷题系列（二十）：子串匹配——利用已知前缀信息

前面几篇使用前缀和保存数值累计信息。本篇在字符串中也利用“前缀”，但含义不同：KMP 保存模式串前缀与后缀的相等关系，在失配时避免从头比较已经确认过的字符。

我们要解决的问题是：在文本 text 中查找模式串 pattern 第一次出现的位置。朴素方法可能反复比较同一段字符；KMP 通过前缀函数将总比较次数控制在 O(n + m)。

一、朴素匹配为何会重复工作

文本 aaaaab 与模式 aaaab 比较时，前面连续多个 a 都匹配，最后才发现字符不同。朴素算法把起点右移一格后，又从模式开头重新比较这些 a。

但已经知道一段后缀与模式前缀相同，可以把模式直接移动到仍有可能匹配的位置。

二、前缀函数（LPS）

对模式串的每个位置 i，定义 lps[i] 为：

pattern[0..i] 的最长真前缀长度，且该前缀同时也是这个子串的后缀。

例如模式 ababaca 的部分 LPS 值：

字符：a b a b a c a
LPS ：0 0 1 2 3 0 1

匹配过程中，若 pattern[j] 与当前文本字符失配，不需要把 j 清零，而是回退到 lps[j - 1]。这表示保留仍可能匹配的那段前缀。

三、KMP 的扫描状态

维护文本索引 i 和模式索引 j：

• 若字符相同，两者都前进；
• 若失配且 j > 0，令 j = lps[j - 1]，文本索引不动；
• 若失配且 j == 0，文本索引前进；
• 若 j 到达模式长度，匹配开始位置为 i - j。

这确保文本索引只向右移动，模式索引依据 LPS 回退。

四、Java 实现

以下代码按 Java char（UTF-16 代码单元）进行比较和返回索引。ASCII 示例下与按码点索引的实现一致。

public class KmpSearch {
    public static int indexOf(String text, String pattern) {
        if (text == null || pattern == null) {
            throw new IllegalArgumentException("arguments must not be null");
        }
        if (pattern.isEmpty()) {
            return 0;
        }

        int[] lps = buildLps(pattern);
        int textIndex = 0;
        int patternIndex = 0;
        while (textIndex < text.length()) {
            if (text.charAt(textIndex) == pattern.charAt(patternIndex)) {
                textIndex++;
                patternIndex++;
                if (patternIndex == pattern.length()) {
                    return textIndex - patternIndex;
                }
            } else if (patternIndex > 0) {
                patternIndex = lps[patternIndex - 1];
            } else {
                textIndex++;
            }
        }
        return -1;
    }

    private static int[] buildLps(String pattern) {
        int[] lps = new int[pattern.length()];
        int matched = 0;
        for (int i = 1; i < pattern.length();) {
            if (pattern.charAt(i) == pattern.charAt(matched)) {
                lps[i] = ++matched;
                i++;
            } else if (matched > 0) {
                matched = lps[matched - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
        return lps;
    }
}

五、Python 实现

def index_of(text: str, pattern: str) -> int:
    if text is None or pattern is None:
        raise ValueError("arguments must not be None")
    if pattern == "":
        return 0

    lps = [0] * len(pattern)
    matched = 0
    index = 1
    while index < len(pattern):
        if pattern[index] == pattern[matched]:
            matched += 1
            lps[index] = matched
            index += 1
        elif matched > 0:
            matched = lps[matched - 1]
        else:
            index += 1

    text_index = 0
    pattern_index = 0
    while text_index < len(text):
        if text[text_index] == pattern[pattern_index]:
            text_index += 1
            pattern_index += 1
            if pattern_index == len(pattern):
                return text_index - pattern_index
        elif pattern_index > 0:
            pattern_index = lps[pattern_index - 1]
        else:
            text_index += 1
    return -1

assert index_of("ababcabcabababd", "ababd") == 10
assert index_of("aaaaab", "aaab") == 2
assert index_of("abc", "d") == -1
assert index_of("abc", "") == 0
assert index_of("", "a") == -1

六、正确性直觉与复杂度

当匹配到 j 个字符后失配，已知模式的前 j 个字符等于文本末尾的 j 个字符。lps[j - 1] 是这段已匹配部分中仍能与模式开头对齐的最长长度。回退到该长度不会跳过可能的匹配。

LPS 数组构建耗时 O(m)，扫描文本耗时 O(n)，额外空间 O(m)。整个过程不回退文本索引，因此总时间为 O(n + m)。

七、常见错误

1. 失配时总把模式索引设为 0：会退化为朴素比较。
2. 更新模式索引后也增加文本索引：应先用当前文本字符尝试新的候选前缀。
3. 把 lps[i] 定义成包含整个子串的前缀：它必须是真前缀，不能等于整个子串。
4. 成功匹配后访问 pattern[pattern.length]：匹配长度达到模式长度时应立即返回或明确继续策略。
5. 忽略空模式串语义：本实现约定空模式在位置 0 匹配。
6. 混淆字符单位与索引单位：Java 返回 UTF-16 代码单元索引，Python 返回码点索引。

小结

KMP 的重点不是背一张 LPS 表，而是理解失配时仍可复用的前缀长度。LPS 让算法跳过必然重复的比较，从朴素匹配的最坏 O(nm) 降到 O(n + m)。