KMP算法

发布于 2026-09-08分类：JavaScript阅读 37

KMP 算法

字符串匹配是计算机的基本任务之一。

举例：字符串 "BBC ABCDAB ABCDABCDABDE" 是否包含 "ABCDABD"？Knuth-Morris-Pratt 算法（简称 KMP）是最常用的之一，以三个发明者命名，起头的 K 就是著名科学家 Donald Knuth。

1. 朴素匹配的低效

朴素的逐位匹配，每次失配就回退搜索词的起点，最坏情况时间复杂度 O(m·n)。

2. KMP 的核心思想

利用已知匹配信息，避免回退搜索词。

当空格与 D 不匹配时，前面 6 个字符 "ABCDAB" 是匹配的。这时不需要把搜索词整个回退到起点，而是根据"部分匹配表"决定后移几位：

移动位数 = 已匹配的字符数 - 对应的部分匹配值

3. 部分匹配表（Partial Match Table）

"部分匹配值" = "前缀"和"后缀"的最长共有元素的长度。

以 "ABCDABD" 为例：

子串	前缀	后缀	共有元素	部分匹配值
A	-	-	-	0
AB	[A]	[B]	-	0
ABC	[A, AB]	[BC, C]	-	0
ABCD	[A, AB, ABC]	[BCD, CD, D]	-	0
ABCDA	[A..ABCDA]	[BCDA, CDA, DA, A]	A	1
ABCDAB	[A..ABCDA]	[BCDAB..B]	AB	2
ABCDABD	[A..ABCDAB]	[BCDABD..D]	-	0

4. JavaScript 实现

let strStr = function (hayStack, needle) {
  if (needle.length === 0) return 0;

  // 构建 next（部分匹配表）
  const getNext = (needle) => {
    const next = [];
    let j = 0;
    next.push(j);
    for (let i = 1; i < needle.length; i++) {
      while (j > 0 && needle[j] !== needle[i]) j = next[j - 1];
      if (needle[j] === needle[i]) j++;
      next.push(j);
    }
    return next;
  };

  const next = getNext(needle);
  let j = 0;
  for (let i = 0; i < hayStack.length; i++) {
    while (j > 0 && hayStack[i] !== needle[j]) j = next[j - 1];
    if (hayStack[i] === needle[j]) j++;
    if (j === needle.length) return i - needle.length + 1;
  }
  return -1;
};