Roll a Window Hash

Practice Exercise Intermediate Medium Array String Rabin-Karp

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement rolling_window_hashes(text, window_size, base, modulus). Use ord(character), polynomial left-to-right hashing, and return each window hash. Inputs satisfy 1 <= window_size <= len(text) and modulus > 0.

Starter code

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

Test cases

roll-windows

{
  "args": [
    "abcd",
    2,
    31,
    1000
  ]
}

Expected: [105,137,169]

whole-text

{
  "args": [
    "abc",
    3,
    31,
    1000
  ]
}

Expected: [354]

Wizard outline

Step 1: Hash the first complete window
Build the polynomial hash for text[:window_size]. Every later hash updates this first complete window.
Step 2: Roll to the second window
Remove the leading character and append one incoming character. Rolling reuse avoids recomputing the shared window suffix.
Step 3: Roll across every complete window
Repeat the rolling transition for the rest of the text. The same outgoing and incoming index relationship holds for every window.

Footguns and prerequisites

Using base**window_size removes the wrong positional weight.
Forgetting modulus after subtraction can break a language-independent hash contract.
strings

Reviewed references

Python More on Lists

Recommended approach and implementation

Build the first polynomial hash, precompute the outgoing weight, then remove, shift, and append for every next window.

Why it works: 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.

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