个人理解，KMP算法主要是减少了匹配的次数，利用已有的信息省去无用的匹配。

先看一个例子，体会一下KMP算法和暴力法的差别。

主串s：abcabcabf， 模式串p：abcabf

暴力匹配过程如下图所示，每次取相同长度的子串与模式串进行比较，每个字符都相同则匹配成功；否则本次匹配失败，将模式串后移一位再从头开始比较。

KMP匹配过程如下图所示（先不用考虑为什么是这个过程，仅体会匹配次数的差别），可以看到采用KMP算法只进行了两次匹配。KMP算法的精髓就在于当匹配失败时，不是盲目的后移一位再从头开始比较，而是利用之前的匹配信息决定模式串后移的位数以及开始比较的位置。而之前的匹配信息就与大名鼎鼎的next数组有关。

这里先介绍 next数组是什么，以及KMP算法是 如何利用next数组减少匹配次数，如何求得next数组将在后面讲解。

next[i] 表示 子串 p[0:i] 的最长相同前后缀的长度（这里不再赘述前缀和后缀的定义），本例中next数组取值如下：

比较的过程中，在模式串的第 j 位（主串的第 i 位）比较失败时，则前面的 0 至 j-1 位是比较成功的。如下图所示，在第5位比较失败（c != f），则 0 至 4 位比较成功 abcab，即 p[0:j-1] 与 s[i-j:i-1] 是相同的，所以。KMP就是利用了这一段相同的子串以及最长相同前后缀的性质省略了无效的匹配。根据next数组得 next[4] 为2，则根据next数组的性质，主串 i 之前的next[j-1]位与模式串开头的next[j-1]位相同，且 i（不包括i）之前仅存在以s[i-next[j-1]]为开头的子串可能与模式串相同，所以，如图所示。将相同的 next[k-1] 位对齐，然后将模式串的指针指向第next[k-1]位（因为第next[k-1]位之前已经相同，不需要再比较）。

整体看来，当两个字符不相同时，保持主串的指针i不动，将模式串的指针j指向next[k-1]处，不断重复此过程直至两个字符相同或是 j 指向模式串的首位，当首位还不相同时，同时移动 i 和 j；当两个字符相同时，则比较它们的下一位，所以同时移动 i 和 j。

这里需要解释一下：为什么直接将相同的 next[j-1] 位对齐？主串中不存在 i-j 位之前开头的子串与模式串相同吗？（简言之，在本例中，为什么直接跳过了bcabc、cabca与模式串的比较？）

因为根据next数组的性质，即最长相同前后缀的性质，当 next[j] > next[j-1] 时，next[j-1]对应的字符串是 next[j] 对应的字符串的子串（如本例中的next[3] 和 next[4]）；当 next[j] // 不相同，去找最长相同前后缀，比较它们的下一位，循环此过程直至首位或相同 while(left > 0 && pattern[left] !== pattern[right]) { left = next[left - 1]; } if(pattern[left] === pattern[right]) { ++left; } next[right] = left; ++right; } return next; } function strStr(haystack, needle) { const next = getNext(needle); const m = haystack.length; const n = needle.length; let i = 0; // 主串指针 let j = 0; // 模式串指针 while(i j = next[j-1]; } if(haystack[i] === needle[j]) { ++j; } ++i; if(left === n) return right - left; } return -1; }