字符串匹配
在s（目标串）中找到t（模式串）
一、暴力匹配（BT算法）
进行匹配，如果不匹配，把模式串向后挪一位，继续从模式串的开头进行匹配
A E 不匹配，后移。
一直到匹配，或者超出目标串肯定不匹配。
代码实现：
但是这种比较方法非常低效
看上边的例子，C 和B不匹配了，按照之前的思想，应该模式串向后移动一格，但是，经过我们第一次的比较已经知道后边有一个AB，和模式串的开头的AB匹配，为什么模式串的开头不可以直接移动到A的下边呢？
故此引入KMP算法，让指针不回溯，快速匹配。
目的：让其不溯回，直接移动到目标串的第二个AB。
首先，我们继续观察第一个图，也就是下边的。
第一次匹配中，C和B不匹配时，他们之前都是匹配的，正好匹配过的目标串中第二个AB与模式串的开头相同（不管后边，因为后边的不知道，还未匹配）
1和2匹配，1和3我们也知道是匹配的（目标，还未实现），所以2和3也是相同的吧，唉？发现了叭，2和3相同，我们就能把3移动到1的地方。
而2和3相同呢，他们就是模式串中不匹配的B前边字符串的相同前缀和后缀。
如下ABCAB：
（注意后缀都顺序，还是正着来的哦）
所以，我们让计算机知道模式串每一个字母前的最长相同前缀和后缀，，当一个字母不匹配了，知道这个字母前的最长相同前缀和后缀，就能让它移动到我们想的位置。
看上边的模式串q[5], q[0] = -1,前边没有，规定为-1，而且方便之后计算。找出最长相同前缀和后缀即可
问题是每个字符串不同，怎么让计算机自己算出来的，故此我们先给出代码进行分析，
由结果入手，上边的例子中， 我们每求一个字符的nextt时，我们已经知道其前边的字符的nextt了叭，以q[4]为例；我们知道q[3]的nextt,为1，所以，q[0] 和去q[2] 是相同的，我们只要比较q[2]和q[3] 是不是相同，相同就在 next[3] 上 +1， 如果不同呢，j就看next [ next [ 3 ] ]
如上，假如求next[ 17 ], 16 和 8 不相同，我们需要看next [ 8 ] ，next [ 8 ] = 3， 我们就看3 和 16 相不相同，以此类推。
完整代码：
标签：AB,匹配,相同,后缀,模式,next,字符串 From： https://www.cnblogs.com/lyhjzx/p/16820702.html