字符串匹配算法（KMP）
文章目录
1. KMP由来
- 上一节说的BM算法是最高效、最常用的字符串匹配算法。
- 最知名的却是KMP，它3位作者（D.E.Knuth，J.H.Morris，V.R.Pratt），算法的全称是Knuth Morris Pratt 算法，简称KMP算法。
2. KMP算法基本原理
类似于BM里的概念：坏字符（不能匹配的），好前缀（已经匹配的那段）
-
KMP算法目的：当遇到坏字符后，对于已经对比过的好前缀，将模式串多滑动几位
上面可以看出，可以事先预处理好模式串，与主串比较时，直接用 -
构建next数组（失效函数）
用来存储模式串中每个前缀（它们都可能是好前缀）的最长可匹配前缀子串的结尾字符下标 -
失效函数计算方法
方法1：
方法2：