预备知识

一. 朴素模式匹配算法

 二、KMP算法

• KMP算法：最长相同前后缀，每次匹配都从匹配失误的地方开始匹配
• i 不动

三、求next数组

1、最长公共前后缀

假设有一个串P=“p0p1p2 …pj-1pj”。如果存在p0p1…pk-1pk = pj-kpj-k+1…pj-1pj，我们就说在P串中有一个最大长度为k+1的公共前后缀。

2、如何寻找前后缀？？？

找前缀时，要找除了最后一个字符的所有子串。
找后缀时，要找除了第一个字符的所有子串。

 这个表的含义是在当前字符作为最后一个字符时，当前子串所拥有的公共前后缀最长长度。例如当c作为最后一个字符时，当前子串abaabc并没有公共前后缀。

即 看该位置之前的( 不包括该位置 ) 的 最长相同前后缀 最后一个元素的下一个位置

参考来源：

cKMP算法详解_yyzsir的博客-CSDN博客_kmp算法

王道数据结构