关于KMP算法的简略防遗忘总结

KMP是一个相比朴素匹配要高效得多的字符串匹配算法, 在主串长度为m, 子串长度为n时, 其时间复杂度为O(m+n), 而朴素匹配则需要O(m*n).在下文中以i代指主串指针, j代指模式串指针, 所有文中描述的数组均以1作为index起始位置, 防止产生混淆.

算法本体

(1) 存在一个主串和模式串, 以及由模式串进行计算得出的模式匹配表(使用next数组进行存储)
(2) i=1, j=1
(3) 开始比较
(4) 如果在j=1时就发生失配, i=i+1
(5) 如果在j>1的位置发生失配, j=next.at(j), 完成j指针的回退
(6) 返回(3), 重复执行, 直到字符串匹配成功/全部匹配失败为止.

模式匹配表的手工计算方法

用于计算的代码实例已经很多了, 但是在有关KMP算法的博文里有关模式匹配表(即next数组)的部分要不就是用那一大坨连格式都没有的式子表示要不就是描述对我这种语文常年分数低下的人不友好. 在寻找了一些视频和资料后, 大致总结了一份方便查看的步骤. 注意, 本文只描述了一种模式匹配表的计算方法, 其他的方法还需要自己去寻找相关文章.

(1) 规定j前面的字符串作为计算对象, 前缀子串和后缀子串不能是完整字符串本身.
(2) next.at(1)设置为0, 代表了算法本体部分中的(4)
(3) next.at(j)的值为: j前面的字符串的前缀子串集合后缀子串集合中最长的相同子串的长度加1.

C++代码版本以后再补充.