KMP 字符串匹配

字符串 · 失配跳转不回退

在文本里找模式串

在一段文本 T（abababcab）里找模式串 P（ababc）第一次出现的位置——这是编辑器「查找」、grep、DNA 比对的基本操作。朴素做法：把 P 对齐到 T 的每个位置逐字符比，一旦失配就把 P 整体右移一格、从头再比——最坏 O(n·m)，因为每次失配都白白丢掉了已经比对成功的信息。

KMP：失配时「跳」而不是「重来」

KMP 的洞见：失配时，已经匹配的那段前缀我们是知道的，不必从头再比。它预先算出模式串的部分匹配表（lps，又叫失败函数 π）：lps[k] 是 P[0..k] 里「既是真前缀又是真后缀」的最长长度。

匹配时用两个指针：i 扫文本、j 扫模式。字符相等，i、j 一起前进；失配时，文本指针 i 绝不回退，只把 j 跳到 lps[j-1]——相当于把模式串向右滑动，让「已匹配前缀的最长可复用后缀」接着比。这样每个文本字符最多被看常数次，总复杂度降到 O(n + m)。

下面是 T=abababcab、P=ababc（其 π = [0,0,1,2,0]）。点「下一步」逐步看：T 行在上、P 行按对齐位置滑动、π 行是部分匹配表。当前比较的两格琥珀高亮，已匹配的前缀变绿；比到 abab 后 a≠c 失配，j 用 π 跳回、模式右滑（留意 i 没动！），接着一路匹配到 ababc——命中于下标 2。右侧代码随每一步同步高亮。

在文本 T 中找模式 P：i、j 都从 0 开始，模式对齐到文本开头

1function buildLps(pat: string): number[] {
const lps = new Array(pat.length).fill(0);
let len = 0, i = 1;
while (i < pat.length) {
  if (pat[i] === pat[len]) lps[i++] = ++len;
  else if (len > 0) len = lps[len - 1];
  else lps[i++] = 0;
}
return lps;
10}
11function kmpSearch(text: string, pat: string): number[] {
const n = text.length, m = pat.length;
const lps = buildLps(pat);
const res: number[] = [];
let i = 0, j = 0;
while (i < n) {
  if (text[i] === pat[j]) {
    i++; j++;
    if (j === m) { res.push(i - m); j = lps[j - 1]; } // 命中
  } else if (j > 0) {
    j = lps[j - 1];                    // 失配：跳转，i 不回退
  } else {
    i++;                               // j=0 失配：文本前进
  }
}
return res;
27}

文本 Tabababcab

模式 Pababc

i（文本）0

j（模式）0

已找到—

1 / 12

为什么快

朴素匹配失配后 i 回退、模式从头比，同一段文本被反复扫描。
KMP 靠部分匹配表让 i 永不回退，模式串「聪明地滑动」，跳过注定失配的对齐——O(n+m)。
部分匹配表本身也用「模式串和自己匹配」的方式 O(m) 算出（本页预置展示，构建过程同样精巧）。

KMP 是字符串匹配的基石。同一族里还有：Rabin-Karp（滚动哈希）、Boyer-Moore（从右往左比 + 坏字符/好后缀跳更远）、以及多模式的 AC 自动机——都是「用预处理换匹配时的跳跃」这一思想的不同展开。

算法可视化

KMP 字符串匹配

在文本里找模式串

KMP：失配时「跳」而不是「重来」

为什么快