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 代码实现 

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

  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 实现 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

  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 题目

参考