KMP

KMP算法

模式(Pattern)匹配，模式串就是子串，解决的是查找子串在主串中出现的位置。

暴力算法

暴力算法是对主串的每一位都进行检测，能否与模式串的第一位匹配，两层循环，最坏复杂度是O(mn)。

极端情况下，如00000000000001，和000001，每次匹配都是到最后一位才发现1和0不等，然后又重新比较，因此耗时大。

KMP思想

如果已经匹配好相等的序列里，有【后缀】 是某个【前缀】，直接把模式串向前滑动到【模式串的前缀】和【原串后缀】对齐的位置即可。

比如：

a b c d e f g

a b c g

匹配到第四位失败了，模式串应该直接向前移动三位

但是如果是：

a b a d e f g

a b a e

匹配到第四位失败了，模式串应该向前移动两位

如果是：

a a a a a a b

a a a b

匹配到第四位失败了，模式串应该向前移动