对KMP算法的改进,主要体现在对next数组的改进上.
改进后的next数组 称之为nextval数组
减少不必要的比较
走了一段重复的路
若Pk = Pj , nextval[k] = nextval[j] = nextval[next[k]]
若Pk ≠ Pj , nextval[k] = next[k] = j
在求next[]数组时,基本上也把nextval[]数组给求出来了
发现:根本没有必要弄个next[ ]数组进来。
将next数组扔掉之后 得到最终的求nextval数组代码
网友评论