text T a b c a a a b a b a S=3 pattern a a we say that pattern P occurs with shift s in text T (or,equivalently,that pattern P occurs beginning at position s+1 in text T)if 0≤s≤n-m and T5+l.s+m=P[l.m(that is,.ifT5+j】=P[Ujl,for 1jm).If P occurs with shift s in T,then we call s a valid shift;otherwise, we call s an invalid shift.The string-matching problem is the problem of finding all valid shifts with which a given pattern P occurs in a given text T
text T a b a b a a b a b a c S=3 pattern P a b a a Algorithm Preprocessing time Matching time Naive 0 O(n-m+1)m) Rabin-Karp ⊙(m) O(n-m+1)m) Finite automaton O(mΣ) ⊙(n) Knuth-Morris-Pratt ⊙(m) ©(n)
NAIVE-STRING-MATCHER(T,P) 1 n T.length 2 m =P.length 3 for s 0 to n-m 4 ifP1..m]==T[s+1..s+m 5 print"Pattern occurs with shift"s 问题3: 为什么在最坏情况下复杂 度是平方级的?
最容易想到的算法 a a b a a a b a a b a a a b S=0 5=3 a a b a a a a b 逐位单字符比较 NAIVE-STRING-MATCHER(T,P) 1 n T.length 2 m= P.length 3 for s =0to n-m 4 ifP[1..m==T[s+1..s+m 5 print "Pattern occurs with shift"s
最容易想到的算法
问题5, Rabin-Karp算法的基本 思想是什么? For expository purposes,let us assume that=,1,2..,so that each character is a decimal digit.(In the general case,we can assume that each charac- ter is a digit in radix-d notation,where d)We can then view a string of k consecutive characters as representing a length-k decimal number.The character string 31415 thus corresponds to the decimal number 31,415