KMP 有什么用
KMP 主要应用在字符串匹配上。
KMP 的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。所以如何记录已经匹配的文本内容，是 KMP 的重点，也是next 数组肩负的重任。
next 数组就是一个前缀表（prefix table）。
文本串和模式串
前缀表是如何记录的呢
- 首先要知道前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置。
什么是前缀表：记录下标 i 之前（包括 i）的字符串中，有多大长度的相同前缀后缀。
文章中字符串的
- 前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。
- 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
最长公共前后缀==最长公共前后缀==最长相等前后缀
- 下标 5 之前这部分的字符串（也就是字符串 aabaa）的最长相等的前缀 和 后缀字符串是 子字符串 aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面重新匹配就可以了。
构造 next 数组其实就是计算模式串 s，前缀表的过程。 主要有如下三步：
- 初始化
- 处理前后缀不相同的情况
- 处理前后缀相同的情况
使用 next 数组来做匹配
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以邮件至 963614756@qq.com。