KMP 与字符串哈希：两种字符串匹配优化

我对“KMP 与字符串哈希：两种字符串匹配优化”的理解经历过一个从会背到会用的过程。其中最明显的一点是：KMP 的 next 数组我背过不止一次，也忘过不止一次；字符串哈希写起来更短，但碰撞问题又让我不敢放心使用。后来每次看到结论，我都会追问它省掉了哪一步、又付出了什么代价，这也是这篇文章的主线。

字符串匹配里最常见的两个优化方向是 KMP 和字符串哈希。它们目标一样：减少重复比较。但思路完全不同。

KMP 依赖模式串自身的前缀信息；字符串哈希依赖把子串映射成数字摘要。

它从哪里来

Knuth、Morris 与 Pratt 在 1977 年发表 KMP 算法。它解决的关键浪费是：失配后主串指针不应回退，已经匹配的模式前缀本身就告诉我们下一次可以从哪里继续。字符串哈希则用摘要快速比较子串，但需要承担冲突风险。

两种思路

KMP 与字符串哈希

图：KMP 复用前后缀，字符串哈希复用窗口哈希

KMP 的关键：next 数组

next[i] 表示模式串 pattern[0..i] 中，最长相等真前缀和真后缀的长度。

例如：

pattern = ababa
next    = 00123

当已经匹配了 j 个字符，却在下一个字符失配时，不需要把文本指针回退，只要让 j = next[j-1]。这表示模式串跳到最长可复用前缀的位置。

int[] buildNext(String p) {
    int[] next = new int[p.length()];
    for (int i = 1, j = 0; i < p.length(); i++) {
        while (j > 0 && p.charAt(i) != p.charAt(j)) {
            j = next[j - 1];
        }
        if (p.charAt(i) == p.charAt(j)) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

KMP 匹配

int kmp(String text, String pattern) {
    if (pattern.isEmpty()) return 0;
    int[] next = buildNext(pattern);
    for (int i = 0, j = 0; i < text.length(); i++) {
        while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        if (text.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        if (j == pattern.length()) {
            return i - j + 1;
        }
    }
    return -1;
}

KMP 的时间复杂度是 O(n + m)，因为文本指针不会回退，模式指针虽然会跳转，但总回退次数受前进次数限制。

字符串哈希

字符串哈希把一个字符串映射为数字。滚动哈希可以让窗口右移时快速更新。

常见公式：

hash(s[0..k]) = s[0]*base^k + s[1]*base^(k-1) + ... + s[k]

子串哈希可以通过前缀哈希得到。

long[] prefixHash(String s, long base, long mod) {
    int n = s.length();
    long[] h = new long[n + 1];
    for (int i = 0; i < n; i++) {
        h[i + 1] = (h[i] * base + s.charAt(i)) % mod;
    }
    return h;
}

子串 [l, r) 的哈希：

long hash(long[] h, long[] pow, int l, int r, long mod) {
    return (h[r] - h[l] * pow[r - l] % mod + mod) % mod;
}

哈希冲突

字符串哈希有冲突风险。两个不同字符串可能得到相同哈希。

处理方式：

哈希相同后再做字符比较。
使用双哈希降低冲突概率。
在安全敏感场景不要把普通哈希当强校验。

算法题里有时默认概率足够小，工程里必须明确风险。

KMP 和哈希怎么选

场景	更适合
单模式精确匹配	KMP
需要严格无误判	KMP 或哈希后字符确认
大量子串比较	字符串哈希
多模式匹配	Trie / AC 自动机
回文判断	中心扩展 / Manacher / 哈希

KMP 难在前缀跳转，哈希难在冲突和取模细节。

工程场景

文章内搜索关键词。
日志中匹配固定模式。
文件内容去重。
拼写和自动补全的前置处理。
URL 路由和文本扫描。

对于中文文章，不能简单假设字符都是 ASCII。Java 的 char 是 UTF-16 代码单元，如果涉及 emoji、复杂 Unicode 字符，要更谨慎地处理码点。

常见错误

把 next[i] 理解成跳到哪个下标，而不是长度。
KMP 失配时同时回退文本指针。
哈希没有预计算幂数组。
哈希相减后忘记加 mod 防止负数。
完全忽略哈希冲突。
中文和 emoji 场景按单字节处理。

面试题

KMP 的 next 数组表示什么？
KMP 为什么文本指针不需要回退？
字符串哈希为什么可能冲突？
如何 O(1) 得到子串哈希？
单模式、多模式、回文问题分别适合什么算法？

小结

KMP 和字符串哈希都在减少重复比较。KMP 用模式串结构保证线性匹配，哈希用摘要加速子串比较。一个偏确定性，一个偏概率性。工程中选择哪个，取决于是否允许冲突、是否需要多次子串查询，以及字符集是否复杂。