为什么要有KMP算法

KMP算法是在一个长的字符串中，查找固定序列的子字符串序列。有一种算法是暴力匹配。

假设长字符串是babaabaacc，记作字符串A,想要在其中找出aabaa,记作字符串B。

暴力匹配就是拿着B和A，从头到尾一一比较。

1. 先比较用B[0]与A[0]，

2. 发现a!=b,

3. 然后从B往后移动一个位置，

4. 用B[0]与A[1]比较，发现a==a,继续用B[1]与A[2]比较。

5. 发现a!=b。

6. 然后B往后移动一个位置，开始新一轮的比较。

7. 这时用B[0]与A[2]比较，

8. 发现a!=b，

9. 然后B往后移动一个位置 ...

过程比较清晰，可以看到在比较的过程中，做了些无用功。在B[1]与A[2]比较后，发现a!=b，就已经知道A[2]!=a了，就不需要比较B[0]与A[2]，而是直接比较B[0]与A[3]。

KMP算法就是用来解决这样的无用功。

主要分为两步。第一步，先获取nest数组。nest数组表示当匹配字符串与被匹配字符串不匹配的时候，指向匹配字符串的指针应该指向哪里

求nest数组

nest数组，就相当于是求前后缀公共最长子串：

最大公共前后缀子串：一个字符串的最大公共前后缀子串是指它的一个子串，既是它的前缀，也是它的后缀，并且长度最大。

例如，字符串aaba的最大公共前后缀子串是a，长度为1；字符串aabaa的最大公共前后缀子串是aa，长度为2。 下面有模式串aabaaf的详细匹配表：

位置	0	1	2	3	4	5
字符	a	a	b	a	a	f
最大公共前后缀子串长度	0	1	0	1	2	0

这个表可以通过递推的方式求出，具体步骤如下：

• 初始化一个数组next，长度和模式串相同，将next[0]设为0。
• 从第二个字符开始遍历模式串，对于每个位置i，找到它之前的最长相同前后缀子串的长度k = next[i-1]。
• 如果模式串的第k+1个字符和第i+1个字符相同，那么说明最长相同前后缀子串的长度可以加一，即next[i] = k + 1。
• 如果不相同，那么需要回溯到更短的相同前后缀子串，即将k = next[k]，重复上一步，直到找到相同的字符或者回溯到头。
• 最后返回最大公共前后缀子串数组。

将最大公共前后缀子串数组整体往右移一格，然后整体加一；0位始终置0，就得到了nest数组。而nest数组就是我们KMP要用到的关键数组。 至于为什么要这么处理最大公共前后缀子串数组就能得到nest数组，可以评论区留言，我专门出一期

编写代码

对于nest数组刚开始我也只会手算，不知道如何用算法描述，就在网上找了一篇文章（kmp算法 next[]数组的两种求法），看了里面讲求解nest数组的第一种方法，看懂了，就写了下面这个代码。

要是你看懂了上面这篇文章，下面代码为啥这么写你也肯定知道。

/** 
 * @typedef {(str: string) => number[]} getNestArray
 */

/** 
 * @type {getNestArray}
 * 
 * 声明一个名为 getNestArray 的常量，类型为 getNestArray。
 * 这个函数用于计算KMP算法中的嵌套数组（next数组）。
 */
const getNestArray = (str) => {
    // 创建一个初始的数字数组 nestArray，包含一个初始值 -1。
    const nestArray = [-1];
    const strArray = "0" + str;

    // 初始化数组的前两个元素。
    nestArray[1] = 0;
    nestArray[2] = 1;

    // 定义内部函数 getNestNum，用于递归计算嵌套数字。
    const getNestNum = (nestNum, s1) => {
        // 获取当前位置 nestNum 对应的字符 s2。
        const s2 = strArray[nestNum];
        
        // 如果当前字符 s1 与 s2 相同，返回 nestNum + 1，即下一个位置。
        if (s1 === s2) {
            return nestNum + 1;
        } 
        // 如果 nestNum 等于 1，则返回 1，表示未找到嵌套。表示不要再往前找了
        else if (nestNum === 1) {
            return 1;
        }
        // 否则，递归调用 getNestNum，继续计算嵌套数字。
        return getNestNum(nestArray[nestNum], s1);
    };

    // 循环遍历输入字符串的字符，从第三个字符开始。
    for (let i = 3; i < strArray.length; i++) {
        // 获取前一个字符 s1。
        const s1 = strArray[i - 1];
        
        // 调用 getNestNum，并将结果存储在 nestArray 中。
        nestArray[i] = getNestNum(nestArray[i - 1], s1);
    }

    // 返回最终的 nestArray 数组，其中包含了KMP算法中的嵌套数组（next数组）。
    return nestArray;
};

解释：

1. 在nest数组中，下标会从1开始计算，所以下标为0的位置用-1占位。对于字符串也会用0占位0的位置。这是一个习惯。（也可以从0开始）

测试代码：

const str = "ababaa";
const str1 = "aaaab";

console.log(getNestArray(str));
console.log(getNestArray(str1));

结果：

和nest数组一致

求是否含有匹配字符串

/** 
 * @typedef {(str: string) => number[]} getNestArray
 * 
 * 使用 JSDoc 注释语法定义了一个类型别名 getNestArray。
 * 它表示一个函数，接受一个字符串参数并返回一个数字数组。
 */

/** 
 * @param {string} str - 原始文本字符串
 * @param {string} matchStr - 要查找的匹配字符串
 * @param {getNestArray} getNestArray - 用于计算嵌套数组的函数
 * @returns {number} - 返回匹配字符串在原始文本字符串中的起始位置，如果未找到则返回 -1
 * 
 * 这个函数实现了KMP算法，用于在原始文本字符串中查找匹配字符串的位置。
 * 它接受三个参数：原始文本字符串、要查找的匹配字符串以及用于计算嵌套数组的函数。
 */
const KMP = (str, matchStr, getNestArray) => {
    // 调用 getNestArray 函数来获取嵌套数组（next数组）。
    const nestArray = getNestArray();

    // 在原始文本字符串前面添加一个 "0"，占个第0位。
    const strArray = "0" + str;

    // 初始化两个指针 i 和 j。
    let i = 0,
        j = 1;

    // 使用双指针算法来比较匹配字符串和原始文本字符串。
    while (i < matchStr.length && j < strArray.length) {
        if (j === 0 || strArray[j] === matchStr[i]) {
            // 如果字符匹配或者 j 为 0，或者匹配成功，增加 i 和 j。
            i++;
            j++;
        } else {
            // 如果字符不匹配，根据嵌套数组来调整 j。
            j = nestArray[j];
        }
    }

    // 检查是否找到完全匹配。
    if (j === strArray.length) {
        // 返回匹配字符串在原始文本字符串中的起始位置。
        return i - j + 1;
    } else {
        // 如果未找到匹配，返回 -1。
        return -1;
    }
};

非常经典的KMP算法，就不做解释了。思路和网上的大部分文章相似，而且网上肯定有比我解释得更好的。 测试数据：

const str = "ababaa";
const matchStr1 = "qweaaababaaabab";
const matchStr2 = "bbabaabab";

console.log(KMP(str, matchStr1, getNestArray));
console.log(KMP(str, matchStr2, getNestArray));

测试结果：

求nestVal数组

这是对nest数组进行优化

const getNestValArray = (str) => {
	const nestValArray = getNestArray(str);
	const strArray = "0" + str;
	for (let i = 2; i < nestValArray.length; i++) {
		const s1 = strArray[i];
		const nestNum = nestValArray[i];
		const s2 = strArray[nestNum];
		if (s1 === s2) {
			nestValArray[i] = nestValArray[nestNum];
		}
	}

	return nestValArray;
};

nestVal数组是nest数组的升级版，因为即使nest数组也有不必要的移动，没有效率最优。所以才有了nestVal数组。

对于nestVal数组，讲得最好的就是王道考验的数据结构视频课了，这里有链接，快过去看看吧：【王道计算机考研 数据结构】 【精准空降到 00:08】 4.2_4_KMP算法的进一步优化_哔哩哔哩_bilibili

测试数据：

const str = "ababaa";
const str1 = "aaaab";

console.log(getNestValArray(str));
console.log(getNestValArray(str1));

结果：

测试KMP算法：

const str = "ababaa";
const matchStr1 = "qweaaababaaabab";
const matchStr2 = "bbabaabab";

console.log(KMP(str, matchStr1, getNestValArray));
console.log(KMP(str, matchStr2, getNestValArray));

结果：

成功

好问题：

这个算法这么酷，在实际开发中能用到吗。说实话，根本用不到。 在javascript开发中跟，字符串匹配可以用用API轻轻松松解决。其他高级编程语言同样如此。

const str = "ababaa";
const matchStr1 = "qweaaababaaabab";
const matchStr2 = "bbabaabab";

const isInclude = matchStr.include(str); // first blood
const isMatch = /ababaa/.test(matchStr);// double kill
const index = matchStr.indexof(str); //triple kill

总结：

这篇比较难懂，通篇都是代码，如果不知道KMP思想，根本看不懂代码为什么这么写，如果懂了KMP思想，相信大家自己也能写出来。

那这篇文章有什么用呢？算是给那些懂了KMP思想，又不想动手写代码的人？哈哈