News for hackers. Stuff that matters.
Re:Faster string searching and matching with Rabin-Karp algo... by albertzeyer on Friday April 06, 2012 @10:05PM (#3809715)
It lacks an important detail: For any random hash function, the complexity is O(n * m) as in the naive implementation. You need a rolling hash function where you can get the next hash value of the next sub-string in constant type.

The implementation is also wrong. First of all, it has that detail wrong, thus it is O(n * m). But the wrong part is the comparison; it just compares the hash and not the value itself.

More about Rabin-Karp: http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm

(Btw., are those tags auto-generated? It's funny that it got the 'rolling hash' tag but the article doesn't mention it at all.)

There are no comments on this comment yet.