温馨提示：本篇属于总结，难免有疏漏和错误，如有发现建议直接囸作者，欸嘿
课上老师提到了KMP，下来了解了一下——md感觉瞬间懵逼（这就是马鹿吗i了i了）
KMP简介是这样的：
其中对核心要素next数组是这么介绍的：
最核心的next求法明白了，基本上KMP就没问题了。但是不幸的是，这玩意儿特别绕……
最长相等前后缀：
我们先看一下一个例子：abbcbabcc
这里对于他每一位字符而言，都会有一个对应的最长相等前后缀，针对倒数第二个c而言，我们可以画个图：
红框对应的就是一对最长相等前后缀，注意这里的“对称”并非是镜像的，而应该是以“a”，“a b”为整体的中心对称。
现在再回到next求法上面。
关于NEXT：
这里的方程其实给人一种动态规划的状态转移方程的感觉（然而这个其实不是），但是问了一些ACM大手子，他们认为确实用了动态规划的一些思想但是缺少最优子结构什么的……
我觉得KMP有dp的思想，但不能算dp，你可以认为它做了两个事情：构造状态转移关系和根据关系转移，但是并没有明确的最优子结构和转移方程，硬要说的话，更接近记忆化搜索或者自动机
上面定义中，next[0]=-1是为了算法方便做的改动（实际j=0和j=-1都对应0）
在这个过程中，最重要的其实就是确定当前的Max{k}，我们先看看GetNext代码：
next[j]=k是记录当前最长相等前后缀长度，但是k=next[k]呢？这里就是理解这个函数的最大障碍，要弄清楚这个原理，我们再看看字符串中的对称：
$$
比如“abcdeabcdef”这个字符串
$$
字符串中“e”元素对应最长相等前后缀其实就是“abcde”，我们可以这么划分一下：
【abcde】【abcde】f
此时元素“f”出现了不匹配，那么我们就要找到一个新的最长相等前后缀，而这个新的最长相等前后缀肯定是小于“abcde”且除新的“f”元素以外都包含于“abcde”的，此时由于【abcde】【abcde】f中两个“abcdef”彼此对称，我们就可以把k回溯至开头的“abcde”后进行判定。
如此反复调用之前记录过的next[k]数据，即可求得新的最长相等前后缀。这里有两篇教程：
https://www.cnblogs.com/dusf/p/kmp.html
BMP的优化：
实际上，现在我们一般用的BMP算法与上面我们推导出来的还有一些细微的不同——BMP还可以进一步优化，省去一些不必要的过程。
这里我们看一下目标串与模板串进行比对的函数：
其实我们的优化就是利用中间标红的“j=next[j]”，对GetNext函数进行优化
在比对过程中，可能会出现这样的状况：
可以看到其实“d”在与“c”判断后，接下来几个连续与“a”的判断是多余的，因此要更改判断方式使相同的字符不会被重复选取。
上图红色部分的意思是如果有t[j]==t[k]了，那么就说明KMP函数中调用next[j]肯定会出现重复，于是我们就直接跳过他调用next[k]（若再出现一致则重复递归）。
附上详细讲解：
KMP算法大致就是这样运行的，建议再做两道题巩固一下o(*￣▽￣*)o~
好了，话也说完了，那差不多就该
