字符串匹配 蛮力方法 O(N^2)

KMP与MP的区别

这是MP

这是KMP
对于ABCABCC这样的一个子串，假设我们匹配到第六位的时候失败了（也就是第二个C的位置）。
那么往前看，ABCAB中，AB是相同的，因此我们可以回退到第三位，就是第一个C的位置进行匹配。

KMP算法呢？因为第六位失败了，所以我们知道第三位的C页肯定匹配不成了，因此再往后前进一位，到第四位开始。
其实区别就在这。

MP算法时间复杂度

AC自动机
匹配失败就跳转到后缀。

BM算法

一共算三个表格
下面以模式GCAGAGAG为例

坏字符表

这个表好算。从右往左算字符的下标就行了。不能是最后一个字母，比如G，你得算第二次出现（我觉得意思就是没有0）。

辅助表suffix

小纸带算法
以i=6为例，就是比较GCAGAGA与GCAGAGAG的最长公共后串（把它们两个后对齐）
GCAGAGA
GCAGAGAG

就是不断把上面那一行向右位移的算法，是不是很像小纸带？

bmGs表格

例子里只有这个case1