Preprocessing 问题6： Rabin-Karp算法是采用“预处理” 方式的算法。何为“预处理”，这 个算法预处理的结果是什么？ 31415→ mod 13 1234567891011121314151617 1819 2359023141526739921 mod 13 8931101784510117911
Preprocessing 问题6: Rabin-Karp算法是采用“预处理” 方式的算法。何为“预处理”，这 个算法预处理的结果是什么？
Matching 31415→mod13→7 间题7： Rabin-Karp算法在“匹配”时拿 什么与什么匹配？ 这样有什么问题？是如何解决的？ 1 2 3 4 6 7 8 9 10111213141516 1718 19 2 3590 231415 267399 21 mod 13 89311017845 10 11 valid spurious match hit 什么意思？
Matching 什么意思？
问题8： 对T中每个长度为m的子串在匹配前 都必须计算它的“值”，这个计算 是如何被“简化”的？ 递推的方法 old new old new high-order low-order high-order low-order digit digit digit shift digit 314152 14152=(31415-310000)10+2(mod13) ≡(7-33)10+2(mod13) ≡8(mod13) 78
问题8: 对T中每个长度为m的子串在匹配前 都必须计算它的“值”，这个计算 是如何被“简化”的？ 递推的方法
RABIN-KARP-MATCHER(T,P,d,q) 1 n T.length 问题9 2 m P.length 3 h=dm-1 mod g 影响复杂度的 4p=0 关键是什么？ 5 to=0 6 for i 1 to m ∥preprocessing 7 p =(dp+p[il)mod g 8 to =(dto +T[il)mod q 9 for s =0to n -m ∥matching 10 if p==ts 11 if P[1..m]==T[s +1..s +ml 12 print“Pattern occurs with shift”s 13 if s n-m 14 ts+1=(d(ts -T[s +1]h)+T[s +m +1])mod q
Rabin and Karp proposed a string-matching algorithm that performs well in prac- tice and that also generalizes to other algorithms for related problems,such as two-dimensional pattern matching.The Rabin-Karp algorithm uses (m)prepro- cessing time,and its worst-case running time is((n-m+1)m).Based on certain assumptions,however,its average-case running time is better. 问题10： 这是书上开始介绍Rabin-Karp 算法时的第一段话，现在你能 解释一下了吗？