朴素模式匹配算法分析

以下是朴素模式匹配算法的过程

对于暴力算法，如果出现不匹配字符，同时回退 txt 和 pat 的指针，嵌套 for 循环，时间复杂度O(MN)，空间复杂度O(1)。最主要的问题是，如果字符串中重复的字符比较多，该算法就显得很蠢。

但实际上这种暴力解法明显多做了很多不必要的操作

KMP算法则用了一种聪明的办法，当发现字符串不匹配的时候，并不会从头开始比较，因为之前已经匹配成功的字符可以给我们提供一些有用的信息，利用这个信息我们可以将子串移动到某个位置，并从这个位置直接开始比较

朴素模式匹配算法优化

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。

如此就可以用这些记录来避免重复的操作

KMP算法的过程

比如 txt = “aaacaaab” pat = “aaab”：

类似的 txt = “aaaaaaab” pat = “aaab”，暴力解法还会蠢蠢地回退指针 i，而 KMP 算法又会耍聪明：

因为 KMP 算法知道字符 b 之前的字符 a 都是匹配的，所以每次只需要比较字符 b 是否被匹配就行了。

KMP 算法永不回退 txt 的指针 i，不走回头路（不会重复扫描 txt），而是借助 dp 数组中储存的信息把 pat 移到正确的位置继续匹配，时间复杂度只需 O(N)，用空间换时间，所以我认为它是一种动态规划算法。

KMP算法实现跳转的方法

借助数组中储存的信息把指针移到正确的位置继续匹配

算法代码实现

与朴素模式匹配算法的比较

参考内容 ：
王道数据结构
知乎 ： https://zhuanlan.zhihu.com/p/83334559
codetime： https://www.xdull.cn/kmp.html