KPM 算法的 JS 实现

[NOTE] Updated May 31, 2023. This article may have outdated content or subject matter.

KMP (Knuth–Morris–Pratt algorithm) 算法是用于比较字符串的，给定字符串A，以及匹配字符串 B，判断 A 中是否包含 B。

最直白的做法是，遍历 A 的每个字符，找到和 B 的第一个字符相同的，然后从这个字符开始，逐个和 B 的字符比较，看是否能完全匹配 B。

当 A 中的某个字符不能匹配 B 时，则从 A 的下一个匹配字符开始，再和 B 进行匹配。

这样的匹配过程，会造成 A 中比较过的字符重复去匹配，从而造成匹配效率的下降。

而 KMP 的目的就是避免重复匹配，A 中的字符匹配过了就不会再进行匹配， B 进行移动，移动到下一个和 A 匹配的位置，继续配置。

KMP 利用了匹配后的信息，把 匹配串(B)的匹配部分的前缀 和 原串(A)匹配部分的后缀 进行对齐，从而快速移动匹配串，避免了原串遍历的回溯。

字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；

字符串的后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

最长公共前后缀: 所有相同的前缀和后缀中，最长的一个前缀后缀。

例如字符串 "abcaa":

前缀有 ["a", "ab", "abc", "abca"]

后缀有 ["a", "aa", "caa", "bcaa"]

最长公共前后缀: "a"

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

PMT[i] 表示一个部分匹配值，描述的是在 0 ~ i 这个区间，最长公共前后缀的长度。

计算 PMT 的过程，其实也利用了 KMP 算法。

PMT 代码实现

  function getPmt(s) {
    const n = s.length;
    // 初始化为 0
    const pmt = new Array(n).fill(0);

    // i 对应的是后缀(除去 0 的元素)
    // j 对应的是前缀，错位比较，计算公共前后缀
    let i = 1;
    let j = 0;

    while (i < n) {
      // 如果字符相同，则有相同前后缀，统计长度
      if (s[i] == s[j]) {
        pmt[i++] = ++j;
      } else {
        // 当字符出现不匹配的时候，判断 j 前面是否还有zh公共前缀，有则移动到前缀的下一位
        // 即 pmt[j - 1] (0 ~ j - 1 中，最长公共前后缀长度）
        if (j > 0) {
          j = pmt[j - 1];
        } else {
          // 如果 j 为 0，肯定没有公共前轴缀，此时 j 无法移动，只能移动 i
          i++;
        }
      }
    }

    return pmt;
  }

  console.log(getPmt('aaabbab'));

参考 [算法] 轻松掌握 kmp 的最后一个视频。

  function kmp(s, p) {
    const n = s.length;
    const m = p.length;

    const pmt = new Array(m).fill(0);
    let i = 1, j = 0;

    while (i < m) {
      if (p[i] === p[j]) {
        pmt[i++] = ++j;
      } else {
        if (j > 0) {
          j = pmt[j - 1];
        } else {
          i++;
        }
      }
    }

    i = 0;
    j = 0;

    while (i < n) {
      if (s[i] === p[j]) {
        i++;
        j++;

        if (j === m) {
          return i - j;
        }
      } else {
        if (j > 0) {
          j = pmt[j - 1];
        } else {
          i++;
        }
      }
    }

    return -1;
  }

时间复杂度为 O(n + m) ，其中 n 是字符串的长度， m 是匹配串的长度。

28. 实现 strStr()

[算法] 轻松掌握 kmp - bilibili@邋遢大哥233 最容易理解的视频
字符串匹配的 KMP 算法 - ruanyifeng
多图预警详解 KMP 算法 - leetcode
如何更好地理解和掌握 KMP 算法? - 知乎@海纳

Author Spike Leung

LastMod 2023-05-31 (1ef6a30)

License CC BY-NC-ND 4.0

Contents

PMT 代码实现