【正文】 S[ik+1..i1] == T[1..k1] k j S(ij) S1 … … S(ij+1) S (i1) … S n S i … p 1 p (j1) … p m p j 主串： S1 … Sn 子串： P1 … Pm p(jk+1) p(j1) … p1 p(k1) … … p1 p(k1) … p m p j1 p k p j … S(ij) S1 … … S(ij+1) S (i1) … S n S i S(ik+1) S(i1) … p(jk+1) p(j1) … S(ik+1) S(i1) … i i j j 定義： 模式串的 next函數 ????????????????????其它情況當此集合不空時且時當, 1 , }39。pp39。39。ppp39。jk1|M a x { k1j, 0[ j ]1j1kj1k21??n e x tj 1 2 3 4 5 6 7 8 模式 a b a a b c a c Next[j] 0 1 1 2 2 3 1 2 int Index_KMP(SString S, SString T, int pos) { // 1≤pos≤StrLength(S) i = pos。 j = 1。 while (i = S[0] amp。amp。 j = T[0]) { if (j = 0 || S[i] == T[j]) { ++i。 ++j。 } // 繼續(xù)比較后繼字符 else j = next[j]。 // 模式串向右移動 } if (j T[0]) return iT[0]。 // 匹配成功 else return 0。 } // Index_KMP 這實際上也是一個匹配的過程， 不同在于：主串和模式串是同一個串 . 求 next 函數值的過程是一個遞推過程， 分析如下 : 已知 ： next[1] = 0； (1)若 ： T[j] = T[k] , 則 ： next[j+1] = k+1 (2)若 ： T[j] ? T[k] , 則 需往前回朔 , 假設 ： next[j] = k。 檢查 T[j] = T[?] ? T[j] = T[next[k]] ?j 1 2 3 4 5 6 7 8 模式 a b a a b c a c Next[j] 0 1 1 2 2 3 1 ? 如何求 next[6]? 當前 j=5,next[5]=2, 考察 p5 與 p2 ： p5 = p2 ， 所以 next[6]=next[5]+1， 如何求 next[7]? 當前 j=6,next[6]=3, 考察 p6 與 p3 ： p6 p3 ， next[3]=1，繼續(xù) 考察 p6 與 p1 ： p6 p1 ， next[1]=0，則 next[7]=1，從頭開始比較。 void get_next(SString amp。T, int amp。next[] ) { // 求模式串 T的 next函數值并存入數組 next。 i = 1。 next[1] = 0。 j = 0。 while (i T[0]) { if (j == 0 || T[i] == T[j]) {++i。 ++j。 next[i] = j。 } else j = next[j]。 } } // get_next 還有一種特殊情況需要考慮： 例如： S = ?aaabaaabaaabaaabaaab? T = ?aaaab? next[j]= 01234 nextval[j]= 00004 (調整后的 next值 ) 若 pj = pnext[j],則 Next[j]= Next[Next[j]] void get_nextval(SString amp。T, int amp。nextval[]) { i = 1。 nextval[1] = 0。 j = 0。 while (i T[0]) { if (j == 0 || T[i] == T[j]) { ++i。 ++j。 if (T[i] != T[j]) next[i] = j。 else nextval[i] = nextval[j]。 } else j = nextval[j]。 } } // get_nextval t=?abcaabbabcab?，寫出用 KMP算 法求每個字符的 next和 nextval函數值。 j 1 2 3 4 5 6 7 8 9 10 11 12 模式 a b c a a b b a b c a b Next 0 1 1 1 2 2 3 1 2 3 4 5 val 0 1 0 1 1 0 練 習 t=?abcaacabaca?，寫出用 KMP算法 求每個字符的 next和 nextval函數值。 練 習 j 1 2 3 4 5 6 7 8 9 10 11 模式 a b c a a c a b a c a Next 0 1 1 1 2 2 1 2 3 2 1 val 0 0 1 0 作 業(yè) 已知主串 t=?abcaabbabcabaacbacba?，模式串 p=?abcabaa?，要求： (1)計算模式 p的 next和 nextval值； (2)不寫出算法，畫出利用 KMP算法進行模式匹配時每一趟的匹配過程。