前言

KMP算法（Knuth-Morris-Pratt）是字符串匹配领域的“灵魂算法”。它的核心智慧在于：当匹配失败时，利用已经匹配成功的部分信息，让模式串“智能地”向右滑动，而文本指针绝不回溯。

为了让你彻底理解，我们从痛点出发，逐步拆解。

正文

1. 暴力匹配的痛点

在暴力匹配中，若文本串 S 为 AAAAAB，模式串 P 为 AAAAB： 当匹配到 S[4]=A 与 P[4]=B 失配时，暴力法会把模式串整体右移一位，从 S[1] 重新开始比较。 这意味着 i（文本指针）发生了回溯，之前比较过的字符又被重复比较，时间复杂度高达 O(n*m)。

KMP的绝招就是：i 永远不后退，只让 j（模式串指针）回退到合适的位置。

2. 核心武器：最长相等前后缀（LPS / Next数组）

为了让 j 知道该回退到哪里，我们需要预处理模式串，生成一个 Next数组（也叫部分匹配表，PMT）。

• 定义：next[i] 表示 模式串 P[0...i] 这个子串中，最长的相等真前缀与真后缀的长度。
• 真前缀/后缀：不包含字符串本身的前缀/后缀。

举个经典例子：模式串 P = "ABABC"

所以 next = [0, 0, 1, 2, 0]。

3. 匹配时的“跳跃”逻辑

当我们在文本 S 中匹配 P 时，假设匹配到 S[i] 与 P[j] 失配了（j 是当前模式串要比较的位置）：

1. 如果 j > 0，说明 P[0...j-1] 这一段是匹配成功的。
2. 我们查看 next[j-1]，设其值为 k。
3. 这意味着，在已匹配的前缀 P[0...j-1] 中，最前面的 k 个字符 和 最后面的 k 个字符 是一样的。
4. 因此，我们可以直接把 j 跳到 k（即 j = next[j-1]），然后继续用当前的 S[i] 和新的 P[j] 比较。文本指针 i 不动！

4. 手把手模拟运行（看清“不回溯”）

• 文本 S：ABABABC
• 模式 P：ABABC (next = [0, 0, 1, 2, 0])

步骤详解：

1. i=0, j=0：S[0]=A vs P[0]=A → 匹配，i=1, j=1
2. i=1, j=1：S[1]=B vs P[1]=B → 匹配，i=2, j=2
3. i=2, j=2：S[2]=A vs P[2]=A → 匹配，i=3, j=3
4. i=3, j=3：S[3]=B vs P[3]=B → 匹配，i=4, j=4
5. i=4, j=4：S[4]=A vs P[4]=C → 失配！
   • 此时 j=4 > 0，查 next[3] = 2。
   • 我们令 j = 2。注意：i 依然停在 4 不动。
   • 逻辑含义：模式串右移，利用已知的 "AB" 前缀，直接对齐文本中已匹配的后缀 "AB"。
6. 继续比较：S[4]=A 与 P[2]=A → 匹配，i=5, j=3
7. i=5, j=3：S[5]=B vs P[3]=B → 匹配，i=6, j=4
8. i=6, j=4：S[6]=C vs P[4]=C → 匹配，j == 5，匹配成功！

5. 最难啃的骨头：如何高效构建 Next 数组？

构建 Next 数组的过程，本质上是模式串自己与自己进行 KMP 匹配。

我们用双指针：

• len 表示当前最长的相等前后缀长度（也是前缀指针）。
• i 从 1 遍历到末尾（后缀指针）。

构建逻辑（伪代码思路）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

next[0] = 0
len = 0
i = 1
while i < m:
    if P[i] == P[len]:
        len += 1
        next[i] = len
        i += 1
    else:
        if len > 0:
            # 关键回退！利用已经算好的 next
            len = next[len - 1]
        else:
            next[i] = 0
            i += 1

手动演算 P = "AAACAAAA"（让你体会回退的精髓）：

1. i=1, len=0：P[1]=A vs P[0]=A → 匹配，next[1]=1, len=1, i=2
2. i=2, len=1：P[2]=A vs P[1]=A → 匹配，next[2]=2, len=2, i=3
3. i=3, len=2：P[3]=C vs P[2]=A → 失配！
   • len > 0，所以 len = next[1] = 1（回退）。
   • 继续比较：P[3]=C vs P[1]=A → 失配！
   • len > 0，所以 len = next[0] = 0。
   • 继续比较：P[3]=C vs P[0]=A → 失配！
   • len == 0，next[3] = 0, i=4
4. i=4, len=0：P[4]=A vs P[0]=A → 匹配，next[4]=1, len=1 … 以此类推。

6. 终极总结（面试/考试速记）

• 时间复杂度：O(n + m)（预处理 O(m)，匹配 O(n)）。
• 空间复杂度：O(m)。
• 核心口诀：

  匹配失败看前一位，
  Next 值决定 j 回退到几，
  主串指针永不回头，
  前缀函数自己匹配自己。

代码实现（Python）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def build_next(p):
    m = len(p)
    next_arr = [0] * m
    j = 0 # 前缀长度
    for i in range(1, m):
        while j > 0 and p[i] != p[j]:
            j = next_arr[j-1] # 回退
        if p[i] == p[j]:
            j += 1
            next_arr[i] = j
    return next_arr

def kmp(s, p):
    next_arr = build_next(p)
    j = 0
    for i in range(len(s)):
        while j > 0 and s[i] != p[j]:
            j = next_arr[j-1]
        if s[i] == p[j]:
            j += 1
            if j == len(p):
                return i - j + 1 # 返回起始索引
                # 如果想找所有匹配：j = next_arr[j-1]
    return -1