Rolling Hash String Matching

Rolling Hash / String Matching Window

When To Use

Use this when every window has fixed length, but comparing raw strings or full frequency arrays would be too expensive.

Template

hash = 0
 
for r = 0; r < n; r++:
    add s[r] to hash
 
    if r - l + 1 > k:
        remove s[l] from hash
        l++
 
    if r - l + 1 == k:
        use hash

Problems Using This Pattern

Repeated DNA Sequences

Problem: find all length-10 DNA strings that appear more than once.

State: encoded rolling hash in seen and repeated sets.

Rabin-Karp Pattern Matching

Problem: find occurrences of a pattern inside a text.

State: compare rolling hash first, then confirm by string compare if needed.

Longest Duplicate Substring

Problem: find the longest substring that appears at least twice.

State: binary search the length, then scan all fixed-size hashes.

Distinct Echo Substrings

Problem: count distinct substrings that appear twice in a row.

State: use hashes to compare adjacent same-length substrings quickly.