What this module covers: Finding a pattern inside a larger text — the job behind every grep, every log search, every "find in file" — has a naive solution that's O(n × m), the same quadratic shape flagged throughout this course. This module covers two different fixes: Rabin-Karp, which compares hashes instead of characters using a rolling hash (Module F-9's sliding window, made multiplicative), and KMP, which never backtracks in the text at all, by precomputing exactly how much progress can be reused after a mismatch.
The Naive Approach's Cost
typescript
For every one of the roughly n starting positions in text, this potentially compares up to m characters (the pattern's length) before finding a mismatch — O(n × m) in the worst case (imagine searching for "aaaaab" inside "aaaaaaaaaaaaaaaa" — nearly every position gets a long, failed near-match before giving up). Both fixes below avoid this by never blindly re-comparing characters that a smarter approach could have ruled out or skipped.
Rabin-Karp: Compare Hashes, Not Characters
The idea: compute a hash of the pattern once, then compute a hash of every same-length window in the text — if two hashes don't match, the strings definitely don't match, skipping a full character-by-character comparison entirely. The trick that makes this fast is a rolling hash: updating the previous window's hash to the next window's hash in O(1), rather than recomputing it from scratch.
typescript
The rolling update is exactly Module F-9's sliding window idea (subtract what's leaving, add what's entering, avoid recomputing from scratch), just multiplicative instead of additive: treating the window as a base-256 number, removing the leftmost character's contribution, shifting everything up one digit, and adding the new rightmost character. This keeps each window's hash update O(1), so the whole scan is O(n) for hashing plus O(m) for the initial pattern hash — O(n + m) on average. The hash comparison is a screening step, not a guarantee — two different strings can occasionally hash to the same value (a collision), which is exactly why the code still does a direct text.slice(i, i + m) === pattern comparison before confirming a match; with enough collisions (a poorly chosen hash, or an adversarial input), this degrades back toward O(n × m) in the worst case, but is O(n + m) in the typical case.
KMP: Never Backtrack in the Text
Knuth-Morris-Pratt takes a different approach entirely: precompute, for every prefix of the pattern, how much of a match can be reused after a mismatch, so the text pointer never has to move backward — only the pattern pointer resets, using information already known from the pattern itself.
The precomputed table (the failure function, or LPS array — Longest Proper Prefix that's also a Suffix) answers, for each position in the pattern: if a mismatch happens here, how far back in the pattern can I safely resume, without re-checking characters I already know matched?
typescript
The entire point of lps: when a mismatch happens after partially matching j characters of the pattern, those j characters are already known — re-scanning them from scratch in the text (as the naive approach implicitly does, by moving the starting position forward by one and starting the comparison over from the beginning of the pattern) is wasted work. lps[j - 1] says exactly how much of that already-matched prefix is also a valid suffix of what was just matched, meaning the pattern can resume from that point without needing to re-examine any character in the text a second time. Because i (the text pointer) genuinely never moves backward, KMP guarantees O(n + m) in the worst case — a stronger guarantee than Rabin-Karp's average-case-only bound, at the cost of the more involved LPS precomputation.
Where This Shows Up in Your Stack
grep and text search tools need exactly this problem solved efficiently at scale — searching for a literal string (or, with more machinery, a regex pattern) across potentially huge files, where an O(n × m) naive scan would be unacceptably slow on large inputs.
Malware and antivirus signature scanning matches known malicious byte sequences against files being scanned — a direct string (byte-sequence) matching problem at a scale and frequency where the naive approach's worst case is a genuine liability.
DNA sequence matching (finding a specific genetic subsequence within a much longer genome) is string matching at a very literal level, over a four-character alphabet, at a scale where efficient algorithms matter enormously.
Plagiarism detection tools commonly use rolling hashes (Rabin-Karp's core mechanism, sometimes generalized to hash multi-word chunks rather than raw characters) to quickly find overlapping passages between documents, screening with cheap hash comparisons before ever doing an expensive direct text comparison.
Summary
The naive approach compares up to m characters at each of n positions, O(n × m) in the worst case — the same quadratic shape flagged throughout this course.
Rabin-Karp compares hashes first, using an O(1) rolling update (Module F-9's sliding window, made multiplicative) to avoid recomputing each window's hash from scratch — O(n + m) on average, with a direct string comparison still required to rule out hash collisions.
KMP precomputes a failure function (LPS array) that says exactly how much of a partial match can be reused after a mismatch, letting the text pointer advance monotonically and never backtrack — a guaranteed O(n + m) worst case.
Both fixes share the same underlying instinct as the rest of this course: don't redo work you've already effectively done — Rabin-Karp screens with cheap hashes instead of full comparisons, KMP reuses information already extracted from the pattern instead of re-scanning matched text.
This is the literal mechanism behind grep, malware signature scanning, DNA sequence search, and plagiarism detection at production scale.
The next module, P vs NP: Recognizing Intractable Problems, is a conceptual shift from "here's a faster algorithm" to "here's how to recognize when no fast algorithm can exist at all" — and what to do about it in production anyway.
Knowledge Check
In rabinKarp, why is the direct string comparison text.slice(i, i + m) === pattern still necessary after patternHash === windowHash is found to be true?
In kmpSearch, why does a mismatch cause j (the pattern pointer) to fall back to lps[j - 1], rather than restarting the comparison from j = 0 — and why does i (the text pointer) never move backward at all?
According to the module, what is the key difference between Rabin-Karp's and KMP's worst-case time complexity guarantees, and why does that difference exist?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
functionrabinKarp(text:string, pattern:string):number[]{const n = text.length, m = pattern.length;const matches:number[]=[];if(m > n)return matches;constBASE=256,MOD=1_000_000_007;let patternHash =0, windowHash =0, highOrder =1;// highOrder = BASE^(m-1) mod MODfor(let i =0; i < m -1; i++) highOrder =(highOrder *BASE)%MOD;for(let i =0; i < m; i++){ patternHash =(patternHash *BASE+ pattern.charCodeAt(i))%MOD; windowHash =(windowHash *BASE+ text.charCodeAt(i))%MOD;}for(let i =0; i <= n - m; i++){if(patternHash === windowHash){// Hashes matching doesn't guarantee equality (a collision is possible) — verify with a direct comparisonif(text.slice(i, i + m)=== pattern) matches.push(i);}if(i < n - m){// Roll the window forward: drop the leaving character's contribution, add the new one — O(1) windowHash =(((windowHash - text.charCodeAt(i)* highOrder)*BASE)+ text.charCodeAt(i + m))%MOD;if(windowHash <0) windowHash +=MOD;// JavaScript's % can return negative — correct it back into range}}return matches;}
functionbuildLPS(pattern:string):number[]{const lps =newArray(pattern.length).fill(0);let length =0;// length of the current longest matching prefix-suffixlet i =1;while(i < pattern.length){if(pattern[i]=== pattern[length]){ length++; lps[i]= length; i++;}elseif(length >0){ length = lps[length -1];// fall back to the next-best-known prefix-suffix length, don't reset to 0 outright}else{ lps[i]=0; i++;}}return lps;}functionkmpSearch(text:string, pattern:string):number[]{const lps =buildLPS(pattern);const matches:number[]=[];let i =0, j =0;// i walks the text, j walks the pattern — i NEVER moves backwardwhile(i < text.length){if(text[i]=== pattern[j]){ i++; j++;if(j === pattern.length){ matches.push(i - j);// full match found j = lps[j -1];// look for the NEXT match, reusing whatever partial match already applies}}elseif(j >0){ j = lps[j -1];// mismatch — fall back using the precomputed table, i still doesn't move}else{ i++;// no partial match to fall back on — just move forward in the text}}return matches;}