KMP 有什么用
- KMP 主要应用在 快速在「原字符串」中找到「匹配字符串」；
- KMP 的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了；
概念理解
最长相等前后缀
-
理解 最长相等前后缀 之前需要先理解，什么是前缀、什么是后缀，以 abeabf 为例，列出所有的前缀和后缀；
前缀 / 后缀 前缀子串 / 后缀子串 前缀：包含首字母，不包含尾字母的所有子串a、ab、abe、abea、abeab 后缀：包含尾字母，不包含首字母的所有子串f、bf、abf、eabf、beabf -
前缀表要求的就是相同前后缀的长度 ，以 aabaaf 为例，求出 最长相等前后缀：
前缀 最长相等前后缀 a 0 ab 0 abe 0 abea 1 abeab 2 abeabf 0
什么是前缀表
-
前缀表是用来回退的，它记录了 匹配串 与 主串 (文本串)不匹配的时候，模式串应该从哪里开始重新匹配；
-
为了清楚地了解前缀表的来历，来举一个例子：要在文本串 abeababeabf 中查找是否出现过一个匹配串 abeabf；
- 可以看出，原串中第六个字符 a 和 匹配串的第六个字符 f 不匹配了，如果暴力匹配，发现不匹配，此时就要从头匹配了；
![]( "什么是前缀表")
- 但如果使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第三个字符 e 继续开始匹配；
![]( "什么是前缀表")
- 可以看出，原串中第六个字符 a 和 匹配串的第六个字符 f 不匹配了，如果暴力匹配，发现不匹配，此时就要从头匹配了；
-
在
最长相等前后缀中求出了 abeabf 的 最长相等前后缀 ，那前缀表是多少呢？匹配串索引 0 1 2 3 4 5 匹配串 a b e a b f 前缀表 0 0 0 1 20
前缀表 与 next 数组
-
很多 KMP 算法的实现都是使用 next 数组来做回退操作，那么 next 数组与前缀表有什么关系呢？
-
常见的 next 数组有三种：
- 第一种：前缀表就是 next 数组（下面会用这个进行分析），遇到冲突后，就取冲突的前一位，所对应的 next 数组中的值所对应的下标，从第 2 位 e 开始继续匹配；
- 第二种：把前缀表整体右移一位，初始位置为 -1 的结果当做 next 数组，遇到冲突后，就取冲突的当前位，所对应的 next 数组中的值所对应的下标，从第 2 位 e 开始继续匹配；
-
以文本串 abeababeabf 举例说明：
匹配串索引 0 1 2 3 4 5 匹配串 a b e a b f 第一种前缀表 0 0 0 1 20 第二种前缀表 -1 0 0 0 1 2
朴素匹配 VS KMP 匹配
朴素匹配
-
枚举原串 str 中的每个字符作为「发起点」，每次从原串的「发起点」和匹配串 pattern 的「首位」开始尝试匹配：
- 匹配成功：返回本次匹配的原串 str 的「发起点」；
- 匹配失败：枚举原串 str 的下一个「发起点」，重新尝试匹配；
-
也就是说，对于「朴素匹配」而言，一旦匹配失败，将会将原串指针调整至下一个「发起点」，匹配串的指针调整至起始位置，然后重新尝试匹配；
![]( "朴素匹配")
-
所以「朴素匹配」的复杂度是
O(m∗n)；
KMP 匹配
-
首先匹配串会检查之前已经匹配成功的部分中里是否存在相同的「前缀」和「后缀」，若存在，则根据前缀表构建 next 数组，匹配串 f 匹配失败，对应的next 数组中的 索引 2 ，也就是从 e 的位置继续向后匹配；
![]( "什么是前缀表")
-
跳转到下一匹配位置后，尝试匹配，发现两个指针的字符对不上，并且此时匹配串指针前面不存在相同的「前缀」和「后缀」，这时候只能回到匹配串的起始位置重新开始：
![]( "什么是前缀表")
-
到这里，应该清楚 KMP 为什么相比于朴素解法更快：
- 因为 KMP 利用已匹配部分中相同的「前缀」和「后缀」来加速下一次的匹配；
- 因为 KMP 的原串指针不会进行回溯（没有朴素匹配中回到下一个「发起点」的过程）；
-
当原串指针从 i 位置后移到 j 位置，不仅仅代表着「原串」下标范围为 [i, j) 的字符与「匹配串」匹配或者不匹配，更是在否决那些以「原串」下标范围为 [i, j) 为「匹配发起点」的子集；
next 数组的构建
构建分析
以 前缀表就是 next 数组 为例，来看看对应的 next 是如何被构建出来的？
-
起始时
next[0] = 0，j 从 0 位置开始，i 从 1 位置开始；
![]( "next 数组的构建")
-
如果
p[j] === p[i]：则next[i] = j+1，i 和 j 同时后移（这个过程一直循环进行）；
![]( "next 数组的构建")
-
如果
p[j] !== p[i]：则将 j 指针指向迁移位置的 next 数组所对应的值，即j = next[j-1]，这个过程同样是循环进行，直到p[j] === p[i]或者j === 0(j===0 则代表不能继续回退了)；
![]( "next 数组的构建")
-
继续这个过程，如果不匹配且
j = 0，直接让next[i] = 0，i 指针后移；
![]( "next 数组的构建")
-
如果匹配，则
next[i] = j+1，并让 i、j 后移；
![]( "next 数组的构建")
-
循环以上步骤，直到匹配串匹配完毕；
![]( "next 数组的构建")
代码实现
const getNext = (needle) => {
const next = [0];
let j = 0;
for (let i = 1; i < needle.length; i++) {
while (j > 0 && needle[i] !== needle[j]) {
j = next[j - 1];
}
if (needle[i] === needle[j]) {
j++;
}
next[i] = j;
}
return next;
}
参考资料
算法基础🔮 链表
上一篇
