算法 - KMP 字符串匹配

Posted on

1. 题目

给定字符串 haystack 和 needle，返回 needle 在 haystack 中第一次出现的下标，若不存在返回 -1。要求优于暴力的 O(m×n)。

示例:

1
2
3
4
5
输入: haystack = "sadbutsad", needle = "sad"
输出: 0

输入: haystack = "leetcode", needle = "leeto"
输出: -1

2. 解题思路

暴力匹配在文本串上每失配一次就把模式串整体后移一位、指针回到开头，产生大量重复比较。KMP 的核心：利用「模式串自身的重叠信息」，失配时主串指针不回退，模式串指针跳到最长可用位置。

2.1 前缀函数（next / lps 数组）

定义 lps[i] = 子串 needle[0..i] 的最长相等真前后缀长度（proper prefix 同时是 suffix）。

例如 needle = "abab"：

  • lps = [0, 0, 1, 2]
  • "abab" 前 4 个字符分别的最长相等前后缀："a"->0、"ab"->0、"aba"->"a"=1、"abab"->"ab"=2。

2.2 构建 lps（也是双指针）

len 表示当前已匹配的前缀长度：

  • needle[i] === needle[len] → lps[i] = ++len; i++。
  • 不等且 len > 0 → len = lps[len-1]（回溯到次长前后缀，i 不动）。
  • 不等且 len === 0 → lps[i] = 0; i++。

2.3 匹配

主串 j、模式串 i 双指针，失配时 i = lps[i-1]（不回退 j），直到 i === needle.length 命中。

  • 时间复杂度：O(m + n)；空间复杂度：O(n)（lps 数组）。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
function buildLPS(pattern: string): number[] {
    const n = pattern.length;
    const lps = new Array(n).fill(0);
    let len = 0; // 前一个最长前后缀长度
    let i = 1;

    while (i < n) {
        if (pattern[i] === pattern[len]) {
            lps[i++] = ++len;
        } else if (len > 0) {
            len = lps[len - 1]; // 回溯，i 不前进
        } else {
            lps[i++] = 0;
        }
    }
    return lps;
}

function strStr(haystack: string, needle: string): number {
    const m = haystack.length;
    const n = needle.length;
    if (n === 0) return 0;

    const lps = buildLPS(needle);
    let i = 0; // haystack 指针（永不回退）
    let j = 0; // needle 指针

    while (i < m) {
        if (haystack[i] === needle[j]) {
            i++;
            j++;
            if (j === n) return i - j; // 完全匹配
        } else if (j > 0) {
            j = lps[j - 1]; // 部分匹配，跳回
        } else {
            i++; // j=0 直接前移
        }
    }
    return -1;
}

console.log(strStr("sadbutsad", "sad"));       // 0
console.log(strStr("ababcababc", "abc"));       // 2
console.log(strStr("leetcode", "leeto"));       // -1
console.log(buildLPS("abab"));                  // [0,0,1,2]

4. 面试延伸

  • 理解 j = lps[j-1] 的精髓：它把「已经匹配过的前缀」当作可复用的后缀，让 i 全程不回退，这是 KMP 达到线性的根本。
  • 最小覆盖子串 / 重复子串（459）：用 n - lps[n-1] 判断字符串是否由某最短单元重复构成。
  • Rabin-Karp（滚动哈希）：多模式匹配 / 查重更友好，平均线性但要处理哈希冲突。
  • BM 算法：编辑器/grep 的实战主力（坏字符 + 好后缀规则，实际常常比 KMP 快），面试聊到工程落地可提。
  • 手推 lps 时一定举例 "aabaaab" 之类复杂串验证，别只说结论。

难度：中等 | LeetCode 28 题 | 前缀函数 / 双指针