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