KMP算法是一种改进的字符串算法
KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数。函数本身包含了模式串的局部匹配信息。
移动位数=已匹配的字符数-对应的部分匹配值
《部分匹配表》是如何产生的？
部分匹配值就是前缀和后缀的最长的元素的长度。
- 前缀，是指除了最后一个字符以外，一个字符串的全部头部组合；
-
后缀，指除了第一个字符串以外，一个字符串的全部尾部组合。
比如ABCDABD的算法
b15831994b1f1284bca34999ca229a8.png
next（j）取值过程，见视频03
网友评论