Skip to content
Hello Python
Algorithm1 Practice1 Interview

Rabin-Karp

Use a rolling hash to compare many candidate substrings efficiently with collision checks. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Rabin-Karp when the prompt's constraints and required operations match this shape: Use a rolling hash to compare many candidate substrings efficiently with collision checks.

Pybit demonstrates Rabin-Karp in a professional Python interview workspace.
On this page · Compare Rolling Window Fingerprints

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Rabin-Karp Code Labs

Compare Rolling Window Fingerprints

Rabin-Karp computes a pattern hash and same-width text-window hashes. Unequal hashes reject a window quickly; equal hashes identify candidates, not proof.

Remove Leaving Add Entering

A rolling polynomial hash subtracts the leaving character’s highest-place contribution, multiplies by the base, and adds the entering character, reducing modulo m after each step.

Trace Rolling Hash Windows

Reference
def rolling_hash_trace(text,width,base,modulus):
    if width>len(text):return []
    highest=pow(base,width-1,modulus);value=0
    for character in text[:width]:value=(value*base+ord(character))%modulus
    trace=[[0,value]]
    for start in range(1,len(text)-width+1):
        value=(value-ord(text[start-1])*highest)%modulus;value=(value*base+ord(text[start+width-1]))%modulus;trace.append([start,value])
    return trace
Practice

Implement rolling_hash_trace(text,width,base,modulus). Map characters with ord and return [start,hash] for each fixed-width window.

Public tests

  • Remove leaving and append entering symbol

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Verify Every Hash Match

Different strings can collide under any fixed-size hash. Compare the actual substring or symbols whenever fingerprints match to preserve correctness.

Find Rabin-Karp Matches

Reference
def rabin_karp(text,pattern):
    if pattern=="":return list(range(len(text)+1))
    width=len(pattern)
    if width>len(text):return []
    base=257;modulus=1000000007;highest=pow(base,width-1,modulus)
    pattern_hash=window_hash=0
    for p,t in zip(pattern,text):pattern_hash=(pattern_hash*base+ord(p))%modulus;window_hash=(window_hash*base+ord(t))%modulus
    matches=[]
    for start in range(len(text)-width+1):
        if window_hash==pattern_hash and text[start:start+width]==pattern:matches.append(start)
        if start+width<len(text):window_hash=(window_hash-ord(text[start])*highest)%modulus;window_hash=(window_hash*base+ord(text[start+width]))%modulus
    return matches
Practice

Implement rabin_karp(text,pattern). Return all match starts including overlaps and verify hash candidates.

Public tests

  • Verify every fingerprint collision candidate

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Modulus Base and Collision Policy

Use a modulus and base appropriate to the symbol domain; double hashing can reduce candidate frequency but does not replace verification when correctness is exact. Empty and oversized patterns need explicit contracts.

Explain It in an Interview

Say: “The rolling hash updates each alignment in O(1), but a hash match is only a candidate, so I verify the text.” State expected O(n + m), collision-driven worst case, overlap handling, and normalization.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Rabin-Karp complete workflowO(n)O(n)Build the first polynomial hash, precompute the outgoing weight, then remove, shift, and append for every next window.

Space

O(n) for the focused Roll a Window Hash implementation.

Assumptions

  • The update removes exactly the outgoing highest-order term, multiplies remaining terms by base, and adds the incoming character, producing the polynomial hash for the next window.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Rabin-Karp invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. The retained prefix or hash state represents exactly the current candidate alignment.
  3. Text positions already passed cannot begin an unreported match.
  4. Build the first polynomial hash. Preserve this claim after every transition.
  5. Roll each next window without slicing or recomputing all characters. Preserve this claim after every transition.

When To Use Or Avoid Rabin-Karp

Use It When

  • Use Rabin-Karp when this precondition is stated or can be proved: The pattern, text, equality semantics, and reusable prefix or rolling-hash state are explicit.
  • Use it when this maintained state removes repeated work: The retained prefix or hash state represents exactly the current candidate alignment.

Choose Another Tool When

  • Avoid Rabin-Karp when this precondition is absent: The pattern, text, equality semantics, and reusable prefix or rolling-hash state are explicit.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The pattern, text, equality semantics, and reusable prefix or rolling-hash state are explicit.

Avoid

def rolling_window_hashes(text, window_size, base, modulus):
    pass

Use instead

def rolling_window_hashes(text, window_size, base, modulus):
    current = 0
    for character in text[:window_size]:
        current = (current * base + ord(character)) % modulus
    hashes = [current]
    leading_weight = pow(base, window_size - 1, modulus)
    for index in range(window_size, len(text)):
        outgoing = ord(text[index - window_size])
        current = (current - outgoing * leading_weight) % modulus
        current = (current * base + ord(text[index])) % modulus
        hashes.append(current)
    return hashes

Where you will hit this: Roll a Window Hash(opens in a new tab)

Breaking the state transition

Reuses the initial hash for every window.

Prevent it: Preserve this proof obligation: Every skipped comparison is represented by an already verified prefix or a collision-checked hash candidate.

Avoid

def rolling_window_hashes(text,k,base,modulus):
    h=0
    for c in text[:k]:h=(h*base+ord(c))%modulus
    return [h]*(len(text)-k+1)

Use instead

def rolling_window_hashes(text, window_size, base, modulus):
    current = 0
    for character in text[:window_size]:
        current = (current * base + ord(character)) % modulus
    hashes = [current]
    leading_weight = pow(base, window_size - 1, modulus)
    for index in range(window_size, len(text)):
        outgoing = ord(text[index - window_size])
        current = (current - outgoing * leading_weight) % modulus
        current = (current * base + ord(text[index])) % modulus
        hashes.append(current)
    return hashes

Where you will hit this: Roll a Window Hash(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(n).

Avoid

def rolling_window_hashes(text,k,base,modulus):
    h=0
    for c in text[:k]:h=(h*base+ord(c))%modulus
    return [h]*(len(text)-k+1)

Use instead

def rolling_window_hashes(text, window_size, base, modulus):
    current = 0
    for character in text[:window_size]:
        current = (current * base + ord(character)) % modulus
    hashes = [current]
    leading_weight = pow(base, window_size - 1, modulus)
    for index in range(window_size, len(text)):
        outgoing = ord(text[index - window_size])
        current = (current - outgoing * leading_weight) % modulus
        current = (current * base + ord(text[index])) % modulus
        hashes.append(current)
    return hashes

Where you will hit this: Lowest Common Ancestor in a BST(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.