cf.completefrontend
STRING ALGORITHMS · CORE

Rabin-Karp rolling hash

Compare a window of text with a pattern by comparing one number, and update that number in constant time as the window slides.

Time O(n + m) on averageSpace O(1)4 practice problemsStep-through picture

The idea

Comparing two strings of length m takes up to m steps. If you slide a window of length m over a text and compare at every position, that costs n * m steps. Rabin-Karp, named after Michael Rabin and Richard Karp, makes each comparison cost one step most of the time.

It turns each string into a number called a hash. Think of the characters as digits of a big number in base 256. Equal strings always give equal numbers. If the window's number differs from the pattern's number, the strings differ and you move on. Only when the numbers are equal do you compare the actual letters, to rule out a rare false alarm.

The clever part is the rolling update. When the window slides one step right, you don't recompute its number from scratch. You remove the leftmost character's part, shift everything one place, and add the new character. That is a few multiplications, whatever m is. The numbers are kept small with % mod, the remainder after dividing by a large prime.

An everyday example

Checking a moving odometer

Picture a row of digits 3 1 4 1 5 9 and a 2-digit window you want to compare with 41. The window starts on 31. To slide right, you drop the 3, which was worth 30, leaving 1. Multiply by 10 to shift it, giving 10, and add the new digit 4: 14. Slide again: drop 10, shift, add 1, giving 41. That matches. You never re-read the whole window; you just updated one number.

How the example maps to the code
In the exampleIn the code
The digits in the windowtext.slice(start, start + m)
The number the window showswindowHash
The number you are looking forpatternHash
What the leftmost digit is worthtext.charCodeAt(start) * high
Shifting and adding the new digit(windowHash - dropped) * base + text.charCodeAt(start + m)

From the slow way to rabin-karp rolling hash

  1. The simple search compares the pattern with each window of the text, letter by letter. There are n - m + 1 windows and each can take up to m comparisons, so the cost is O(n · m). Most windows fail after a letter or two, but long near-matches make every window expensive.
  2. Comparing two strings is slow, but comparing two numbers takes one step. So turn each string into a number, a hash, in a way where equal strings always get equal numbers. Then a window whose number differs from the pattern's number can be skipped without reading its letters.
  3. Computing a fresh hash for each window would still read m letters per window. The trick is a hash that can be updated: read the letters as digits of a number in base 256. Sliding the window one step means removing the leftmost letter's value, dropped, shifting the rest by multiplying by base, and adding the new letter. That is a few operations, whatever m is.
  4. These numbers get huge, so keep only the remainder % mod for a large prime mod. Different strings can then share a remainder, so when the hashes are equal, compare the actual letters before recording a match. Slide, update, check: that loop is Rabin-Karp.

How it works

  1. Let m be the pattern's length. Choose base = 256 (one digit per character code) and a large prime mod.
  2. Compute high = base^(m-1) % mod, the worth of the leftmost character in a window.
  3. Compute patternHash and the first windowHash by reading m characters: multiply the hash by base and add the next character code, each time taking % mod.
  4. For each start, if windowHash === patternHash, compare the actual strings to make sure, and record start if they are equal.
  5. Slide the window: subtract dropped = text.charCodeAt(start) * high, multiply by base, add the next character code, and take % mod. Add mod before taking the remainder so the value never goes negative.
  6. Return the list of starts where the pattern was found.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function rabinKarp(text, pattern) {
  2. const m = pattern.length;
  3. const base = 256;
  4. const mod = 1000000007;
  5. if (m === 0 || m > text.length) return [];
  6. let high = 1;
  7. for (let k = 1; k < m; k++) high = (high * base) % mod;
  8. let patternHash = 0;
  9. let windowHash = 0;
  10. for (let k = 0; k < m; k++) {
  11. patternHash = (patternHash * base + pattern.charCodeAt(k)) % mod;
  12. windowHash = (windowHash * base + text.charCodeAt(k)) % mod;
  13. }
  14. const matches = [];
  15. for (let start = 0; start + m <= text.length; start++) {
  16. if (windowHash === patternHash && text.slice(start, start + m) === pattern) {
  17. matches.push(start);
  18. }
  19. if (start + m < text.length) {
  20. const dropped = (text.charCodeAt(start) * high) % mod;
  21. windowHash = ((windowHash - dropped + mod) * base + text.charCodeAt(start + m)) % mod;
  22. }
  23. }
  24. return matches;
  25. }

How fast it is

TimeO(n + m) on average
Extra memoryO(1)

Each slide updates the hash with a few arithmetic steps. The full comparison only runs when hashes are equal, which is rare unless the pattern really appears.

  • Best caseO(n + m)

    No window's hash equals the pattern's: the first hashes cost O(m), and each window then costs O(1).

  • Average caseO(n + m)

    Ordinary text with a few real matches: each match costs O(m) to confirm, and collisions with a large prime mod are very rare.

  • Worst caseO(n · m)

    Almost every window matches, like the pattern aaa in aaaaaaaa, or someone picks text that is built to collide: each window then needs an O(m) letter check.

Common mistakes

  • Trusting equal hashes without comparing the text. Collisions are rare but real, and a wrong match is a silent bug.
  • Subtracting without adding mod back. In JavaScript % keeps the sign, so (-5) % 7 is -5, and the hash goes negative and stops matching.
  • Choosing a base or mod so big that products pass Number.MAX_SAFE_INTEGER. The math quietly rounds and equal strings can get different hashes.
  • Recomputing the hash of each window from scratch. That is just the slow O(n * m) search with extra steps.

When to use it

Look for these clues in a problem:

  • You compare many fixed-length windows of a text with a pattern or with each other.
  • You need to find repeated substrings of a given length, or the longest repeated substring.
  • Several patterns of the same length must be searched at once (put their hashes in a Set).
  • Comparing two substrings quickly, many times, would make the solution fast enough.

Check yourself

Answer each one in your head first, then open it.

Why add mod before taking the remainder in the roll?

windowHash - dropped can be negative, and in JavaScript % keeps the sign. Adding mod first keeps the value between 0 and 2 × mod, so the remainder comes out right.

What is high for a pattern of length 3, with base = 256?

65536, which is 256^2: the worth of the leftmost of 3 letters.

If two windows have different hashes, can they still be the same string?

No. The hash is computed from the letters alone, so equal strings always get equal hashes. Only the other direction can fail.

Why is mod a large prime like 1000000007?

A large modulus spreads hashes over about a billion values, so collisions are rare. A prime avoids shared factors with the base, which would make some letter patterns collide more often.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule at the top of each loop: windowHash is the hash of text.slice(start, start + m), computed by the same formula as patternHash. It's true for start = 0, because both hashes were built by the same loop over m letters.

The roll keeps the rule. In base 256, the window's leftmost letter is worth code × 256^(m-1), which is code × high after % mod. Subtracting it leaves the other m - 1 letters, multiplying by base shifts them one place left, and adding the next code puts the new letter last. Taking % mod at each step gives the same remainder as doing the math on the full numbers, and adding mod before the remainder keeps the value from going negative.

So equal strings always have equal hashes, and a window with a different hash can't be a match: no match is ever missed. A match is recorded only after text.slice(start, start + m) === pattern, so a collision can't cause a wrong answer. The loop visits all n - m + 1 windows and stops.

Going deeper

3 more ideas

Why equal numbers aren't proof

Many different strings share the same remainder after % mod, so two different strings can get the same hash. This is called a collision. With a large prime like 1000000007, a collision is very rare, but it can happen, so the code checks the real letters before reporting a match. Different hashes, on the other hand, always mean different strings.

How fast it is

Building the first hashes takes O(m). Each slide is O(1), so all n - m + 1 windows cost O(n). Each true match costs O(m) to confirm. With few collisions the total is O(n + m); the worst case, when many windows collide, is O(n * m). Memory is O(1) besides the output.

Staying inside safe numbers

JavaScript numbers are exact only up to about 9 * 10^15. With mod = 1000000007 and base = 256, every product in the code stays below that. Using a much bigger mod, or a much bigger base, can silently lose precision; switch to BigInt or use two smaller hashes together if you need more safety.

Work it by hand

Every step in a table, with why

Find pip in a 7-letter text. It appears twice, and one window's hash is very close to the pattern's but not equal.

text = "pipapip", pattern = "pip"

StepstartWindowwindowHashEqual to patternHash?What happensWhy
1-pip7367024-high = 65536, patternHash = 7367024p is 112 and i is 105, so pip is 112 × 65536 + 105 × 256 + 112 = 7367024. That is smaller than mod, so % mod changes nothing for these short windows.
20pip7367024yesletters match: record 0The hashes are equal, and text.slice(0, 3) is pip. Then roll: drop 112 × 65536 = 7340032, multiply by 256, and add a (97), giving 6910049.
31ipa6910049noskip, then rollDifferent hashes, so the letters are never compared. Drop 105 × 65536 = 6881280 and add p: 7364976.
42pap7364976noskip, then rollClose to 7367024, but not equal, so the window must differ. Drop 7340032 and add i: 6385769.
53api6385769noskip, then rollDrop 97 × 65536 = 6356992 and add p: 7367024.
64pip7367024yesletters match: record 4Equal again, and the letters match. start + m is 7, the text's length, so there's no next letter to roll in, and the loop ends.

It returns [0, 4]. Only the 2 windows with equal hashes had their letters compared; the other 3 were rejected by one number comparison each.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Rabin-Karp rolling hashO(n + m)O(1)Many patterns of one length, or fast checks of whether two pieces of text are equal.
KMP pattern searchO(n + m)O(m)One pattern, with linear time guaranteed and no chance of slow collisions.
Z-algorithmO(n + m)O(n + m)One pattern, linear time guaranteed, and you'd rather not deal with hashing at all.
Simple searchO(n · m)O(1)Short patterns in ordinary text, where indexOf is the practical choice.

Extra memory: O(1) besides the output: a few numbers. Each check's text.slice makes a short m-letter string that is freed right away.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Rabin-Karp rolling hash and the other approaches, on a scale where each line up is 10 times more steps.
  • Rabin-Karp rolling hash, KMP pattern search, Z-algorithm O(n + m)
  • Simple search O(n · m)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Rabin-Karp rolling hash202,0002 million
KMP pattern search202,0002 million
Z-algorithm202,0002 million
Simple search1001 million1 trillion

Inputs that need care

6 tricky inputs
An empty pattern: pattern = ""
m === 0, so it returns [] on the first check.
A pattern longer than the text: rabinKarp("ab", "abc")
m > text.length, so it returns [] before building any hash.
A pattern equal to the whole text
There is one window. Its hash and letters match, and start + m < text.length is false, so it returns [0] without rolling.
Every window matches: rabinKarp("aaaa", "aa")
All 3 windows are confirmed letter by letter, so it returns [0, 1, 2], spending O(m) on each.
Letters with codes above 255, like € (8364)
charCodeAt returns at most 65535, so code × high stays below about 6.6 × 10^13, under Number.MAX_SAFE_INTEGER. Equal strings still get equal hashes, so rabinKarp("x€€y", "€y") correctly returns [2].
A tiny mod, like 101
Hashes fall into only 101 values, so unrelated windows often collide. The answers stay correct because of the letter check, but the search slows toward O(n · m).

Variations and follow-ups

Twists interviewers add

Many patterns of one length

Put every pattern's hash in a Set, roll one window over the text, and look up each windowHash. One pass finds all of them, in O(n) on average after hashing the patterns.

Two hashes at once

Keep two hashes with different mod values, and treat windows as equal only when both match. A false match then needs two collisions at once, which is so unlikely that some code skips the letter check.

Hashes of any piece

Store prefix[k], the hash of the first k letters, and the powers of base. The hash of any piece text.slice(a, b) is then prefix[b] - prefix[a] × base^(b - a), taken % mod, in O(1). With binary search, this finds the longest repeated piece of a text.

Rolling hashes for files

File sync tools split files into chunks using a hash over a sliding window of bytes, updated one byte at a time. A chunk ends wherever the hash meets a rule, so an edit in one place only changes nearby chunks.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "find a repeated substring of length k", "longest duplicate substring", or "search for many patterns of one length". Hashing windows turns string comparisons into number comparisons.
  • Explain the roll with base 10 first: in 52734, the window 52 becomes 27 by dropping 5 × 10, multiplying by 10, and adding 7. Then say the real code does the same with base 256 and % mod.
  • Always say why you compare letters when hashes match: collisions are rare but possible. Interviewers check that you know equal hashes aren't proof.
  • Test by hand: overlapping matches, a pattern as long as the text, and the subtraction that could go negative. The usual follow-up is "what's the worst case?": O(n · m) when many windows match or collide, which KMP avoids.

Where frontend code uses it

The same idea in real UI code
  • rsync uses a rolling checksum, updated as a window slides one byte at a time, to find the blocks of a file that the other side already has, so only the changes are sent.
  • Bundlers and build caches name files by a hash of their content, such as main.3f9a2c.js, so the browser can cache them forever. That is hashing whole files rather than rolling windows, but it is the same idea: compare short numbers instead of long text.
  • Finding duplicated code blocks of a fixed length across a code base, as copy-paste detectors do, hashes every window of k lines or tokens and looks for equal hashes.

Related algorithms