dea o f Rabin-Karp algorithm tu+i can be computed from ts in constant time, since ts+1=10(5-10m7s+1)+7s+m+1 Constant is precomputed which can be done in time o(gm) For example, if=5 and t=31415, then we remove the high-order digit T[s+1-3 and bring in the new low-order digit T[s +5+1]=2 to obtain 10(31415-10000·3)+2 14152
Constant is precomputed which can be done in time O (lgm ) Idea of Rabin-Karp algorithm ts+1 can be computed from ts in constant time, since, ts+1 = 10( ts − 10 m − 1 T[s + 1]) + T[ s + m + 1]. For example, if m = 5 and ts = 31415, then we remove the high-order digit T[ s + 1] = 3 and bring in the new low-order digit T[ s + 5 + 1] = 2 to obtain ts+1 = 10(31415 − 10000 · 3) + 2 = 14152
Improved Rabin-Karp algorithm ts+1=(10(-11s+1h)+Ts+m+1)modq g is typically chosen as a prime such that 10g just fits within one computer word h=10 -(mod g)
Improved Rabin-Karp algorithm ts+1 = (10( ts − T[ s + 1] h) + T[ s + m + 1]) mod q. y q is typically chosen as a prime such that 10 q just fits within one computer word. 1 10 m h − y ≡ (mod q )
Improved Rabin-Karp algorithm old high new low order digit 8 order digit 314 1 52 7 14152≡10·(31415-310000+2(mod13) =10·(31415-3·3)+2(mod13) 8(mod13)
Improved Rabin-Karp algorithm 3 1 4 1 5 2 7 8 old highorder digit new low- order digit 14152 10 (31415 3 10000) 2 (mod13) ≡ ⋅ −⋅ + ≡ ⋅ −⋅ + 10 (31415 3 3) 2 (mod13) ≡ 8 (mod13)
Improved Rabin-Karp algorithm 123456789101112131415161718 2|=|59o2|3 1415 267|3|9|9|2 89|31101784510117911 mod 13 Valid match Spurious hit s= p(mod g) does not imply that ts-p
Improved Rabin-Karp algorithm 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 8 9 3 11 0 1 7 8 4 5 10 11 7 9 11 1 10 11 2345678 9 12 13 14 15 16 18 17 ... ... mod 13 Valid match Spurious hit st p ≡ (mod q ) does not imply that ts = p
Rabin-Karp algorithm RABIN-KARP-MATCHER(T, P, d, g) 1.n← length[ 2.m← length 3.h←dm- mod q Preprocessing 4.p←0 0 6.fori←ltom ∥ Preprocessing 7.dop←(cp+P[)modq Matching 8.doto←(do+7ij)mod 9.fors←0ton-m∥ Matching 10. do if p=t then if P[1l….m]=7[s+1….s+m] 12 then print "Pattern occurs with shift" s 13 ifs<n 14 then ts+1+((ts- T[s+I]h)+T[s+m+lD mod q
Rabin-Karp algorithm RABIN-KARP-MATCHER ( T, P, d, q ) 1. n ← length [ T ] 2. m ← length [ P ] 3. h ← d m −1 mod q 4. p ← 0 5. t 0 ← 0 6. for i ← 1 to m // Preprocessing. 7. do p ← (dp + P [ i]) mod q 8. do t 0 ← (dt 0 + T[ i]) mod q 9. for s ← 0 to n − m // Matching. 10. do if p = ts 11. then if P[1 ... m] = T [ s +1 ... s + m ] 12. then print "Pattern occurs with shift" s 13. if s < n − m 14. then ts+1 ← ( d ( ts − T [s + 1] h) + T [ s + m + 1]) mod q Preprocessing Ф ( m ) Matching O(( n − m + 1) m )