原文链接 多图预警👊🏻详解 KMP 算法

KMP算法是一种字符串匹配算法，可以在 O(n+m) 的时间复杂度内实现两个字符串的匹配。

前缀表（next 数组）

next 数组存放的是当前长度下的 最长相同前后缀 的长度 以 abcabf 举例

1. a 时，最长前后缀长度是 0

   因为是缀。总长度就只有 1 的话单独一个字母不算做缀

   字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

2. ab 时，很显然长度也是 0

3. abc 时，很显然长度也是 0

4. abca 时， 最长相同前后缀长度就是 1 了，是 a

5. abcab 时， 最长相同前后缀长度就是 2 了，是 ab

6. abcabf 时，没有 最长相同前后缀了，长度是0

字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串； 字符串的后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

next 数组的应用