Rabin-Karp算法

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 = 4
Now find the exact match of P mod Q...

解：

复杂

RABIN-KARP-MATCHER在最坏情况下的运行时间为O（（n-m + 1）m, 但平均情况下运行时间很好。如果预期的强移次数较小, 则O（1）为质数q如果选择的值很大, 那么可以预期Rabin-Karp算法的运行时间为O（n + m）加上处理虚假命中所需的时间。