Rabin-Karp Rolling Hash: Mersenne Prime Moduli (2^61 - 1) & Birthday Collision Avoidance

1. Polynomial Prefix Hashing & $O(1)$ Substring Extraction

Define the 1-indexed prefix hash array $P[0..N]$ with $P[0] = 0$ and recurrence $P[i] = (P[i-1] \cdot B + S[i-1]) \bmod M$, alongside power table $\text{powB}[k] = B^k \bmod M$. Notice that $P[R+1]$ contains $P[L]$ shifted left by $R - L + 1$ powers of $B$, plus the polynomial of $S[L..R]$:

$$P[R+1] = P[L] \cdot B^{R - L + 1} + \sum_{j=L}^{R} S[j] \cdot B^{R - j} \pmod M$$

Subtracting $P[L] \cdot \text{powB}[R - L + 1]$ modulo $M$ isolates the exact canonical hash of $S[L..R]$ in $O(1)$ time!

2. Production Implementation: Mersenne $2^{61}-1$ Rolling Hash with $O(1)$ Substring Hash & $O(\log N)$ LCP

const MOD61 = (1n << 61n) - 1n;
// Random odd base chosen per process startup in [257 .. 10^9] to defeat adversarial inputs
const RANDOM_BASE = BigInt(257 + Math.floor(Math.random() * 1000000000));

function mod61(x) {
  let res = (x & MOD61) + (x >> 61n);
  if (res >= MOD61) res -= MOD61;
  return res;
}

function mul61(a, b) {
  return mod61(a * b);
}

/**
 * RollingHash61: O(N) build, O(1) arbitrary substring hash, O(log N) substring LCP & compare
 */
class RollingHash61 {
  constructor(str, base = RANDOM_BASE) {
    this.str = str;
    this.n = str.length;
    this.pref = new BigUint64Array(this.n + 1);
    this.pow = new BigUint64Array(this.n + 1);
    this.pow[0] = 1n;

    for (let i = 0; i < this.n; i++) {
      const code = BigInt(str.charCodeAt(i));
      this.pref[i + 1] = mod61(this.pref[i] * base + code);
      this.pow[i + 1] = mul61(this.pow[i], base);
    }
  }

  // O(1) hash of closed substring str[l..r] (0-indexed); returns 0n for empty range l > r
  getHash(l, r) {
    if (l > r) return 0n;
    const sub = this.pref[r + 1] + MOD61 - mul61(this.pref[l], this.pow[r - l + 1]);
    return sub >= MOD61 ? sub - MOD61 : sub;
  }

  // O(log N) Longest Common Prefix of suffixes str[i..] and str[j..]
  lcp(i, j) {
    let lo = 0;
    let hi = this.n - Math.max(i, j);
    while (lo < hi) {
      const mid = (lo + hi + 1) >> 1;
      if (this.getHash(i, i + mid - 1) === this.getHash(j, j + mid - 1)) {
        lo = mid;
      } else {
        hi = mid - 1;
      }
    }
    return lo;
  }

  // O(log N) lexicographical comparison of substrings str[l1..r1] and str[l2..r2]
  compareSubstrings(l1, r1, l2, r2) {
    const len1 = r1 - l1 + 1, len2 = r2 - l2 + 1;
    const common = Math.min(len1, len2, this.lcp(l1, l2));
    if (common >= Math.min(len1, len2)) return len1 - len2;
    return this.str.charCodeAt(l1 + common) - this.str.charCodeAt(l2 + common);
  }
}

3. Complexity Matrix