KMP

代码随想录: https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC

KMP 算法主要应用于字符串匹配。

主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，利用这些信息，以避免从头匹配。

所以如何记录已经匹配的文本内容，是 KMP 的重点。

前缀表用于记录下标 i 之前的字符串中，有多大长度的相同前缀和后缀。

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

个人理解，KMP 的关键点在于如何利用已经匹配的部分，next 数组就是干这个的，利用前缀和后缀的概念，以实现字符串的匹配。

1. 构建 next 前缀数组，next[i] 表示子字符串 (0,..i) 的最长相等前后缀的长度
2. 遍历匹配，当匹配失败时，使匹配点位于 next[i-1]，因为，next[i-1]存储着与(0,..i-1)的后缀相等的最长前缀的下标的后一位，这样，可以从这个位置继续匹配，如果还是匹配不上，则继续移动匹配点。