[算法][KMP]

KMP算法原理

参考资料：

最浅显易懂的 KMP 算法讲解

KMP算法之求next数组代码讲解、

KMP算法中next数组的求法及代码实现【C++】

由于上述的参考资料中各种假设略有不同，在此整理。

KMP算法：线性时间内，求出主串中匹配的子串的位置。

关键点：当遇到不匹配的字符时，通过之前匹配的相同字符（next数组）决定跳过多少个字符重新匹配。

核心为next数组求解, next求解的核心原理如下：

四段重合的示意图如下：

定义

前缀：包含首字符但是不包含尾字符的子串

后缀：包含尾字符但是不包含首字符的子串

前缀和后缀的定义 都排除了 字符串本身