



对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数组代码

网友评论