Lesson 35.3 · Advanced String Algorithms

Rolling Hashes (Rabin-Karp)

Treat a substring as a number in base B modulo a large prime. Sliding the window by one updates the hash in O(1), so all substrings of a length can be compared quickly.

14 min

Think of it like this

A barcode for every window of text: when the window slides one letter, you can update the barcode from the old one instead of scanning the whole window again.

1.Hash, slide, verify

hash(s[i..i + L)) = s[i]·B^(L−1) + … + s[i + L − 1] (mod M). To slide: multiply by B, add the new character, subtract the character leaving times B^L. With M around 10⁹ and B like 131, keep values in long and reduce after each step.

Different strings can share a hash (a collision). Either verify candidates character by character, or use two independent hashes (or a 61-bit modulus) to make collisions negligible.

Rolling hashes shine when you compare many substrings: repeated DNA, longest duplicate substring (binary search on the length + hash set), and substring equality queries after O(n) precomputation.

Main.java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        String t = "abababa", p = "aba";
        long MOD = 1_000_000_007L, B = 131, pow = 1, hp = 0, h = 0;
        int L = p.length();
        for (int i = 0; i < L; i++) { hp = (hp * B + p.charAt(i)) % MOD; pow = pow * B % MOD; }
        List<Integer> matches = new ArrayList<>();
        for (int i = 0; i < t.length(); i++) {
            h = (h * B + t.charAt(i)) % MOD;
            if (i >= L) h = ((h - t.charAt(i - L) * pow) % MOD + MOD) % MOD;     // drop the leaving char
            int start = i - L + 1;
            if (start >= 0 && h == hp && t.regionMatches(start, p, 0, L)) matches.add(start);   // verify
        }
        System.out.println("matches at " + matches);
    }
}

Output

matches at [0, 2, 4]

2.Manacher in one paragraph

Manacher's algorithm finds the longest palindrome around every centre in O(n), with the same mirror trick as the Z-box: a centre inside a known palindrome starts with its mirror's radius. In interviews, expand-around-centre (O(n²)) is usually enough; mention Manacher when asked for linear time.

Remember

O(1) slide.
Verify or double-hash against collisions.
Great for many substring comparisons.

Common mistakes

Negative values after subtraction (add M before taking % M).
Overflow from multiplying two values near M in int.

Command Palette

Rolling Hashes (Rabin-Karp)

1.Hash, slide, verify

2.Manacher in one paragraph