Algorithm

KMP 算法 —— 理解与实现

算法学习笔记

Posted by Nicodechal on 2019-10-22

这里简单介绍 KMP 算法及其实现思路。KMP 算法实现了在线性时间内完成子串的查找，下面首先介绍基本的匹配算法，在考虑如何使用 KMP 的思路加快匹配。

基本的匹配算法

基本的思路，就是使用两个指针分别指向字符串 A 和待查找字符串 B，然后比较两个指针处的字符是否相等，如果相等就同时推进两个指针，否则回退两个指针 ( 具体来说，两个指针都先回退 B 指针移动的距离，此时，B 指针回到索引为 0 的字符，然后 A 指针再向前一格，重新匹配 )。遍历完 A 字符串后，如果 B 指针值为 B 的长度，说明得到匹配，否则失配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function match(A, B) {
  let i = 0, j = 0;
  while (i < A.length && j < B.length) {
    if (A[i] == B[j]) { // 相等同时推进两个指针
      i++;
      j++;
    } else { // 否则 i 退回下一次重试的索引，j重来
      i = i - j + 1;
      j = 0;
    }
  }
  // 最后根据 j 是否为 B 长度判断匹配
  return j < B.length ? -1 : i - j;
}

举个例子说明一下回退，其实就是先重置 i, j，再将 i 向前移一格：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
A = ababd, B = abd

ababd   i = 0
abd     j = 0
|

ababd   i = 1
abd     j = 1
 |

ababd   i = 2
abd     j = 2
  |

上面失配了，进行下面的回退:

ababd   i = i - j + 1 = 1
 abd    j = 0
 |

KMP 算法

KMP 加快匹配的方式是，使 i 不会回退，只改变 j 的位置。下面举个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
A = abababc, B = ababc

abababc i = 0
ababc   j = 0
|

...

abababc i = 4
ababc   j = 4
    |

上面失配，如果不回退 i，只改变 j，变成下面:

abababc   i = 4
  ababc   j = 2
  ^^|

上面最后 ^ 标记出已经匹配的部分，|代表现在正在匹配的位置。

拿上面的例子来说，已知失配点前是匹配的，因此，失配点 j = 4 前一定是 abab，不管是 A 还是 B，说明 abababc 中 i = 4 前一定是 abab。

1
2
3
[abab]abc i = 4
[abab]c   j = 4
      |

因此，这里可以直接利用失配点前的信息是已知的这一点就可以加快匹配。

例如对于 ababc，如果在 j = 2 失配，那失配点前内容为 ab；如果在 j = 3 失配，那失配点前内容为 aba。而且注意，这里只靠 B 自己就可以知道失配点前的内容了。

因此，对于 ababc，如果失配点是 j = 4，说明失配点前是 abab，又其后缀是 ab，和 ababc 的前缀匹配，因此此时只需把 j 移动到 j = 2 处即可，省略了 ab == ab 的匹配。

据此，即可实现 i 指针不动，只移动 j 指针：

1
2
3
4
5
6
7
8
9
10
11
A = abababc, B = ababc

abababc i = 4
ababc   j = 4
    |

上面失配。

abababc   i = 4
  ababc   j = 2
  ^^|

由上面可知，j 的跳转只取决于 B 本身，所以，对于一个给定的 j 值，其下一跳是固定的，使用一个 next 数组指明 j 的下一跳，即：j = next[j]。

由于下一跳的值小于自己 next[j] < j，因此假设 next[0] = -1。那么，如果已经知道 j 的下一跳，不后退 i 的匹配算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
function KMP(A, B) {
  let i = 0, j = 0;
  while (i < A.length && j < B.length) {
    if (j == -1 || A[i] == B[j]) { // change
      i++;
      j++;
    } else {
      j = next[j]; // change.
    }
  }
  return j < B.length ? -1 : i - j;
}

相较之前，两处改变，首先如果失配，i 值不变，j 变为下一跳；另一处为匹配条件增加了 -1 的判断。由于只有 next[0] = -1，因此 j == -1 说明在 0 处就失配了，因此需要让下一个 i 和 j = 0 匹配。代码通过让 i 和 j = -1 都加 1 实现这一点。

接下来说明 next 数组的计算。

next 数组计算也利用 KMP 算法的思路，这里匹配的是 i 之前的子串的前缀 (j) 和后缀 (i)。

i 的索引依旧不后退，当出现 A[j] == A[i] 时，前后缀匹配，所以 next[i + 1] 可以跳到 j + 1，即对于 ababc，A[1] == A[3]，说明前缀 A[0,1] = ab 和 后缀 A[2,3] = ab 匹配，所以有 next[4] = 2。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function getNext(A) {
  let i = 0, j = -1; // i = 0, 前缀从 -1 开始。
  const next = [-1]; // next[0] = -1;
  while (i < A.length - 1) { // 之后要赋值 i + 1, 所以减 1
    if (j == -1 || A[j] == A[i]) {
      i++;
      j++;
      next[i] = j; // 这里说明前后缀匹配，得到 i + 1 的 next
    } else {
      j = next[j];
    }
  }
  return next;
}

小结

本文简单介绍了 KMP 算法及其实现思路。首先说明常规的匹配方式，再对该算法进行改进引入 KMP 算法。然后说明对 KMP 算法的直观理解及具体实现。最后对 next 数组的求解进行了简要介绍。

FEATURED TAGS
Algorithm
FRIENDS