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）加上处理虚假命中所需的时间。
