You have a couple of fundamental problems in your code.
The first one is here: patternHash += int_mod(patternHash * base + pattern[i], primeMod);
It is duplicated on a few more places.
The second one is in calculating the rowing hash:
segmentHash += int_mod(segmentHash * base + text[i + pattern.length -1],primeMod);
segmentHash -= int_mod(segmentHash * base + text[i-1], primeMod);
Both this errors can be easily fixed. However, I will suggest you to understand better the logic behind the code instead of just copying it from somewhere. The hashing algorithm you've used is based on polynomials, so try to see what happens on that level. Maybe even write a few examples by hand -- they will be useful while debugging the code.
Note also that you will have problems with integer overflowing:
- int can store numbers which are up to ~2 billion;
- your prime module is ~1 billion so the hashes (patternHash
and segmentHash
in particular) can be up to that number;
- your base is int base = 257;
Thus, the expression segmentHash * base
can be up to ~257 billion, which will surely be an integer overflow.