字符串匹配算法

KMP 是面试中最常考的字符串算法。关键不是背代码，而是理解为什么 KMP 不用回退文本指针，以及前缀函数到底在表达什么。

面试考察点

面试官通过这道题想考察：
1. 你是否能解释暴力匹配的缺点
2. 你是否能理解 KMP 的核心思想
3. 你是否能解释前缀函数的含义
4. 你是否能手写 KMP

---

一、暴力匹配

1.1 暴力匹配的问题

面试官追问："暴力匹配为什么慢？"

文本 T: "ABABABCABAABABAC"
模式 P: "ABABAC"

暴力匹配：

T[0] 和 P[0] 匹配 ✓
T[1] 和 P[1] 匹配 ✓
T[2] 和 P[2] 匹配 ✓
...
T[5] 和 P[5] 不匹配！

怎么办？暴力解法：
T 的指针回退到 T[1]
从 P[0] 重新开始

T:    A B A B A B C A B A A B A B A C
P:    A B A B A C
       ↑ 不匹配！

最坏情况：
T = "AAAAAAAAAB"
P = "AAAAB"

每次都要回退 T 的指针
时间复杂度：O(n × m)

1.2 暴力匹配为什么浪费？

关键观察：

T:    A B A B A B C A B A A B A B A C
P:    A B A B A C
                 ↑
           匹配到 P[5] 时失败

T 的指针回退到了 T[1]

但我们知道：
- T[0..5] = "ABABAB"
- P[0..5] = "ABABAC"
- 已经匹配了 T[1..4] = P[0..3]

为什么要回退到 T[1]？
从 T[1] 开始意味着 T[1..4] 要重新和 P 比较

但 T[1..4] = "BABA"，而 P[0..3] = "ABAB"
它们根本不可能匹配！（开头不同）

暴力匹配浪费了已知的信息！

---

二、KMP 算法

2.1 KMP 的核心思想

面试官追问："KMP 怎么避免回退？"

KMP 的核心：不回退 T 的指针！

利用已匹配的信息：
当 P[5] 匹配失败时，我们知道 T[0..5] = "ABABAB"，P = "ABABAC"

已经匹配的 "ABABA" 有什么特点？
- 前缀 "ABA" 和后缀 "ABA" 相同！

所以可以这样：

T:    A B A B A B C A B A A B A B A C
P:    A B A B A C
              ↑
        P[5] 匹配失败

T[0..5] = "ABABAB"
前缀 "ABA" 和后缀 "ABA" 相同！

所以直接把 P 向右滑到：

T:    A B A B A B C A B A A B A B A C
P:        A B A B A C
          ↑       ↑
        P[0]   原来的 P[2]

让 P[0] 对齐 T[2]（跳过已知的匹配）

关键：不需要回退 T 的指针！

2.2 前缀函数（核心）

面试官追问："什么是前缀函数？"

前缀函数（Failure Function）：求模式串每个位置的最长相等前后缀

举例：

P = "ABABAC"

求每个位置的最长相等前后缀（不包括本身）：

位置 0 ('A')：没有前缀后缀 → 0
位置 1 ('AB')：没有相等前后缀 → 0
位置 2 ('ABA')：前缀"A" = 后缀"A" → 1
位置 3 ('ABAB')：前缀"AB" = 后缀"AB" → 2
位置 4 ('ABABA')：前缀"ABA" = 后缀"ABA" → 3
位置 5 ('ABABAC')：没有相等前后缀 → 0

前缀函数：π = [0, 0, 1, 2, 3, 0]

有什么用？
当匹配失败时，查前缀函数，
确定 P 应该滑动到哪里！

2.3 KMP 匹配过程

T = "ABABABCABAABABAC"
P = "ABABAC"
π = [0, 0, 1, 2, 3, 0]

匹配：

Step 1: T[0..4] = "ABABA"，P[0..4] = "ABABA" 匹配
        T[5] = 'B'，P[5] = 'C' 不匹配

        T:    A B A B A B C A B A A B A B A C
        P:    A B A B A C
                          ↑
                     π[5] = 0

Step 2: P 滑动，P[0] 对齐 T[2]

        T:    A B A B A B C A B A A B A B A C
        P:        A B A B A C
                  ↑       ↑
              P[0]    原来的 P[2]

Step 3: 继续匹配...

为什么这样滑动是对的？
因为 π[5] = 0 表示没有相等前后缀
所以 P[0] 不能和 T[2] 之后的任何位置匹配
（因为 T[0..4] 的后缀不可能是 P 的前缀）

---

三、面试总结

KMP 核心要点

┌─────────────────────────────────────────────────┐
│                    KMP 核心                       │
├─────────────────────────────────────────────────┤
│                                                  │
│  核心思想：不回退 T 的指针，利用已匹配的信息       │
│                                                  │
│  前缀函数：                                      │
│  - 位置 i 的最长相等前后缀长度                   │
│  - 匹配失败时，确定 P 滑动的位置                 │
│                                                  │
│  时间复杂度：O(n + m)                            │
│                                                  │
│  vs 暴力匹配：                                   │
│  - 暴力：回退 T 的指针，O(nm)                   │
│  - KMP：不回退，利用信息，O(n+m)               │
│                                                  │
└─────────────────────────────────────────────────┘

面试能加分的回答

1. 能解释为什么 KMP 快
   "暴力匹配回退了 T 的指针，浪费了已知信息，
    KMP 通过前缀函数，让 P 滑动到正确的位置"

2. 能解释前缀函数
   "前缀函数表示位置 i 的最长相等前后缀，
    当匹配失败时，查这个值就知道 P 该滑到哪里"

3. 能手写前缀函数
   "用递推：如果 s[i] == s[π[i-1]]，则 π[i] = π[i-1] + 1"

---

相关题目

• LeetCode 28 - 实现 strStr() - KMP 实现
• LeetCode 459 - 重复的子字符串 - 前缀函数应用