For plain string search, it's definitely much slower than Boyer-Moore or KMP.
... but the cool thing about Karp-Rabin is that it generalizes well to different problems.
* 2D pattern matching (requires a little bit of thinking to implement sliding hash blocks quickly).
* matching against a set of equal length strings instead of a single string by replacing the hash equality check with a set containment check. Aho-Corasick, a generalization of KMP to this problem, will outperform this though. Note this composes with previous modification, you can do 2D pattern matching against different sets of 2D patterns, as long as they have the same dimension.
* You can use it to build a data structure to quickly let you answer queries like is substring(a, b) == substring(c, d).
My favorite use is to pick content aware variable block sizes for a block-deduping file system. Imagine before you write a block, you compute a check sum and re-use a block if you've seen it already. You want to pick blocks so that if you don't store redundant copies of content you have. Imagine you have a 1GB file A, and some modified file version A' that has a few character insertions at the beginning. Ideally, you would reuse most of the blocks for the files, since they are basically identical. The naive strategy of picking say, every 8k as a block isn't going to re-use any of the contents, because the two files aren't lined up. Instead, imagine you keep a rolling hash of length 16. Whenever the rolling hash mod 8k == 0, you start a new block. Now you'll miss some of the commonality early in the file, but eventually the same window will cause the blocks to restart in an aligned place in A and A', so you'll only store one copy of most of the data. See section 3.1.1 in this paper for more details: http://pdos.csail.mit.edu/papers/lbfs:sosp01/lbfs.pdf
Comments
For plain string search, it's definitely much slower than Boyer-Moore or KMP.
... but the cool thing about Karp-Rabin is that it generalizes well to different problems.
* 2D pattern matching (requires a little bit of thinking to implement sliding hash blocks quickly).
* matching against a set of equal length strings instead of a single string by replacing the hash equality check with a set containment check. Aho-Corasick, a generalization of KMP to this problem, will outperform this though. Note this composes with previous modification, you can do 2D pattern matching against different sets of 2D patterns, as long as they have the same dimension.
* You can use it to build a data structure to quickly let you answer queries like is substring(a, b) == substring(c, d).
My favorite use is to pick content aware variable block sizes for a block-deduping file system. Imagine before you write a block, you compute a check sum and re-use a block if you've seen it already. You want to pick blocks so that if you don't store redundant copies of content you have. Imagine you have a 1GB file A, and some modified file version A' that has a few character insertions at the beginning. Ideally, you would reuse most of the blocks for the files, since they are basically identical. The naive strategy of picking say, every 8k as a block isn't going to re-use any of the contents, because the two files aren't lined up. Instead, imagine you keep a rolling hash of length 16. Whenever the rolling hash mod 8k == 0, you start a new block. Now you'll miss some of the commonality early in the file, but eventually the same window will cause the blocks to restart in an aligned place in A and A', so you'll only store one copy of most of the data. See section 3.1.1 in this paper for more details: http://pdos.csail.mit.edu/papers/lbfs:sosp01/lbfs.pdf
This is such a great comment. Thank you.