-
-
Notifications
You must be signed in to change notification settings - Fork 30.6k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
rabinKarp seems to miss some matches #102
Comments
It seems to be some kind of overflow of 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. |
Given the fact that the issue is coming from 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. |
Good catch @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: Running example: https://runkit.com/dubzzz/rabin |
Incorporate tests from @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:
In order to find it, I used fast-check framework with the property:
I was not able to have a smaller example for this precise case :/
The text was updated successfully, but these errors were encountered: