KMP 演算法笔记

这篇是我学习 KMP 演算法的一个纪录。

KMP 演算法介绍

KMP（Knuth-Morris-Pratt）演算法是一种高效率的字串匹配演算法，用来在一个字串中（此文之后称为 mainStr，文章后面，程式码的变数也以此命名）快速搜寻一个目标字串（此文之后称为 targetStr，文章后面，程式码的变数也以此命名）。

它的最大特点是透过 LPS（Longest Prefix Suffix）阵列，也有些文章会称为 next 阵列，来避免不必要的重复比较。

这个 LPS 阵列会记录 targetStr 中每个位置的「最长可匹配前缀与后缀的长度」，当匹配失败时，可以利用 LPS 阵列跳过已经匹配过的部分，而不需要回退到 mainStr 最起始的位置，从而提升匹配速度。

不过在举一个 LPS 阵列当例子时，要先补充一下，如果我们严格区分前缀的话，其实可以分成两种：

• 前缀（prefix）：可以包含整个字串本身。
• 真前缀（proper prefix）：不能包含整个字串本身。

这里产生 LPS 阵列时，要採用的是真前缀。

举例来说，假设我们的 targetStr 是 "ABABC"，则 LPS 阵列为 [0, 0, 1, 2, 0]：

• 当前遍历过的子字串为 "ABA"，前缀有 "A"、"AB"，后缀有 "A"、"BA"，共同的 LPS 为 "A"，长度 1，LPS[2] 为 1，所以 LPS 阵列中的元素值代表的是一个字串的前缀集合，和后缀集合当中，共同字串当中的最长字串的长度。
• "ABAB" 的前缀 "AB" 与后缀 "AB" 是相等的，因此 LPS[3] = 2。
• "ABABC" 没有相等的前缀与后缀，所以 LPS[4] = 0。

当字串匹配失败时，可以透过这些 LPS 值来决定 targetStr 应该向右滑动多少格，避免不必要的重复比较。

学习资源

有了前面的概念后，先不急着看程式码，因为我自己在学习这个演算法的时候，也爬了不少文章和影片，觉得学习效果比较好的方式还是先看别人推导这个演算法的影片会比较好懂。

所以这里推荐读者可以先观看 NeetCode 解说的 Knuth–Morris–Pratt KMP - Find the Index of the First Occurrence in a String - Leetcode 28 - Python 和 最浅显易懂的 KMP 算法讲解 这两部影片，再看以下的程式码会更有概念，

灵神分享 KMP，这篇是一则短文，不过我很崇拜灵神所以把他写的也补充上来XD。

字符串匹配 - KMP 算法原理和实现 这篇是看过介绍 KMP 演算法的文章当中，最清楚的。

KMP 演算法的程式码

这个演算法主要分成两个部分：

1. 建立 LPS 阵列

function computeLPS(targetStr) {
const lps = new Array(targetStr.length).fill(0);
let prevLPS = 0; // 目前最大前缀长度
let i = 1; // 从 mainStr 的第二个字元开始计算

while (i < targetStr.length) {
if (targetStr[i] === targetStr[prevLPS]) {
lps[i] = ++prevLPS; // 记得 prevLPS 先 + 1
i++;
} else {
if (prevLPS !== 0) {
prevLPS = lps[prevLPS - 1]; // 回溯到之前计算的 LPS 值
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}

建立 LPS 阵列的时间复杂度为 O(n)，n 为 mainStr 长度。

2. 进行字串匹配

function KMPSearch(mainStr, targetStr) {
const lps = computeLPS(targetStr);
let i = 0; // mainStr 的 index
let j = 0; // targetStr 的 index

while (i < mainStr.length) {
if (mainStr[i] === targetStr[j]) {
i++;
j++;
} else {
if (j !== 0) {
j = lps[j - 1]; // 跳过部分匹配
} else {
i++;
}
}
if (j === targetStr.length) {
return i - j; // 找到匹配位置

// 如果需要查找所有匹配位置，可以继续执行，把当前位置(i - j)存在一个阵列，while 迴圈结束后回传
// j = lps[j - 1];
}
}
return -1; // 未找到匹配
}

console.log(KMPSearch("ABABDABACDABABCABAB", "ABABCABAB")); // 10
console.log(KMPSearch("abcxabcdabcdabcy", "abcdabcy")); // 8
console.log(KMPSearch("hello world", "world")); // 6
console.log(KMPSearch("abcdef", "xyz")); // -1

字串匹配的时间复杂度为 O(m)，m 为 targetStr 长度，所以整个 KMP 演算法的时间复杂度为 O(n + m)。

LeetCode 练习题

学习完后，可以来实战演练下，前两题暴力解能过，但可以运用 KMP 优化：

28. Find the Index of the First Occurrence in a String

1408. String Matching in an Array

1392. Longest Happy Prefix

KMP 演算法会建立 LPS 阵列，1392 这题是找出 Longest Prefix Suffix 字串本身并回传。