串的模式匹配算法KMP
前言：
自从2015年上半年学会KMP，到现在2019年12月20日，已经快5年过去了，陆陆续续地四次认真学习KMP，第一次是数据结构课程上学习，第二次是考试之前复习，第三次是认真搞ACM的时候又学了一遍，第四次是今天，我即将结束长达一年的销售工作，重新做回程序员，最近在把ACM的几乎所有所学重新学习了一遍，大部分都看一下之前的代码就OK了，唯独KMP比较复杂。
这么多年以来，今天写这篇博客，我才第一次真正的觉得自己吃透了KMP，很多东西一定要用严格的语言表述出来，才真的懂了。
可能写的不如其他网友清楚，但是关键在于自己写的这个过程，认真写完之后思路无比清晰，这才是我写了一千多篇博客之后的重要无比的收获。
目录：
目录
正文：
一，原作引用
我把我的课本中，KMP这一块截图出来了，参见
数据结构课本上的KMPhttps://blog.****.net/nameof****/article/details/103625577
二，串的模式匹配算法
有一个文本串S，长度为n，和一个模式串T，长度为m，现在要查找T在S中的位置，怎么查找？
方法一：暴力枚举，时间复杂度O（n*m）
方法二：KMP，时间复杂度O（n+m）
KMP是由3位大佬同时发现，三个人的名字首字母分别是K、M、P
三，KMP的核心思想
暴力枚举当匹配失败即S[i]!=T[j]时，j需要回溯到1，从第一个字符重新匹配，而i也需要回溯到i-j+2
KMP的核心思想是，先充分挖掘模式串T的信息，当匹配失败时，i不动，j回溯到某个位置即可，因为匹配失败位置的前j-1个字符都是匹配成功的，所以S的这一段和T的这一段是相同的，也就是说，所有需要的信息都在T中。
那么，这个需要充分挖掘的信息，就是当匹配失败时，如何回溯，这个信息其实就是T的next数组。
四，next数组
注意：
next数组的定义是：对于j，next[j] 定义为满足式（4-4）的最大k值，写成表达式即为式（4-5）
具体求next的方法：
五，KMP方法
得到next数组之后，还是双指针扫描，当匹配失败即S[i]!=T[j]时，j需要回溯到next[j]继续匹配，直到模式串匹配完，即得到一个完全匹配。
暴力算法在一般数据的情况下，时间也接近（n+m），而KMP除了时间复杂度是O（n+m）之外，还有一个好处就是在很多场景下，不需要存主串S，只需要存模式串T，然后输入S的时候边输入边计算，不需要存，这种情况下空间复杂度就是O（m）
六，改进的next数组
当匹配失败时，我们需要把j回溯到next[j]重新与i匹配，使得尽快找到一个完全匹配。
然而，式（4-5）只是next数组的一个必要，并不是充分条件。
如果T[j]==T[next[j]]，那么把j回溯到next[j]之后，重新与i匹配也一定会失败，所以这个地方需要继续往前回溯。
如此得到nextval数组：
改进后的nextval数组，可以理解为充分必要。即j只能回溯到nextval[j]，无法回溯到更远的地方，因为nextval[j]是有可能和S[i]匹配成功的，这个有可能只取决于s[i]是什么，和T无关，所以nextval数组无法再优化。
七，难点总结
1，用KMP算法匹配主串S和模式串T，需要预先求出T的next数组，而求next数组的过程，其实是T从任意处和T本身的一个匹配的过程，而这个过程用的还是KMP。
是否逻辑循环？没有，这个KMP只需要基于已经求出来的前面一部分next数组即可。
换句话说，利用next数组的前i项求第i+1项的过程，就是一个kmp的过程，也就是如何利用next数组快速匹配的过程
八，next数组和nextval数组的相同点和不同点
1，相同点：
（1）get_next和get_nextval都是把P串和P串进行匹配，在实际匹配过程中一个个算出
（2）求next的过程和求nextval的过程都是递推
（3）用next和nextval都可以做KMP，时间复杂度都是O（n+m）
2，不同点：
（1）next的递推过程分为2步，第一步，若next[i]==j，则循环执行j=next[......next[next[j]]......]直到P[j]=P[next[j]]，第二步，直接next[i+1]=j+1，完成递推。
而nextval的递推过程也是2步，第一步同上，即若nextval[i]==j，则循环执行j=nextval[......nextval[nextval[j]]......]直到P[j]=P[nextval[j]]，第二步，循环执行nextval[i+1]=nextval[......nextval[nextval[j+1]]......]，直到得到的nextval[i+1]满足P[i+1]!=P[nextval[i+1]]
PS：因为j+1<i+1，所以nextval[j+1]已经被计算过，所以一定有P[i+1]!=P[nextval[j+1]]，所以第二步的循环，实际执行次数为0或1，所以nextval[i+1]=j+1或nextval[j+1]即可，不需要再写循环，这实际上是包含了一个动态规划的过程在里面。
（2）nextval并不满足对next数组的定义（4-5），准确来说，next[j] 定义为满足式（4-4）的最大k值，而nextval[j] 定义为既满足式（4-4）又满足T[j]!=T[k]的最大k值
九，KMP和next数组的应用
简单来说，有2大类问题，一类是字符串匹配问题，用kmp，一类是字符串周期问题，用next或者nextval
1，字符串周期问题
（1）给一个字符串，求至少添加多少字符才能变成周期串。
Cyclic Nacklace HDU - 3746
https://blog.****.net/nameof****/article/details/52131848
用next或者nextval都可以
CSU 1353: Guessing the Number 这题类似https://blog.****.net/nameof****/article/details/79806029
（2）给一个字符串，求它的最小周期
Power Strings POJ - 2406
https://blog.****.net/nameof****/article/details/79692211
用next求是可以的，能否用nextval求不清楚，好像是不行的。
POJ 1261 Period KMP 这题类似 https://blog.****.net/nameof****/article/details/52138521
2，字符串匹配问题
（1）求最大匹配数（主串匹配出来的串不能互相覆盖）
HDU 2087 减花布条
https://blog.****.net/nameof****/article/details/52137424
CSU 1598: 最长公共前缀
https://blog.****.net/nameof****/article/details/79699826
（2）求最大匹配数（主串匹配出来的串可以互相覆盖）
和不能覆盖的求匹配数问题差不多，唯一差别在于每完成一个匹配之后，j不是回溯到0，而是next[j]
（3）求第一个匹配成功的位置
Number Sequence HDU - 1711
https://blog.****.net/nameof****/article/details/79691556
（3）KMP的变形
输入2个数组a和b，在a里面找连续的一段，使得和b一样长，而且所有对应的2个数的差都是一样的。
CodeForces 471D MUH and Cube Walls
https://blog.****.net/nameof****/article/details/52219820
（4）偏序匹配问题
//待更新
3，字符串的周期和匹配综合问题
CSU 1800: 小X的标题
https://blog.****.net/nameof****/article/details/79692807