数据结构 KMP算法及next数组求解过程

例1： ? ? ? ? ? 序号 0 1 2 3 4 5 6 7 8 子串 a b c a a b c b a Next值 -1 0 0 0 1 1 2 3 0 1，第一个字符的next值令为-1。令第二个字符b的next值为0， 初始k=0，j=1， 比较S[k] 和S[j] 2，比较S[0] ！=S[1] ?所以 ?j++ k不变 next[j=2]=0 3，比较S[0] ！=S[2] ?所以 ?j++ k不变 next[3]=0 4，比较S[0] ?==S[3] ? 所以 ?j++，k++， next[4]=k=1 5，k=1了 所以比较S[1] ！=S[4]，k返回到next[k]位置， 即k=next[1]=0,然后比较S[k=0] == S[4] 所以 j++ ，k++ ，next[5]=k=1 6，比较S[1] ==S[5] ? 所以?j++ ，k++ ，next[6]=k=2 7，比较S[2] ==S[6] ? 所以?j++ ，k++ ，next[7]=k=3 8，比较S[3] ！=S[7] ? ? 所以k返回到next[k=3]位置，即k=next[3]=0,然后比较S[k=0] ！= S[7] 所以 j++ ，不变k=0不变，next[8]=k=0 完毕 可以轻松的发现，S[j]的比较，决定了字符 S[j+1 ] 的next函数值 例二：在例一中，每次不相等时返回的都是k=next[k]=0，都是返回到了开头，我们看一个不是返回到开头0的情况： 序号 0 1 2 3 4 5 6 7 8 9 10 子串 a a b c a a a b a a c Next值 -1 0 1 0 0 1 2 2 3 1 2 从 j=5，k=1的时候开始 5，比较 S[1] == S[5] 所以 j++，k++，next[j+1=6]=k=2 6，比较S[2] != S[6] 所以?k返回到next[k=2]位置，即k=next[2]=1,然后比较S[k=1]==S[6] 所以j++，k=1+1=2，next[7]=k=2 ………… 因此，我们发现K的退回 是退回到next[k]的位置 即S[j]!=S[k]时，k=next[k] --------------------- 作者：zero9988 来源：CSDN 原文：https://blog.csdn.net/zero9988/article/details/60478388 版权声明：本文为博主原创文章，转载请附上博文链接！