Rabin-Karp字符串匹配算法为模式以及要比较的文本的每个M字符子序列计算哈希值。如果哈希值不相等, 则算法将确定下一个M字符序列的哈希值。如果哈希值相等, 则算法将分析模式和M字符序列。这样, 每个文本子序列只有一个比较, 并且仅当哈希值匹配时才需要字符匹配。
RABIN-KARP-MATCHER (T, P, d, q) 1. n ← length [T] 2. m← length [P] 3. h←dm-1 mod q 4. p ←0 5. t0 ←0 6. for i ← 1 to m 7. do p ←(dp + P[i]) mod q 8. t0 ← (dt0+T [i]) mod q 9. for s←0 to n-m 10. do if p = ts 11. then if P [1.....m] = T [s+1.....s + m] 12. then "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示例：对于字符串匹配, 工作模块q = 11, Rabin-Karp匹配器在文本T = 31415926535中遇到了多少假匹配。
T = 31415926535.......P = 26 Here T.Length =11 so Q = 11 And P mod Q = 26 mod 11 = 4Now find the exact match of P mod Q...解：
文章图片
文章图片
文章图片
复杂 【Rabin-Karp算法】RABIN-KARP-MATCHER在最坏情况下的运行时间为O（（n-m + 1）m, 但平均情况下运行时间很好。如果预期的强移次数较小, 则O（1）为质数q如果选择的值很大, 那么可以预期Rabin-Karp算法的运行时间为O（n + m）加上处理虚假命中所需的时间。
