Rabin-Karp String Matching

Rabin-Karp finds a pattern by comparing fingerprints of fixed-width text windows. Each time the window slides one position, a rolling hash updates its fingerprint in constant time, so most windows are rejected after one hash comparison. When the fingerprints agree, the algorithm checks the characters before accepting the candidate.

That last check is essential. A hash compresses a whole string into a small number, so different strings can share one fingerprint. Rabin-Karp is exact because it treats hash equality as permission to verify, not as proof of a match.

This lesson uses decimal digits so the rolling arithmetic stays readable. The same method works on ordinary text by mapping each character to a number.

The useful part: rolling the fingerprint

Suppose the pattern has length m, the base is 10, and hashes are kept modulo q. A window such as 31428 is a base-10 number, but the animation stores only its remainder modulo q.

Before the scan, compute the place-value factor

high = 10^(m - 1) mod q.

For each pattern digit and each digit in the first window, seed a hash with

hash = (10 × hash + digit) mod q.

Now consider moving the window one place to the right. If out is the digit leaving the left edge and in is the digit entering on the right, the next fingerprint is

next = (10 × (windowHash - out × high) + in) mod q.

The subtraction removes the outgoing digit's highest place value. Multiplication by 10 shifts the remaining digits left, and adding in fills the empty units place. Only the outgoing digit, incoming digit, and old fingerprint are needed. The other m - 1 digits are not read again.

JavaScript's % operator can return a negative remainder, so the implementation normalizes the result with (raw % q + q) % q. A negative intermediate value is not an error. It is simply another representative of the same modular value.

Rabin-Karp step by step

The default animation searches for pattern 31415 in text 3142831415 with q = 13.

1. The pattern length is 5, so high = 10^4 mod 13 = 3.
2. Seeding the pattern fingerprint one digit at a time gives 7. Seeding the first window, 31428, also gives 7.
3. The two fingerprints agree, so the first window becomes a candidate. Character verification compares 3, 1, and 4 successfully, then finds 2 != 1 at offset 3. This is a hash collision, not a match.
4. Roll the window right once. The outgoing digit is 3 and the incoming digit is 3. The raw calculation is 10 × (7 - 3 × 3) + 3 = -17. Normalizing -17 mod 13 gives 9, the fingerprint for 14283.
5. Continue rolling and comparing fingerprints. Windows with a different hash skip character checks altogether.
6. At shift 5, the window is 31415. Its fingerprint is 7, so the gate opens again. All five characters agree this time, and the algorithm returns 5.

The completed trace uses six hash checks, five rolls, and nine character checks. Four character checks belong to the false candidate at shift 0; five prove the real match at shift 5.

Why the modulus changes the work

Keep the text and pattern fixed, then switch q from 13 to 101. The code and answer do not change, but the false candidate disappears.

With q = 13, both 31428 and 31415 have fingerprint 7. Their numeric difference is exactly 13, so they are equal modulo 13. With q = 101, their fingerprints are 17 and 4. The first window is rejected by the hash, and character verification begins only at the real match.

A larger modulus usually lowers the chance of accidental equality, though it does not remove the possibility. Production implementations often use a much larger modulus, a machine-word hash, or two independent hashes. Exact substring search still needs a final equality check unless the application explicitly accepts a small collision risk.

Correctness

Rabin-Karp relies on two straightforward facts.

First, equal strings produce equal hashes under the same base and modulus. Therefore a window whose hash differs from the pattern hash cannot be the pattern. Rejecting it is safe.

Second, equal hashes do not imply equal strings. The algorithm resolves that ambiguity by comparing the candidate window with the pattern character by character. It reports a match only after every pair agrees.

The rolling recurrence preserves the same polynomial fingerprint that recomputing the whole window would produce. Removing the outgoing highest-order term, shifting the remaining terms, and appending the incoming term gives the polynomial for the next window. Taking the remainder after each operation does not change the final remainder.

Time and space complexity

Let n be the text length and m the pattern length.

The rolling scan itself is linear. The worst case comes from verification: if many windows collide with the pattern hash and each fails late, the algorithm can compare nearly m characters at nearly every shift.

Open the Collision storm preset to see that cost begin to accumulate. Five windows pass the hash gate even though none equals the pattern. A deliberately weak hash, adversarial input, or unlucky modulus can erase the filtering advantage.

When to use Rabin-Karp

For one ordinary substring lookup, a language's built-in search is usually the right choice. Rabin-Karp becomes especially useful when fingerprints can rule out a large amount of repeated work.

• Searching for several patterns of the same length can share one rolling pass over the text. Put the pattern hashes in a set, then verify only windows whose hash is present.
• Finding duplicate chunks or plagiarism candidates uses the same rolling-window idea, often with larger hashes and careful collision handling.
• Two-dimensional matching can roll across rows and then across columns.

KMP offers a deterministic O(n + m) bound for a single pattern and never depends on collision frequency. Rabin-Karp has a simpler fixed-width scan and extends naturally to batches of equal-length patterns. The better choice depends on the job, not on one algorithm being universally faster.

Edge cases

• If the pattern is longer than the text, no legal window exists, so the function returns -1.
• An empty text with a non-empty pattern also returns -1.
• A one-digit pattern works without special rolling logic; high is 1.
• Leading zeros are safe because the window width stays fixed. The strings 0012 and 12 are not compared as if they had the same length.
• A match at the last legal shift must still be checked. The scan includes shift n - m.
• The UI requires a non-empty pattern because libraries disagree about that API convention. The displayed function documents its own convention and returns 0 for an empty pattern.

Common mistakes

• Returning immediately when the hashes agree. The default first window shows the false match this would report.
• Recomputing every window hash from its m characters. That is correct but throws away the rolling hash and can make the scan O(nm) before verification is counted.
• Forgetting the outgoing digit's place-value factor. Subtract out × high, not just out.
• Using the language remainder directly when it may be negative. Normalize before the next roll, or later calculations will use the wrong representative.
• Choosing a tiny modulus in production. Small values are good for watching collisions in a lesson, not for filtering real workloads.
• Calling every hash hit a collision. It is a candidate until verification finishes; it is a collision only when the strings differ.