Rolling Hash (Rabin–Karp)

A rolling hash turns each fixed-length substring into a number, then slides the window in O(1) — drop the leading char’s contribution, multiply, add the new char.

Focus on recognizing:

“Compare many substrings” / “duplicate substring” → hash windows instead of scanning them

Pattern 1: The Rolling Formula

Rabin–Karp hunting "26" inside "3141592653" — each window reuses the previous hash with one subtract, one multiply, one add. Press ▶ to animate.

Slide a window hash over text to find a pattern match.

Precompute the pattern hash, then roll the window: subtract the leading digit·base^(m-1), multiply by base, add the new char, all mod M. When winHash == patHash, verify (here it matches '26' at index 6). O(n+m) expected.

GRID VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        patHash = hash(p), winHash = hash(first window)
                      
                        2
                        for each new right char:
                      
                        3
                          winHash -= leading digit * base^(m-1)
                      
                        4
                          winHash = (winHash * base + s[right]) % MOD
                      
                        5
                          if winHash == patHash: verify chars

For window s[i..i+m-1] with base b, mod M:

hash(i+1) = (hash(i) − s[i]·b^(m−1)) · b + s[i+m]   (mod M)

long hash = 0;
for (int i = 0; i < m; i++)          // first window
    hash = (hash * BASE + s.charAt(i)) % MOD;

long power = 1;                      // BASE^(m-1) % MOD
for (int i = 1; i < m; i++)
    power = power * BASE % MOD;

// slide: remove s[i], add s[i+m]
hash = ((hash - s.charAt(i) * power % MOD + MOD) * BASE
        + s.charAt(i + m)) % MOD;

h = 0
for ch in s[:m]:                 # first window
    h = (h * BASE + ord(ch)) % MOD

power = pow(BASE, m - 1, MOD)

# slide: remove s[i], add s[i+m]
h = ((h - ord(s[i]) * power) * BASE + ord(s[i + m])) % MOD

long long h = 0;
for (int i = 0; i < m; i++)      // first window
    h = (h * BASE + s[i]) % MOD;

long long power = 1;             // BASE^(m-1) % MOD
for (int i = 1; i < m; i++)
    power = power * BASE % MOD;

// slide: remove s[i], add s[i+m]
h = ((h - s[i] * power % MOD + MOD) * BASE + s[i + m]) % MOD;

let h = 0;
for (let i = 0; i < m; i++)
  // first window
  h = (h * BASE + s.charCodeAt(i)) % MOD;

let power = 1; // BASE^(m-1) % MOD
for (let i = 1; i < m; i++) power = (power * BASE) % MOD;

// slide: remove s[i], add s[i+m]
h =
  ((h - ((s.charCodeAt(i) * power) % MOD) + MOD) * BASE +
    s.charCodeAt(i + m)) %
  MOD;

+ MOD before subtracting keeps the value non-negative in Java/C++.

O(1) per window instead of O(m) per window — that’s the entire value of rolling.

Pattern 2: Pattern Search (Rabin–Karp)

Hash the pattern once, roll over the text, verify on hash equality:

public int search(String text, String pat) {
    int n = text.length(), m = pat.length();
    if (m > n) return -1;

    long patHash = 0, winHash = 0, power = 1;

    for (int i = 0; i < m; i++) {
        patHash = (patHash * BASE + pat.charAt(i)) % MOD;
        winHash = (winHash * BASE + text.charAt(i)) % MOD;
        if (i > 0) power = power * BASE % MOD;
    }

    for (int i = 0; ; i++) {
        if (winHash == patHash
                && text.substring(i, i + m).equals(pat))
            return i;                    // verify!

        if (i + m >= n) return -1;

        winHash = ((winHash - text.charAt(i) * power % MOD
                + MOD) * BASE + text.charAt(i + m)) % MOD;
    }
}

def search(text, pat):
    n, m = len(text), len(pat)
    if m > n:
        return -1

    pat_hash = sum(ord(c) * BASE ** (m - 1 - j)
                   for j, c in enumerate(pat)) % MOD
    win_hash = sum(ord(c) * BASE ** (m - 1 - j)
                   for j, c in enumerate(text[:m])) % MOD
    power = pow(BASE, m - 1, MOD)

    for i in range(n - m + 1):
        if win_hash == pat_hash and text[i:i + m] == pat:
            return i                     # verify!

        if i + m < n:
            win_hash = ((win_hash - ord(text[i]) * power)
                        * BASE + ord(text[i + m])) % MOD

    return -1

int search(const string& text, const string& pat) {
    int n = text.size(), m = pat.size();
    if (m > n) return -1;

    long long patHash = 0, winHash = 0, power = 1;

    for (int i = 0; i < m; i++) {
        patHash = (patHash * BASE + pat[i]) % MOD;
        winHash = (winHash * BASE + text[i]) % MOD;
        if (i > 0) power = power * BASE % MOD;
    }

    for (int i = 0; i + m <= n; i++) {
        if (winHash == patHash
                && text.compare(i, m, pat) == 0)
            return i;                    // verify!

        if (i + m < n)
            winHash = ((winHash - text[i] * power % MOD
                + MOD) * BASE + text[i + m]) % MOD;
    }

    return -1;
}

function search(text, pat) {
  const n = text.length,
    m = pat.length;
  if (m > n) return -1;

  let patHash = 0,
    winHash = 0,
    power = 1;

  for (let i = 0; i < m; i++) {
    patHash = (patHash * BASE + pat.charCodeAt(i)) % MOD;
    winHash = (winHash * BASE + text.charCodeAt(i)) % MOD;
    if (i > 0) power = (power * BASE) % MOD;
  }

  for (let i = 0; i + m <= n; i++) {
    if (
      winHash === patHash &&
      text.slice(i, i + m) === pat
    )
      return i; // verify!

    if (i + m < n)
      winHash =
        ((winHash -
          ((text.charCodeAt(i) * power) % MOD) +
          MOD) *
          BASE +
          text.charCodeAt(i + m)) %
        MOD;
  }

  return -1;
}

Hash match ≠ string match. Always verify characters on collision.

Pattern 3: Longest Duplicate Substring

Binary search the length; rolling hash detects any repeated window:

public String longestDupSubstring(String s) {
    int lo = 1, hi = s.length() - 1;
    String best = "";

    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        String dup = findDupOfLength(s, mid);  // rolling hash set

        if (dup != null) {
            best = dup;
            lo = mid + 1;          // try longer
        } else {
            hi = mid - 1;
        }
    }

    return best;
}

private String findDupOfLength(String s, int len) {
    Set<Long> seen = new HashSet<>();
    long hash = 0, power = 1;

    for (int i = 0; i < len; i++) {
        hash = (hash * BASE + s.charAt(i)) % MOD;
        if (i > 0) power = power * BASE % MOD;
    }
    seen.add(hash);

    for (int i = len; i < s.length(); i++) {
        hash = ((hash - s.charAt(i - len) * power % MOD
            + MOD) * BASE + s.charAt(i)) % MOD;

        if (!seen.add(hash))
            return s.substring(i - len + 1, i + 1);
    }

    return null;
}

def longest_dup_substring(s):
    def dup_of_length(length):
        seen = set()
        h = sum(ord(c) * BASE ** (length - 1 - j)
                for j, c in enumerate(s[:length])) % MOD
        seen.add(h)
        power = pow(BASE, length - 1, MOD)

        for i in range(length, len(s)):
            h = ((h - ord(s[i - length]) * power)
                 * BASE + ord(s[i])) % MOD
            if h in seen:
                return s[i - length + 1:i + 1]
            seen.add(h)
        return None

    lo, hi = 1, len(s) - 1
    best = ""

    while lo <= hi:
        mid = (lo + hi) // 2
        found = dup_of_length(mid)

        if found is not None:
            best = found
            lo = mid + 1           # try longer
        else:
            hi = mid - 1

    return best

string findDupOfLength(const string& s, int len) {
    unordered_set<long long> seen;
    long long h = 0, power = 1;

    for (int i = 0; i < len; i++) {
        h = (h * BASE + s[i]) % MOD;
        if (i > 0) power = power * BASE % MOD;
    }
    seen.insert(h);

    for (int i = len; i < (int)s.size(); i++) {
        h = ((h - s[i - len] * power % MOD + MOD) * BASE
            + s[i]) % MOD;
        if (seen.count(h))
            return s.substr(i - len + 1, len);
        seen.insert(h);
    }
    return "";
}

string longestDupSubstring(const string& s) {
    int lo = 1, hi = s.size() - 1;
    string best = "";

    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        string dup = findDupOfLength(s, mid);

        if (!dup.empty()) {
            best = dup;
            lo = mid + 1;          // try longer
        } else {
            hi = mid - 1;
        }
    }

    return best;
}

function findDupOfLength(s, len) {
  const seen = new Set();
  let h = 0,
    power = 1;

  for (let i = 0; i < len; i++) {
    h = (h * BASE + s.charCodeAt(i)) % MOD;
    if (i > 0) power = (power * BASE) % MOD;
  }
  seen.add(h);

  for (let i = len; i < s.length; i++) {
    h =
      ((h -
        ((s.charCodeAt(i - len) * power) % MOD) +
        MOD) *
        BASE +
        s.charCodeAt(i)) %
      MOD;
    if (seen.has(h)) return s.slice(i - len + 1, i + 1);
    seen.add(h);
  }
  return null;
}

function longestDupSubstring(s) {
  let lo = 1,
    hi = s.length - 1,
    best = "";

  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    const dup = findDupOfLength(s, mid);

    if (dup !== null) {
      best = dup;
      lo = mid + 1; // try longer
    } else {
      hi = mid - 1;
    }
  }

  return best;
}

Binary search works because “a duplicate of length L exists” is monotonic — if L works, every shorter length does too.

Common Mistakes

Trusting the hash blindly.

Collisions happen — verify actual characters before declaring a match.

Negative values after subtraction.

(h − x·power + MOD) % MOD — without + MOD, Java/C++ go negative.

Wrong power when dropping the lead.

The leading char is worth BASE^(m−1), not BASE^m.

Complexity

Operation	Time	Space
Precompute + slide	O(n)	O(1)
Search (with verify)	O(n + m) expected	O(1)
Longest duplicate	O(n log n) expected	O(n)

⚠️ Animation & Content Notice

Rolling Hash (Rabin–Karp)

Pattern 1: The Rolling Formula

⚠️ Animation & Content Notice