KMP算法中的nextval函數(shù)值的原理，求詳細(xì)推導(dǎo)？1 get_nextval(int *nextval，const char *string)2 {3 int num=strlen

KMP算法中的nextval函數(shù)值的原理，求詳細(xì)推導(dǎo)？

1 get_nextval(int *nextval，const char *string)2 {3 int num=strlen(string)4 int i=0，j=-15 nextval[0]=-16 while(i

kmp算法什么意思？

KMP算法之所以叫做KMP算法是因為這個算法是由三個人共同提出來的，就取三個人名字的首字母作為該算法的名字。其實KMP算法與BF算法的區(qū)別就在于KMP算法巧妙的消除了指針i的回溯問題，只需確定下次匹配j的位置即可，使得問題的復(fù)雜度由O(mn)下降到O(m n)?！?在KMP算法中，為了確定在匹配不成功時，下次匹配時j的位置，引入了next[]數(shù)組，next[j]的值表示P[0...j-1]中最長后綴的長度等于相同字符序列的前綴?！?對于next[]數(shù)組的定義如下：　1) next[j] = -1 j = 0　2) next[j] = max(k): 0<k<j P[0...k-1]=P[j-k，j-1]　3) next[j] = 0 其他　如：　P a b a b a　j 0 1 2 3 4 next -1 0 0 1 2　即next[j]=k>0時，表示P[0...k-1]=P[j-k，j-1]　因此KMP算法的思想就是：在匹配過程稱，若發(fā)生不匹配的情況，如果next[j]>=0，則目標(biāo)串的指針i不變，將模式串的指針j移動到next[j]的位置繼續(xù)進(jìn)行匹配；若next[j]=-1，則將i右移1位，并將j置0，繼續(xù)進(jìn)行比較。