2|34|5678|91 r ba blabla al x17|002345|60 P a aba KMP-MATCHER(T, P) 2 m+lengthIP Lalblalblablabea N+COMPUTE-PREFIX-FUNCTION(P D Number of characters matched I blabber do while q>0 and Pla+11≠ D Next character does not match ifP1a+1]=T0 then g-g+I D Next character matches D Is all of p matched 8 ia bb a be a x 2-o then print“ Pattem occurs with shift”-m D Look for the next match. COMPUTE-PREFIX-FUNCTION(P) BM算法 2t[l]←0 he Boyer-Moore algorithm 4forq←2tom 5 do while k>0 and PIk+1]= plal 种从右边开始进行匹配的算 dok←r[k 法 if P[k +1]=Plal then k←k+1 rq]←k l0 returnπt 66 31 a b a a b a b a Pq Pk 32 1 2 3 4 5 6 7 8 9 10 a b a b a b a b c a 0 0 1 2 3 4 5 6 0 1 33 a b a b a b a b a b a b a b a b a b a b P8 P6 P4 P2 P0 c a a b c a π[8]=6 a b a b c a π[6]=4 a b a b a b c a π[4]=2 ε a b a b a b a b c a π[2]=0 34 KMP-MATCHER(T, P) 1 n←length[T] 2 m←length[P] 3 π←COMPUTE-PREFIX-FUNCTION(P) 4 q ← 0 Number of characters matched. 5 for i ← 1 to n Scan the text from left to right. 6 do while q > 0 and P[q + 1] ≠ T[i] 7 do q ← π[q] Next character does not match. 8 if P[q + 1] = T[i] 9 then q ← q + 1 Next character matches. 10 if q = m Is all of P matched? 11 then print “Pattern occurs with shift” i － m 12 q ← π[q] Look for the next match.       35 COMPUTE-PREFIX-FUNCTION(P) 1 m←length[P] 2 π[1] ← 0 3 k ← 0 4 for q ← 2 to m 5 do while k > 0 and P[k + 1] ≠ P[q] 6 do k ← π[k] 7 if P[k +1] = P[q] 8 then k ← k +1 9 π[q] ← k 10 return π 36 BM算法 • The Boyer-Moore algorithm • 一种从右边开始进行匹配的算 法