The Modulo Went Negative

const int m = 1e9 + 9;
vector<long long> h;      // h[i] = hash of the first i characters, h[0] = 0
vector<long long> p_pow;

// hash of t[l .. l+len-1], scaled by p^l
long long sub(int l, int len) {
    return (h[l + len] - h[l]) % m;     // line 8
}

sub is compared against the pattern hash scaled the same way. The code is correct on many inputs and then silently misses matches. What is wrong, and why is it intermittent?

m is not prime, so subtraction is not well defined modulo m. Switching to $2^{61} - 1$ fixes it.

In C++ the % operator truncates toward zero, so when h[l + len] < h[l] the result is negative and can never equal the non-negative pattern hash. It should be (h[l + len] - h[l] + m) % m. It only shows up on windows where the running prefix hash happens to wrap.

long long overflows, because h[l + len] can be as large as $m^2$ . The fix is __int128.

The index is off by one: it should read h[l - 1], and it only matters when l is 0.