题目链接

28. 实现 strStr()

写点东西

KMP 算法的主要思想是利用模式串自身的特性来减少不必要的匹配过程，例如，在 aabaaf 这个模式串中，倘若此时文本串已经成功匹配了模式串的前四个元素即 aaba ，但是第五个元素没有匹配成功。此时，若按照一般的匹配算法来实现，应该以此时模式串中对应的第二个字符位置为文本串开始新一轮匹配的位置，即文本串开始匹配的元素索引 + 1。

事实上，不难看出，这一次的匹配是一定不可能成功的，即是一次不必要的匹配过程，因为在下一个要匹配的元素位置处，一定是文本串中的 b 与模式串中的 a 相比较，这显然是不可能匹配成功的。接着，文本串再以新的起点 b 来匹配模式串，显然又是一次无法成功的无效匹配。直到下一次从 b 后面的 a 开始的匹配才是有可能成功的匹配，即必要的匹配。

之所以会出现这样的问题，是因为在每一次的遍历过程中没有把能做的事情给做完，没有将这一次的遍历给收益最大化，正如常见的快慢指针一般，只有快指针一个指针的时候，就是没有将每次遍历收益最大化的一种情况。

那么在这里，能做的事情是什么呢？

就是前面所说的，利用自身的特性来减少不必要的匹配过程。在上面的例子中我们不难发现，在只知道在第几个元素处匹配失败，以及知道模式串的内容的情况下，我们不需要知道文本串整体是什么样就能够判断推断出，必然会有两次无效匹配过程。

所以，在这里我们需要做的或者说能做的就是提前推断出这样的情况，跳过这样的无效匹配过程。因为我们的推断只用到了模式串本身的信息，所以我们先把精力放到模式串上，找出其中的规律。

// 自己写的时候歪打正着注意到 j-- 也可以得到相同的结果
// 所以从头开始思考了一下整个过程 试着换了一种解读方式
const cur = 'aabaaf';
const t = cur.split(''); // 模式串数组
let next = [-1];
let j = -1; // 指向用于匹配的模式串
// 构建 next 数组
for(let i = 1; i < t.length; i++) {
    // i 指向用于被匹配的文本串
    while(j >= 0 && t[i] !== t[j + 1]) {
        j--;
    }
    if(t[i] === t[j + 1]){
        next[i] = j + 1;
        j++;
    } else {
        next[i] = j; // j === -1
    }
}
console.log(next);

// 原本的 next 数组构造过程
let next = [-1];
let j = -1;
for (let i = 1; i < t.length; i++) {
    while(j >= 0 && t[i] !== t[j + 1]){
        j = next[j]; // 精髓
    }
    if (t[i] === t[j + 1]) {
        j++;
    }
    next[i] = j;
}

先按算法的过程走，模拟情形，找规律，理解过程寻找每一步的原因。

接着，再从头开始，或者说从已有条件与需要达到的目标开始，以一个新的角度去完整地整理一次，找一种更合适的打开或解读方式。

在正常情况下，如果文本串与字符串一开始就完全匹配了，那就相当于只是遍历了一遍数组，确认了一下是匹配的，没什么参考意义。我们关心的主要问题是，当遇到了不匹配的情况，应该怎么做？

下面将遇到的匹配失败先分成两种情况来考虑：

• 开头失败：这种情况直接去匹配下一个元素就好了
• 中间失败：这种情况才是核心，也就是说，在失败之前，前面是有成功匹配模式串的部分的，从前面的案例来看，在这成功匹配的部分里面是可能存在有效信息让我们减少无效匹配次数的，同时我们也知道了这些有效信息与文本串没有直接联系，那么我们要怎么获取到这些有效信息呢？遇事不决，(量子力学)直接穷举！

这里所谓的穷举指的是，模拟我们可能会遇到的所有失败，并根据每一种失败来找到对应的处理方案。

考虑一个模式串的例子：abababcab ，现在想想，我们可能会遇到哪些匹配失败的情况呢？

这里记录的是匹配成功的部分, 没有记录的是匹配失败的部分。
a
ab
aba
abab
ababa
......
abababca
abababcab

找到了所有失败的情况，接下来根据每一种失败来找到对应的处理方法，注意，这里的处理方法是指除去后续的无效匹配的情况方法。

现在考虑一个串：◻abababcab ，这里的 ◻ 就是模式串中索引为 -1 的项，先不用管是干嘛的，先接受这个设定，后面再回过头来看它的作用。

• 考虑第一种情况（其实和后面相比比较特殊）：

  文本串只成功匹配了 a 就出现了失败，试试拿 j + 1 去匹配，配吗？不配！就是只匹配成功了这个才失败的，拿错误来找错误了属于是。

  给这个 a 打上一个标记 -1 （也就是 next 数组），下次再遇到这情况就拿 ◻ 来匹配（即直接进入下一个元素重新开始匹配）。

• 考虑第二种情况：

  文本串只成功匹配了 ab 就出现了失败，试试拿 j + 1 去匹配，配吗？不配！

  给这个 b 打上一个标记 -1 （也就是 next 数组），下次再遇到这情况就拿 ◻ 来匹配（即直接进入下一个元素重新开始匹配）。

• 考虑第三种情况：

  文本串只成功匹配了 aba 就出现了失败，试试拿 j + 1 去匹配，配吗？这次还真配！

  给这个 a 打上一个标记 0 （也就是 next 数组），下次再遇到这情况就拿模式串中索引下标为 0 的元素 a 来匹配，不需要从 b 开始匹配，因为它的标记是 -1 ，需要直接用 ◻ 去匹配。

  匹配成功，移动 j ，看看还能不能继续往后匹配。

• 考虑第四种情况：

  文本串成功匹配了 abab 后出现了失败，试试拿 j + 1 去匹配，配吗？配！

  给这个 b 打上一个标记 1 （也就是 next 数组），下次再遇到这情况就拿模式串中索引下标为 1 的元素 b 来匹配。

  匹配成功，移动 j ，看看还能不能继续往后匹配。

• 。。。。。。

• 考虑第七种情况：

  文本串成功匹配了 abababc 后出现了失败，试试拿 j + 1 去匹配，配吗？这次不配！

  (前面的出现的情况都只是讨论了遇到了之后该从哪开始，并没有考虑开始之后如果还是不匹配该如何处理)

  此时可以理解为第六种情况，即文本串成功匹配了 ababab 后出现了失败，按照第三、第四种情况中提到的那样，下次再遇到这情况就拿模式串中索引下标为 ? 的元素 来匹配，这里的 ? 指的是模式串中最后一个成功匹配的元素的标记（即 next 数组） ，这里我们不难知道就是 3，也正是图中用的那样。

  而现在下一个元素匹配失败了（c），需要怎么处理呢？（到这里脑子穷了?想不清楚最本质的关系了）

  需要利用到我们前面留下的有效信息（即 next 数组），此时令 j = next[j] 可得 j === 1 ，我们注意到**模式串中索引下标为 1 的元素 **就是 b ，如图中所示的那样移动模式串，用此时的 j + 1 去匹配，配吗？还是不配！

  再继续让 j = next[j] 可得 j === -1 ，我们注意到**模式串中索引下标为 -1 的元素 **就是 ◻ ，如图中所示的那样移动模式串，用此时的 j + 1 去匹配，配吗？这次配了！

  给这个 c 打上一个标记 -1 （也就是 next 数组），下次再遇到这情况就拿 ◻ 来匹配（即直接进入下一个元素重新开始匹配）。

• 。。。。。。

这样一来就可以得到一个 next 数组，这个 next 数组其实就是记录着遇到了各种情况的失败后该从何处开始重新匹配的信息，再本质一点就是，模式串自身的前后元素相似程度以及映射关系。

情况就拿 ◻ 来匹配（即直接进入下一个元素重新开始匹配）。

• 。。。。。。

这样一来就可以得到一个 next 数组，这个 next 数组其实就是记录着遇到了各种情况的失败后该从何处开始重新匹配的信息，再本质一点就是，模式串自身的前后元素相似程度以及映射关系。

在算法实现的过程中，最精髓的一步就是 j = next[j] ，利用 next 数组中前后元素的相似程度以及映射关系，来找到距离当前最后一个成功匹配的模式串元素 的 最近的、可直接拿来对应匹配的模式串元素的位置。