简单理解KMP
本文读者可以获得两方面的知识
- 直观理解如何生成部分匹配表（下文简称匹配表），这是KMP算法的核心思想
- KMP算法的实现
算法描述
输入
- text
- pattern
输出
- text（长串）匹配到的pattern（短串）位置
常见应用
在网页中搜索关键字（常用快捷键ctrl+f）
naive方法
可以使用2层for循环，时间复杂度O(m*n)，m/n分别是text和pattern的长度
生成匹配表
只针对pattern
刚开始看KMP算法，总是看不懂的原因就是因为对匹配表的功能理解不深。尤其是试图理解KMP算法时，下一个匹配位置根据匹配表的值进行跳跃，有些人就开始问为什么了。理解匹配表之后，KMP算法自然而然就理解了。
匹配表的构建基于真前缀，真后缀，让我们先理解它们。
对于pattern='abab'来说，真前缀有
a
ab
aba
注意不包括pattern本身abab，这体现了“真”前缀而区别于前缀
同样，真后缀包含
bab
ab
b
可以发现规律：真前缀总以第一个字符开头，真后缀总以最后一个字符结尾
不要小看这个规律，它极大地帮助理解匹配表。（请再次默读一遍啊上述规律😁）
到了理解KMP算法核心的时候了，我们把pattern拉长以便更好展示，pattern='abcdeeeeabcd'，不通过真前缀和真后缀，能不能一眼看出最长匹配，还记得上边提到的规律吗？画张图帮助理解
这样找到的最长匹配就是abcd，是真前缀和真后缀匹配的最优解，时间复杂度为pattern长度的线性时间。KMP算法中的跳跃到下一个位置，简单讲就是图中左边的匹配跳跃到右边的匹配，这就是KMP算法的核心。
使用匹配表（KMP算法）
当理解了上述的匹配表生成，如何使用自然而然。
todo后续补充
网友评论