I’ve been struggling to trying to understand why the mod 997 in Rabin Karp was necessary. On a whim I removed the modulo operation and ran it through a randomly generated test case.

It seems to work just fine actually. Obviously it is overflowing quite a bit (I switched out the hashes to use unsigned integers), but the actual string matching appears to work well, even with uint8_t hashes.

A reply on StackOverflow (http://stackoverflow.com/questions/12452527/rabin-karp-hashcode-is-too-big) suggested that overflow should be ok because for unsigned ints it is itself a well-defined modulo operation.

Would it be expected that there would be fewer false hash matches with a relatively small prime mod?