Rabin–Karp: How Rolling Hash Finds a Pattern

Rabin–Karp is a pattern-search technique built around a simple question: instead of comparing a pattern with every text window character by character, can we give each window a compact numerical fingerprint and compare fingerprints first?

The supplied example makes that idea concrete with a ten-digit text and a four-digit pattern. A four-digit section of the text can be represented as a number. The next four-digit section can also be represented as a number. If the two numbers are different, the pattern cannot match that window. If the numbers are equal, the window becomes a candidate match and must still be checked directly.

That last step is essential. An equal fingerprint is evidence that two pieces may be equal, not absolute proof that they are equal. The modulus used to keep fingerprints manageable can cause different windows to produce the same fingerprint. Rabin–Karp therefore combines two ideas:

1. Compute a fingerprint for the pattern and for each text window.
2. Verify the actual characters when fingerprints agree.

The important efficiency idea is the rolling update. When the window moves one position to the right, most of its contents are unchanged. Rather than rebuilding the new window’s number from scratch, Rabin–Karp removes the old leading digit, shifts the remaining digits, and adds the new trailing digit. This update takes constant time for a fixed-size window.

The problem: find a short pattern inside text​

Suppose the text is the ten-digit sequence:

1234567890

Suppose the pattern has four digits:

4567

The goal is to determine whether the four-digit pattern appears in the ten-digit text and, if it does, where it begins.

A direct approach would inspect each possible four-digit window:

1234
2345
3456
4567
5678
6789
7890

There are seven possible windows because the text has ten digits and the pattern has four digits. Each window has the same length as the pattern, so it is a possible place for a match.

The window 4567 is the desired one. The question is how to compare these windows with the pattern without repeatedly doing the same work.

Representing a window as a number​

For this decimal example, the four-digit window 1234 can be represented by the number 1234. The next window, 2345, can be represented by 2345, and so on.

The pattern 4567 has a numerical representation of 4567.

The first comparison can therefore be written conceptually as:

fingerprint(pattern) = 4567
fingerprint(first window) = 1234

Because 4567 and 1234 are different, the first window cannot be the pattern. There is no need to compare all four positions in that window before rejecting it.

The same idea applies to the next windows:

pattern: 4567
window:  2345

The fingerprints differ, so the window is rejected as a match candidate.

Eventually, the window becomes:

pattern: 4567
window:  4567

The fingerprints are equal. This window is now a candidate. Rabin–Karp performs a direct comparison of the pattern and the window to confirm that the digits really agree.

For this simple decimal example, the number itself looks like an exact representation. In a general text-search setting, the fingerprint is usually treated as a hash value rather than as an unlimited exact number. The central algorithmic idea remains the same: compare compact fingerprints first, then verify a possible match.

Why rebuilding every window repeats work​

Consider the first two windows:

1234
2345

They share three digits:

1234
 2345

The digits 2, 3, and 4 are already part of the old window and remain part of the new one. Recomputing the entire number 2345 from all four digits repeats work that the previous window already made available.

The same overlap appears at every step:

1234 -> 2345
2345 -> 3456
3456 -> 4567

Each move discards exactly one digit and introduces exactly one new digit. The remaining digits move one place toward the front of the window.

A rolling hash takes advantage of this overlap. Instead of asking, “What is the fingerprint of this four-digit sequence from nothing?” at every position, it asks, “How can I update the previous fingerprint after one digit leaves and one digit enters?”

That is the source of the rolling behavior.

Rolling from 1234 to 2345​

Start with the four-digit window:

1234

Move one position right. The new window is:

2345

The old leading digit is 1. For a four-digit window, its place value is the thousands place, so its contribution is:

Remove that contribution from 1234:

The remaining value represents the last three digits, 234. To make room for the new trailing digit, shift those three digits left by one decimal place:

Now add the incoming digit 5:

The new value is exactly the representation of the new window.

In compact form:

The update does not reconstruct the new window by separately reading all four digits. It uses the previous value, removes the digit that is no longer present, shifts, and adds the one new digit.

Continuing the roll​

The same process moves from 2345 to 3456:

Then from 3456 to 4567:

The window fingerprint has now reached the pattern fingerprint. That equality triggers verification.

The comparison is:

pattern: 4567
window:  4567

The four digits agree, so this is a confirmed match.

A general rolling formula​

For a window of length four in base 10, the leading digit has place value 1000. If the old window value is $H$, the outgoing digit is $a$, and the incoming digit is $b$, the next window value can be described as:

This formula expresses the same three actions:

1. Remove the outgoing digit’s highest place-value contribution.
2. Shift the remaining value left by one decimal position.
3. Add the incoming digit.

The number 1000 is determined by the window length and the base. For a four-digit decimal window, it is $10^3$. More generally, for a window of length $m$ in base $d$:

The shift factor is 10 because the example uses decimal digits.

The formula is useful because it makes the repeated-work avoidance explicit. The new fingerprint is derived from the old fingerprint and the two digits at the boundary of the move. The rest of the window is carried forward implicitly.

Why use a modulus?​

The description of the technique highlights the role of the modulus. A modulus keeps the fingerprint within a controlled numerical range. Instead of allowing values to grow without limit as text is processed, the algorithm can reduce intermediate values modulo a chosen number.

Conceptually, a fingerprint can be maintained as:

where $M$ is the modulus. The rolling update then becomes:

The modulus matters because it changes the fingerprint space. If many possible windows are mapped into a smaller set of values, different windows may receive the same fingerprint. This is the source of a possible collision.

For example, imagine a deliberately tiny modulus of 10. Then the values 1234 and 1244 have the same remainder:

The windows are not equal, but their fingerprints are equal under this small modulus. Therefore, an equal fingerprint cannot by itself establish that the pattern is present.

The modulus is useful for controlling numerical size, but it introduces the need for candidate verification. Rabin–Karp handles that trade-off directly: fingerprints make most unequal windows easy to reject, while direct comparison resolves equal-fingerprint cases.

An equal fingerprint is only a candidate​

This is the most important correctness point in the method.

Suppose the pattern fingerprint is $r$, and a text window also has fingerprint $r$. There are two possibilities:

1. The window really equals the pattern.
2. The window is different but happens to produce the same fingerprint.

The second case is a collision. It does not mean the rolling hash has failed. It means the fingerprint is being used as a filter rather than as the final proof of equality.

The algorithm responds by checking the original contents:

if windowFingerprint == patternFingerprint:
    compare pattern and window directly

If the direct comparison succeeds, the match is confirmed. If it fails, the equal fingerprint was only a collision, and the search continues with the next window.

In the ten-digit example, when the rolling value reaches the pattern’s value, we inspect the corresponding four digits. The fingerprint points to a possible match; the actual digits decide whether the match is real.

This separation between filtering and verification is valuable. Fingerprints provide a compact first test, but the original text remains the authority when the fingerprints agree.

Walking through the complete example​

Let the text be:

1234567890

Let the pattern be:

4567

The pattern length is four, so the text is examined through four-digit windows.

Window 1: 1234​

The initial window is represented as 1234. The pattern is represented as 4567.

window fingerprint: 1234
pattern fingerprint: 4567

The fingerprints differ. Reject the window.

Window 2: 2345​

Roll the window:

Compare 2345 with 4567. They differ. Reject the window.

Window 3: 3456​

Roll again:

Compare 3456 with 4567. They differ. Reject the window.

Window 4: 4567​

Roll again:

The fingerprints are equal. Verify the original four digits:

4567 = 4567

The match is confirmed.

Remaining windows​

The search can continue if the goal is to find every occurrence rather than stop at the first one. The next windows are 5678, 6789, and 7890. Each is reached by another rolling update and compared with the pattern fingerprint.

The same procedure is used at every position: update, compare fingerprints, and verify only when they agree.

What “constant time” means here​

The description specifically emphasizes that the rolling update can be performed in constant time. For one shift of a fixed-size window, the algorithm uses a fixed set of arithmetic actions:

remove the outgoing contribution
shift the remaining value
add the incoming digit

The amount of arithmetic does not grow because the window moves from the beginning of the text toward the end. The update from 1234 to 2345 and the update from 6789 to 7890 have the same basic structure.

This is different from rebuilding every window by processing all four digits again. With a four-digit pattern, that direct rebuilding involves four positions per window. The rolling update reuses the previous fingerprint and processes the boundary change instead.

The phrase “constant time” applies to the update operation described here. It does not mean that the entire search finishes after one operation. The text still has multiple possible windows, and the algorithm still moves through them. The benefit is that each movement can update the numerical state without reprocessing the unchanged interior of the window.

Why verification remains necessary even when numbers look exact​

In the simplest decimal illustration, the window 4567 is represented by the exact number 4567. It may seem that equal numbers should always prove equal windows. However, the description calls attention to the modulus, and modular fingerprints are not one-to-one for all possible inputs.

Once values are reduced modulo $M$, the fingerprint records a remainder rather than the unrestricted original value. Multiple values can share that remainder. Consequently, an equal modular fingerprint identifies a candidate, not necessarily a confirmed match.

The correct mental model is:

fingerprint equality  -> possible match
content equality      -> confirmed match

This distinction prevents a common mistake: returning a match as soon as the hash values agree. A reliable Rabin–Karp search performs the direct check whenever a fingerprint equality occurs.

A small collision example​

Use a small modulus to make the collision visible. Suppose two different window values are:

window A: 1234
window B: 1244

With modulus 10, both fingerprints are 4:

If the pattern’s fingerprint is also 4, both windows would pass the fingerprint test. But only one could be equal to a particular pattern. Direct comparison separates the genuine match from the false candidate.

This tiny example is not intended as a choice of modulus for a practical search. Its purpose is to show why a modulus creates a compact fingerprint and why that compactness can merge distinct values into one fingerprint.

The algorithm’s response is not to trust the collision. It verifies the underlying window.

The pattern fingerprint is prepared once​

Before scanning the text, Rabin–Karp computes the fingerprint of the four-digit pattern. It also computes the fingerprint of the first four-digit text window. These two values establish the initial comparison.

After that, the pattern fingerprint remains unchanged while the text-window fingerprint rolls forward. The search repeatedly compares:

fixed pattern fingerprint
against
current window fingerprint

This arrangement is practical because the pattern is the same at every position. There is no reason to recompute its fingerprint for every text window.

For the example:

pattern fingerprint: 4567
initial text-window fingerprint: 1234

The text-side value changes as the scan advances, while the pattern-side value is reused.

The boundaries of the scan​

A four-digit pattern can begin at the first digit of the ten-digit text, but it cannot begin so late that four digits would extend beyond the text. The possible windows are therefore exactly the four-digit sections listed earlier:

1234, 2345, 3456, 4567, 5678, 6789, 7890

The first window is built directly. Every later window is generated by removing one leading digit and adding one trailing digit. Once the final four-digit window has been considered, there are no more complete windows to inspect.

This boundary behavior is important in an implementation: the rolling operation is performed only when a new trailing digit exists. The search should not treat an incomplete suffix as a full candidate window.

The method as a filtering pipeline​

Rabin–Karp can be understood as a three-stage pipeline:

Stage 1: maintain a fingerprint​

The algorithm stores a compact numerical representation of the pattern and the current text window.

Stage 2: reject unequal fingerprints​

If the fingerprints differ, the window cannot equal the pattern, so the algorithm advances without a direct character-by-character confirmation.

Stage 3: verify equal fingerprints​

If the fingerprints agree, the window is a candidate. The algorithm checks the actual digits to determine whether the candidate is a real match or a collision.

This structure avoids unnecessary detailed comparisons for windows whose fingerprints already differ, while preserving correctness by checking every possible collision.

What repeated work the rolling hash avoids​

The unchanged portion of adjacent windows is the key source of repeated work.

For these windows:

3456
4567

The digits 4, 5, and 6 appear in both. A fresh calculation would process all four digits of 4567. A rolling calculation carries the shared portion through the previous fingerprint, removes 3, shifts the shared digits, and adds 7.

The same pattern occurs throughout the scan. Adjacent windows overlap heavily when the pattern is short relative to the text. Rolling computation turns that overlap into reusable state.

The technique is therefore not merely a trick for decimal numbers. The ten-digit example makes the arithmetic visible, but the underlying principle is broader: represent a fixed-length window numerically, and update that representation when the window shifts by one position.

Practical interpretation for text search​

Rabin–Karp is naturally connected to text search because the task is to locate a pattern inside a larger text. The example uses digits so that the window value and its update can be seen without additional encoding details.

For a text-search interface, the conceptual flow is similar:

pattern entered by the user
text scanned as overlapping windows
fingerprints compared first
candidate windows verified directly

The rolling update is especially useful when the search proceeds through many adjacent windows. The next window differs from the current one at its boundaries, while most of its content is shared. Rather than treating every window as unrelated, the algorithm carries the previous fingerprint forward.

The same reasoning applies whether the visible symbols are digits or characters: the key requirements are a fixed-length pattern, a current window of the same length, a fingerprint representation, and a way to update the fingerprint when one symbol leaves and one enters.

Practical trade-offs​

Rabin–Karp trades a small fingerprint comparison for a possible verification step. When fingerprints differ, the window is rejected quickly. When fingerprints agree, the algorithm must inspect the underlying window because the modulus may have produced a collision.

A modulus that produces a compact range makes fingerprints convenient to maintain, but a smaller fingerprint space can allow more distinct windows to share a fingerprint. A larger or otherwise better-distributed fingerprint space can reduce the chance of accidental equality, but the algorithm still needs the verification rule if correctness depends on distinguishing the original windows.

The central trade-off can be summarized as follows:

smaller, easier-to-manage fingerprints
versus
more possible fingerprint collisions

Verification is the mechanism that makes the approach safe in the presence of those collisions.

Common mistakes to avoid​

Treating equal fingerprints as confirmed matches​

This is the most serious mistake. Equal fingerprints identify candidates. The original pattern and window must be compared before reporting a match.

Forgetting the outgoing digit’s place value​

When rolling from a four-digit window, the first digit contributes at the thousands place. Removing only the digit value rather than its place-value contribution produces the wrong next fingerprint.

For example, rolling from 1234 requires removing 1000, not merely removing 1:

Shifting in the wrong direction​

After the leading digit is removed, the remaining digits need to move toward the higher place values before the incoming digit is added:

Rolling past the final complete window​

The algorithm should update only when there is a new incoming digit. Once 7890 is the final complete four-digit window, no further four-digit candidate begins within the ten-digit text.

Losing sight of the modulus​

If a modular fingerprint is used, all relevant updates must be interpreted consistently under the chosen modulus. The modulus is not an afterthought; it is part of the fingerprint definition and part of the reason verification is required.

A compact conceptual pseudocode outline​

The following outline captures the method without tying it to a particular programming language:

compute the pattern fingerprint
compute the fingerprint of the first text window

for each complete text window:
    if window fingerprint equals pattern fingerprint:
        compare the actual pattern and window
        if they are equal:
            report a match

    if another window exists:
        remove the outgoing digit contribution
        shift the remaining fingerprint
        add the incoming digit
        apply the modulus as required

The first window is initialized before the scan. Every later window is obtained from the previous one by the rolling update. The direct comparison appears only after fingerprint equality.

A final walk-through in plain language​

Imagine a four-digit frame sliding across the ten-digit text 1234567890. The frame first covers 1234. Rabin–Karp records its fingerprint and compares it with the pattern fingerprint for 4567.

The frame moves right. The 1 leaves, the 5 enters, and the fingerprint is updated to represent 2345. The algorithm does not need to rebuild the whole four-digit value from the beginning.

The frame moves again. The 2 leaves, the 6 enters, and the fingerprint becomes 3456.

The frame moves once more. The 3 leaves, the 7 enters, and the fingerprint becomes 4567.

Now the pattern and window fingerprints agree. This is not yet the final answer because a modulus could have caused a collision. The algorithm compares the actual window 4567 with the actual pattern 4567. They agree, so the pattern has been found.

The search can keep sliding to inspect later windows if more occurrences are needed.

Practical takeaways​

Rabin–Karp’s main idea is simple but powerful:

• A pattern and a same-length text window can be represented by fingerprints.
• Adjacent windows overlap, so their fingerprints can be updated rather than rebuilt.
• For a four-digit decimal window, rolling means removing the outgoing thousands-place contribution, multiplying the remainder by 10, and adding the incoming digit.
• The rolling update takes constant time for one fixed-size shift.
• A modulus keeps fingerprint values controlled but allows different windows to share a fingerprint.
• Equal fingerprints therefore indicate candidates, not guaranteed matches.
• Direct comparison of the original pattern and window confirms or rejects every candidate.

In the concrete example, the scan moves through 1234, 2345, 3456, and then 4567. The rolling hash makes each transition reuse the previous window’s work, while verification preserves correctness when the modulus creates a collision. That combination—efficient rolling updates followed by careful candidate checking—is the defining practical lesson of Rabin–Karp.