KPM 算法的 JS 实现

Table of Contents

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 [Partial Match Table])

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

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 的最后一个视频。

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 是匹配串的长度。

leetcode 题目

参考

Author: Spike Leung

Date: 2022-02-12 Sat 00:00

License: CC BY-NC 4.0