前言

本文根据网上查阅的资料进行筛选总结，要点如下：

注：例子都是适合用下标为0开始的数组存储的模式串。

1. 状态机
2. 状态机转化next数组
3. next数组优化为nextval
4. 计算移动长度

KMP

匹配就是我们固定被匹配串，拿着模式串从[0]开始滑动，匹配成功则记录下来。

状态机

不想画图，直接做表跳到下一节next
考虑模式串aabaab

以前缀子串顺序作为状态机的状态节点以其长度为编号（圆圈内的），原模式串中该前缀子串紧跟的下一个字符为转移输入（aab+a->aaba aab+c->不成为模式串的任何前缀子串）。
图中除了最后接受状态，都有两个出边，其中没有字母的就是失败转移，转移到相应节点（相当于if，else中的else）。同时，失败转移表示着，模式串需要滑动相应距离

失败情况：
-1或0 	回到节点0且模式串向前滑动一格；（-1和0相同，在next数组中-1表示阻止继续迭代，这里是为了统一）
 1 		回到节点1，将模式串向前滑动[编号-1]长度
 ……
 i		回到节点i，将模式串向前滑动[编号-1]长度

你可以先不考虑是否滑动的问题，这只是帮助你理解，不影响计算。

为什么回退的节点有差异？
如上图，考察节点2，此时已有符合的字符子串aa，如果下一个输入为b则转移到3否则转移到1.

解释：

1. 为什么接收b就转移到3：显然，当模式串前两个字符已匹配时开始考察第3个字符，如果第3个字符成功匹配就说明前3个字符都匹配.
2. 为什么"否则转移到1"：（重点）
   考虑当前已匹配串aa，发现状态1的串a是它的后缀，所以转移到1。
   即 最长后缀搜索：向前寻找节点，如果有当前子串的相同后缀串则转移（必然是最长的
   而3：aab则前面不存在它的后缀节点，所以重新开始转移到0.

匹配到到一定长度失败，我们要全部丢弃重头开始吗？在匹配过程中我们发现有这样的后缀它可以成为新的模式串的前缀子串（状态机的节点），那么我们直接把这个后缀串的第一个字符和模式串对齐（回退到相应节点），就省事很多！

如果跳到0就损失了一种可能，因为这相当于向后跳过两个字符（包括目前匹配失败的字符）。

More formal：当我们发现以s[i] （被匹配串的第i+1个元素）开头的长度为2的串匹配而长度为3的串无法匹配时，我们就减小它的长度，考虑s[i+1], s[i+2]开头的串能不能匹配长度为1为0的前缀子串（因为我们不知道s[i+3]的及以后的值，所以长度也相应缩小），也就是向前搜索2的串aa的后缀在前面出现的最近的地方。

本质上这就是我们在匹配时不希望每次失败就重头开始，这里当状态机接收到[else]字符时，重头开始相当于跳回0；
事实上在暴力匹配时，我们是先把（被匹配串的）下标0和模式串对齐然后匹配，失败，就把下标1再和模式串对齐然后匹配（代码就是两层for）

next数组

当已匹配长度为l时需要考察的就是第l+1个元素，但不是索引吗，从0开始所以就是第l个元素！
然后根据状态（索引）填上对应字符，再填上对应的转移状态（索引）。

直接计算法，next[i]填前i个字符得最大公共前后缀长度。
例：
next[3],前3个是aab无公共前后缀，填0；
next[4],前4个是aaba有公共前后缀a，填1；
next[5],前5个是aabaa有公共前后缀a, aa，填2；

next[0]=-1; 规定

nextval

先说怎么填

根据next数组向前迭代，如果考察的字符相同则，则值当前元素的next为迭代后的元素的next。

你跳转时发现，你将要跳转的状态(0)和你当前状态(1)需要的字符一样！坏事了，我要跳转，还不是因为输入的字符和我期望的字符(a)不匹配嘛，结果前辈(0)也要这个字符(a)，那我跳到前辈肯定也不匹配，那只能找前辈的前辈(-1)了，如果还不匹配……继续找，直到-1.

同理对于状态5，需求字符b，无b跳转2；而状态2，需求字符也是b，无b跳转1(必须要是基于更新过后的nextval).状态5失败说明输入不是b，则跳转到2，2也必然失败，于是5的失败跳转nextval就填2的失败跳转nextval。
即更新状态5的nextval为 状态2的nextval。

移动长度

超级简单，(索引)j - nextval[j]；找到对应列的索引和nextval直接一减就是结果。

解释一下-1，-1需要跳过第一个字符s[i]，而0是在检查第一个字符.

---

所以会画图就会填，不会画就算，熟练了直接瞪眼得！
这么细致的KMP还不给我点赞😍！