字符串匹配：KMP算法、Rabin-Karp与经典例题

字符串匹配，说白了就是在一个长字符串里找一段短字符串。听起来简单吧？但真做起来，坑可不少。我记得刚入行那会儿，写了个暴力匹配就上线了，结果数据量一上来，直接超时。从那以后，我再也不敢小看字符串匹配了。

今天咱们聊聊三种主流方案：暴力匹配、KMP、Rabin-Karp。重点放在后两个，因为面试和工程里它们才是主角。

暴力匹配——最直观但最慢

先看个最简单的思路：从主串的每个位置开始，逐个字符去比。匹配不上就往后挪一位，继续比。

// 暴力匹配示例
public int bruteForce(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        while (j < m && text.charAt(i + j) == pattern.charAt(j)) {
            j++;
        }
        if (j == m) return i; // 匹配成功
    }
    return -1;
}

时间复杂度是 O(n*m)。数据量小的时候还行，但一旦文本长度上万、模式串再长点，立马就扛不住了。我有个朋友在日志分析系统里用过这个，结果一次查询跑了十几秒……嗯，后来他换了KMP。

KMP算法——利用已匹配信息加速

KMP的核心思想其实很简单：匹配失败时，不回溯主串指针，而是利用已经匹配的部分，把模式串尽量往右推。

怎么推？靠一个叫 next 的数组。这个数组记录了模式串每个位置之前的最长相同前后缀长度。

next数组的构建

// 构建next数组
public int[] getNext(String pattern) {
    int m = pattern.length();
    int[] next = new int[m];
    next[0] = -1; // 第一个字符匹配失败，直接移动主串
    int i = 0, j = -1;
    while (i < m - 1) {
        if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j]; // 回溯
        }
    }
    return next;
}

这里有个细节：next[0] = -1 表示第一个字符就匹配不上时，主串和模式串都要移动。我刚开始学的时候，老是把 -1 和 0 搞混，后来画了个图才彻底明白。

KMP匹配过程

public int kmpSearch(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    if (m == 0) return 0;
    int[] next = getNext(pattern);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
            i++;
            j++;
        } else {
            j = next[j]; // 模式串右移
        }
    }
    if (j == m) return i - j;
    return -1;
}

时间复杂度降到了 O(n+m)。你想想看，如果文本有 10 万字符，模式串 1000 字符，暴力可能要跑 1 亿次比较，KMP 只需要 10 万次左右。差距就是这么大。

Rabin-Karp算法——用哈希加速

Rabin-Karp 的思路更暴力一点：把模式串算出一个哈希值，然后在主串里滑动窗口，每次算一下子串的哈希，跟模式串的哈希比。哈希相同再逐个字符确认。

关键是怎么快速计算滑动窗口的哈希？用滚动哈希：

// Rabin-Karp 简化版
public int rabinKarp(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    if (m > n) return -1;
    int base = 256; // 字符集大小
    int mod = 101;  // 大质数
    int hashP = 0, hashT = 0, h = 1;
    // 计算 base^(m-1) % mod
    for (int i = 0; i < m - 1; i++) {
        h = (h * base) % mod;
    }
    // 计算模式串和第一个窗口的哈希
    for (int i = 0; i < m; i++) {
        hashP = (hashP * base + pattern.charAt(i)) % mod;
        hashT = (hashT * base + text.charAt(i)) % mod;
    }
    // 滑动窗口
    for (int i = 0; i <= n - m; i++) {
        if (hashP == hashT) {
            // 哈希相同，逐个字符确认
            int j = 0;
            while (j < m && text.charAt(i + j) == pattern.charAt(j)) j++;
            if (j == m) return i;
        }
        if (i < n - m) {
            // 滚动更新哈希
            hashT = (base * (hashT - text.charAt(i) * h) + text.charAt(i + m)) % mod;
            if (hashT < 0) hashT += mod;
        }
    }
    return -1;
}

平均时间复杂度是 O(n+m)，但最坏情况（哈希冲突太多）会退化到 O(n*m)。不过实际工程中，选好哈希参数，冲突概率很低。

经典例题：实现 strStr()

LeetCode 第 28 题，实现 strStr()，就是让你在 haystack 里找 needle。这道题用 KMP 或 Rabin-Karp 都能过，但面试官通常希望你写出 KMP。

我建议你两种都练熟。为什么呢？因为有些场景下 Rabin-Karp 更灵活——比如你要同时匹配多个模式串，Rabin-Karp 可以一次搞定，KMP 就得一个个来。

三种算法对比

知识体系总览

下面这张图帮你理清本章的核心逻辑：

三种算法各有千秋。我个人最常用的是 KMP，因为它稳定、可控，面试也最爱考。但如果你在做文本搜索引擎，Rabin-Karp 的多模式匹配能力会让你爱不释手。

好了，字符串匹配这块儿就聊到这儿。代码多敲几遍，尤其是 KMP 的 next 数组，画图推一遍比看十遍都管用。