01 / The idea
Most windows should not need exact work.
Rabin–Karp uses a rolling hash to pick out the windows that might equal one exact pattern, then compares only those symbol by symbol. The hash is a small number that summarizes a window. If it differs from the line’s number, the window can’t be a copy. If it agrees, the window might be, so the search reads it.
Rebuilding a hash for every window would repeat most of the work, because neighboring windows share all but one symbol. The rolling step removes the outgoing symbol’s contribution, shifts what is left, and adds the incoming symbol. One update replaces 30 fresh hash steps.
In the guest post, the spring line is copied at scalar range 97–127. The end is
exclusive, so the copy covers positions 97 through 126. Two of the 127 windows share the
line’s hash, and only one of them is the copy.
02 / Name the rule
Remove, shift, add.
H′ = ((H − out · bm−1) · b + in) mod p
Here b is a base (911 in this lesson), p is a modulus (1,000,003),
and the window has m symbols. The outgoing symbol had the highest place, so
subtract its contribution first. Multiplying by b shifts every remaining symbol one
place left. Adding the incoming symbol completes the next window.
This lesson maps each Unicode scalar to its code point plus one before hashing. That is a teaching choice, not advice about how production systems should normalize text. Matching is exact and case-sensitive.
Fingerprint a window
Compare one small number before touching every symbol in the window.
Reuse the old work
Remove the outgoing contribution, shift, and add one incoming symbol.
Trust no hash alone
Exact comparison turns a collision into extra work, never a false hit.
Why does a collision not break correctness?The hash is only a filter
The search reports a hit only after the window equals the line symbol by symbol. A collision makes a different window pay for verification, so it costs time. It can’t put a different window in the hit list. A stronger or second hash can cut the number of collisions, but the final equality check stays.
03 / Follow one operation
Let the hash reject windows, then read the survivors.
The animation replays the real search. First the rolling hash rejects windows without
reading them. Then it stops at offset 34, where the tide rolls by the old wall hashes to 609557, the same number as the spring line.
Verification reads 9 matching symbols, fails at the tenth, and moves on. The last chapter ends
on the one verified copy.
Let the hash choose which windows deserve exact work.
The hash differs, so this window needs no character comparisons.
confirmed copy current window verification mismatch
Hash each window
Hash the spring line “the tide turns at the old pier” (609557), then slide a 30-symbol window across the guest post. Each step removes the outgoing symbol, shifts, and adds the incoming one instead of rehashing all 30.
Reduced motion: choose a scene to see its completed state.
Read this scene
Hash the spring line “the tide turns at the old pier” (609557), then slide a 30-symbol window across the guest post. Each step removes the outgoing symbol, shifts, and adds the incoming one instead of rehashing all 30.
Windows shown: 1 of 127. At offset 0, the rolling hash rejected this window without exact comparisons.
Watch and Step through replay the same rolling-window evidence. Try it runs the TypeScript search on edited text and pattern inputs.
04 / Read the shape
The hash filters; equality decides.
Basic form validates the line and prepares its hash. In the wild rolls through every same-length window and verifies equal-hash candidates. At the call site compiles the spring line once, scans the guest post, and prints each candidate as a hit or a collision. Both languages print the same two lines.
Validate one line, hash it, and prepare the high-place power for the outgoing symbol. The compiled pattern is reusable across documents.
export const MAX_PATTERN_SCALARS = 32;
export const MAX_TEXT_SCALARS = 512;
export const HASH_BASE = 911;
export const HASH_MODULUS = 1_000_003;
export type Hit = { start: number; end: number };
export type WindowScan = {
offset: number;
hash: number;
hashMatches: boolean;
comparisons: number[];
verificationMismatchIndex: number | null;
hit: boolean;
};
export type CompiledPattern = {
pattern: string;
symbols: string[];
patternHash: number;
highPower: number;
};
export type SearchResult = {
pattern: string;
text: string;
hits: Hit[];
windows: WindowScan[];
};
export type SearchErrorCode = 'empty-pattern' | 'long-pattern' | 'long-text' | 'malformed-text';
export class SearchError extends Error {
readonly code: SearchErrorCode;
constructor(code: SearchErrorCode, message: string) {
super(message);
this.name = 'SearchError';
this.code = code;
}
}
function scalars(value: string, limit: number, code: SearchErrorCode, label: string): string[] {
const symbols = Array.from(value);
for (const symbol of symbols) {
const point = symbol.codePointAt(0)!;
if (point >= 0xd800 && point <= 0xdfff)
throw new SearchError('malformed-text', `${label} must be well-formed Unicode.`);
}
if (symbols.length > limit)
throw new SearchError(code, `${label} is limited to ${limit} Unicode scalar values.`);
return symbols;
}
function symbolValue(symbol: string): number {
return symbol.codePointAt(0)! + 1;
}
function addSymbol(hash: number, symbol: string): number {
return (hash * HASH_BASE + symbolValue(symbol)) % HASH_MODULUS;
}
function subtractSymbol(hash: number, symbol: string, highPower: number): number {
return (hash - ((symbolValue(symbol) * highPower) % HASH_MODULUS) + HASH_MODULUS) % HASH_MODULUS;
}
function hashSymbols(symbols: string[]): number {
let hash = 0;
for (const symbol of symbols) hash = addSymbol(hash, symbol);
return hash;
}
function power(base: number, exponent: number): number {
let result = 1;
let factor = base;
let remaining = exponent;
while (remaining > 0) {
if (remaining % 2 === 1) result = (result * factor) % HASH_MODULUS;
factor = (factor * factor) % HASH_MODULUS;
remaining = Math.floor(remaining / 2);
}
return result;
}
export function compile(pattern: string): CompiledPattern {
const symbols = scalars(pattern, MAX_PATTERN_SCALARS, 'long-pattern', 'The pattern');
if (symbols.length === 0) throw new SearchError('empty-pattern', 'The pattern cannot be empty.');
return {
pattern,
symbols,
patternHash: hashSymbols(symbols),
highPower: power(HASH_BASE, symbols.length - 1)
};
}// Rabin–Karp substring search with a rolling hash and exact verification.
const (
MaxPatternScalars = 32
MaxTextScalars = 512
HashBase int64 = 911
HashModulus int64 = 1000003
)
type Hit struct {
Start int
End int
}
type WindowScan struct {
Offset int
Hash int64
HashMatches bool
Comparisons []int
VerificationMismatchIndex int
Hit bool
}
type CompiledPattern struct {
Pattern string
Symbols []rune
PatternHash int64
HighPower int64
}
type SearchResult struct {
Pattern string
Text string
Hits []Hit
Windows []WindowScan
}
type SearchError struct {
Code string
Message string
}
func (e *SearchError) Error() string { return e.Message }
func symbols(value string, limit int, code string, label string) ([]rune, error) {
if !utf8.ValidString(value) {
return nil, &SearchError{Code: "malformed-text", Message: fmt.Sprintf("%s must be well-formed UTF-8", label)}
}
result := []rune(value)
if len(result) > limit {
return nil, &SearchError{Code: code, Message: fmt.Sprintf("%s is limited to %d Unicode scalar values", label, limit)}
}
return result, nil
}
func symbolValue(symbol rune) int64 { return int64(symbol) + 1 }
func addSymbol(hash int64, symbol rune) int64 {
return (hash*HashBase + symbolValue(symbol)) % HashModulus
}
func subtractSymbol(hash int64, symbol rune, highPower int64) int64 {
value := (symbolValue(symbol) * highPower) % HashModulus
return (hash - value + HashModulus) % HashModulus
}
func hashSymbols(symbols []rune) int64 {
var hash int64
for _, symbol := range symbols {
hash = addSymbol(hash, symbol)
}
return hash
}
func power(base int64, exponent int) int64 {
result := int64(1)
factor := base
for exponent > 0 {
if exponent%2 == 1 {
result = (result * factor) % HashModulus
}
factor = (factor * factor) % HashModulus
exponent /= 2
}
return result
}
func Compile(pattern string) (CompiledPattern, error) {
patternSymbols, err := symbols(pattern, MaxPatternScalars, "long-pattern", "The pattern")
if err != nil {
return CompiledPattern{}, err
}
if len(patternSymbols) == 0 {
return CompiledPattern{}, &SearchError{Code: "empty-pattern", Message: "The pattern cannot be empty"}
}
return CompiledPattern{
Pattern: pattern,
Symbols: patternSymbols,
PatternHash: hashSymbols(patternSymbols),
HighPower: power(HashBase, len(patternSymbols)-1),
}, nil
}Reading the TypeScriptNumbers are a filter
The compiled pattern keeps one modular hash and the high-place power. Each window records whether its hash matched, which exact comparisons ran, and where a candidate failed. A window is a hit only when its hash matched and verification found no mismatch. The numbers stay below 253, so plain JavaScript numbers are exact.
Reading the GoSame recurrence, int64 arithmetic
Go ranges over validated UTF-8 into runes and uses the same modular arithmetic in int64. The native tests pin the guest post’s hit, the collision at offset
34, overlaps, and invalid input.
What is refusedKeep offsets unambiguous
Both versions accept a non-empty pattern of at most 32 Unicode scalars and a document of at most 512 scalars. Empty patterns, overlong input, malformed Unicode, and invalid UTF-8 in Go are rejected. Normalization, locale matching, and security hashing are outside the contract.
05 / Try a decision
Same number, different words.
This is the moment the whole algorithm depends on. Decide what the search does before you trust a hash.
Then open Try it above and load Hash collision. It
searches At dawn the tide rolls by the old wall. on its own: 10 windows, one
hash candidate at offset 8, and no hits. No copy searches the post for a line
it doesn’t contain, and all 131 windows are rejected by the hash without a single symbol comparison.
06 / Follow the cost
Spend one update to avoid rebuilding every window.
| Operation | Time | Extra space | What it assumes |
|---|---|---|---|
| Compile the pattern | O(m) | O(m) | Hash the pattern and compute the high-place power used to remove the outgoing symbol. |
| Build the first window | O(m) | O(m) | Hash the first m document symbols before the rolling scan begins. The shown code slices them into a new array first. |
| Expected scan | O(n + m) | O(n) as shown | With a well-behaved hash, most windows stop at the hash comparison and only candidates verify. |
| Classic worst case | O(n · m) | O(n) as shown | Many collisions or a repeated candidate-heavy text can force exact work at many windows. |
| Report z matches | O(scan + z) | O(n + z) as shown | Advance by one symbol so overlapping matches are retained in half-open scalar ranges. The shown search also keeps the document as a scalar array and one trace entry per window. |
Let n be the document length and m the pattern length, both
measured in Unicode scalars. The rolling update is constant time, so the expected scan is
close to linear when the hash spreads windows well. Exact verification adds work only for
candidates. The scan rows say O(n) space because the shown search keeps the document
as a scalar array and records every window for the animation; a scan without that trace needs
only the pattern and one rolling hash.
On the guest post (156 scalars, a 30-symbol line), the search makes 127 hash comparisons and 40 exact symbol comparisons: 10 for the collision and 30 for the copy. A naive search that stops at each first mismatch makes 188. That is a small saving on a short post. The gap grows when many windows start the way the line does, because the naive search reads further into each one before it fails, while a hash comparison costs the same every time.
The classic worst case is still O(n · m): every window can become a candidate
that needs up to m comparisons. A single modular hash is a teaching choice, not a
defense against someone who picks inputs to collide on purpose.
07 / Give it a real job
Go’s strings.Index reaches for it on long patterns.
Go’s standard library calls Rabin–Karp from strings.Index. For a substring
longer than the fast brute-force limit (32 bytes on arm64; 31 or 63 on amd64, depending on
the CPU), Index first scans for the pattern’s first byte. When that keeps
producing false starts, it hands the rest of the string to bytealg.IndexRabinKarp. Its hash is a uint32 that wraps instead of using a modulus, and it still compares
the window with the pattern before it returns, the same filter-then-verify contract as this lesson.
A copy checker for the newsletter owns the same job at a larger size: compile each line it cares about once, scan every submission, and hand back verified hit ranges. What it leaves out is paraphrase. A post that rewords the line has no exact window to find, and that is a different question with a different tool.
This runs where the text is scanned, on a server or in a command-line tool. In a browser, includes and indexOf are the engine’s job, so nothing in a component
needs its own rolling hash.
08 / Make the call
Choose the filter, the number of patterns, and the guarantee.
Reach for Rabin–Karp when a same-length fingerprint is the natural question: one exact line or token in a stream of text, with every candidate verified. For one pattern in long text where skipping ahead pays off, Boyer–Moore compares from the right and jumps over windows that can’t match. For a fixed list of many patterns in one pass, use Aho–Corasick.
For a short or one-off search, indexOf or the standard-library search is
clearer and already tuned. If the question is whether a post reworded the line, a hash of
exact windows can’t help: MinHash compares overlapping word
sets, and Levenshtein distance counts
the edits between two short strings.
09 / Take the idea with you
Explain a copy check without saying “Rabin–Karp.”
“Turn the line into a number. Slide a window of the same length along the text and keep a running number for it: take out the symbol that leaves, put in the one that arrives. Only where the two numbers agree do you read the symbols, because different text can land on the same number.”
Before moving on, load the lab’s Hash collision preset, change one letter
of wall, and predict whether that window is still a candidate before you
search.
Connections to follow nextRelated lessons
- Sliding window is the same move without the hash: keep a running answer as one item leaves and one arrives.
- Boyer–Moore substring search finds one exact pattern by skipping windows instead of hashing them.
- MinHash and LSH hashes word shingles to find near copies, where exact windows miss.