rabinKarp seems to miss some matches

[dubzzz]

Hello,

I recently tried to run some property based tests on the algorithms provided in javascript-algorithms.
I discovered the following failing case with rabinKarp algorithm:

expect(rabinKarp("^ !/'#'pp", " !/'#'pp")).toBe(2); // output: -1

In order to find it, I used fast-check framework with the property:

// for any strings a, b and c
// rabinKarp(a + b + c, b) should be different from -1 (indeed b is a substring of a+b+c)
fc.assert(
  fc.property(
    fc.string(), fc.string(), fc.string(),
    (a, b, c) => rabinKarp(a + b + c, b) !== -1
  )
);

I was not able to have a smaller example for this precise case :/

[dubzzz]

It seems to be some kind of overflow of hashWord/reHashWord. With previous strings the computed hash is above Number.MAX_SAFE_INTEGER.

Number.MAX_SAFE_INTEGER; //9007199254740991
hashWord(" !/'#'pp"); //9143038766935264
reHashWord(hashWord("^ !/'#'p"), "^ !/'#'p", " !/'#'pp"); //9143038766935266

Maybe we can try to mod the hash into [-2 ** 31, 2 ** 31 -1] space in order to get rid of the issue. I will give it a try and send you an update as soon as I get something.

[dubzzz]

Given the fact that the issue is coming from word[charIndex].charCodeAt(0) * PRIME ** charIndex going above Number.MAX_SAFE_INTEGER, it means we are safe up to charIndex == 4 because 0x10ffff * 97 ** 4 < Number.MAX_SAFE_INTEGER - false for 5.

The current implementation of the algorithm should be ok - will confirm my test passes with this limit - for any word having at most 5 characters otherwise there is no guarantee that it does not overflow and goes into rounding issues.

[trekhleb]

Good catch @dubzzz

[dubzzz]

@trekhleb Would you agree on a PR adding some property based tests in this repository?

All the issues I reported so far were found using this test method. For the moment I only added them for sorting, knuth and rabin in my local fork. I think I can spend some time to check the other algorithms too.

In a nutshell:

It is a testing approach complementary to examples based tests. The idea is to check for properties:
for all (x, y, ...) such as precondition(x, y, ...) holds property(x, y, ...) is true
The framework is then responsible to generate x,y..., such as precondition holds, run the check on them and build a smaller failing case in case of failure.

Running example: https://runkit.com/dubzzz/rabin

[dubzzz]

@trekhleb Fixed by #110