String Searching: Naive, KMP, Rabin-Karp and Z

Lesson 6 ended with a problem that has no known fast exact answer. This one is the opposite. "Does the word needle appear in this text?" has several fast, exact algorithms, and interviewers like it because each one teaches a different idea: reuse what you already matched (KMP), compare small numbers instead of strings (Rabin-Karp), and precompute how a string matches itself (Z).

You should know loops and strings first: DSA Lesson 9, Strings, DSA Lesson 30, String Patterns and DSA Lesson 31, Substrings and Windows (the sliding window is a close cousin of the rolling hash below). Big-O is in DSA Lesson 12. The trie, which is the base for multi-pattern search, is in DSA Lesson 58, and string dynamic programming (edit distance and friends, a different kind of "matching") is in DSA Lesson 57.

Words used in this lesson

• Text is the long string we search in. Pattern is the short string we look for. I write n for the text length and m for the pattern length.
• Match means the pattern appears in the text starting at some position (an index, counting from 0).
• Prefix of a string is its first few characters (ab is a prefix of abc). Suffix is its last few characters (bc).
• Border of a string is a piece that is both a prefix and a suffix, and is shorter than the whole string. aba has the border a. ababa has the borders a and aba.
• Failure function (also called the prefix function or LPS table) is a list that says, for each position of the pattern, the length of the longest border of the pattern up to that position. KMP uses it.
• Hash is a small number computed from a string. Equal strings always have equal hashes. Different strings can have the same hash, which is called a collision.
• Rolling hash is a hash of a window that you update in constant time when the window moves one step.
• False positive means the hashes are equal but the strings are not.
• Z-array is a list where z[i] is the length of the longest piece starting at i that is also a prefix of the whole string.
• Automaton here means a machine with states and arrows labelled by characters. Aho-Corasick is one.

The naive method and its worst case

Put the pattern at position 0 of the text and compare character by character. On a mismatch, slide the pattern one step to the right and start again.

function naive(t, p) {  const n = t.length, m = p.length;  if (m === 0) return 0;  for (let i = 0; i + m <= n; i++) {    let j = 0;    while (j < m && t[i + j] === p[j]) j++;    if (j === m) return i;  }  return -1;}

There are up to n - m + 1 start positions and each can compare up to m characters, so the worst case is about n x m comparisons. On typical text it is fast, because most start positions fail on the first character. The bad input is text and pattern made of almost the same letter:

text = "aaaa...a" (n letters)   pattern = "aaa...ab" (m letters, m about n/2)

At every start position the naive method compares m - 1 letters that match, then fails on the last b. Then it throws that work away and starts again one step later. I counted the character comparisons for the naive search and for KMP (below):

n 1000 m 500 naive compares 250500 kmp compares 1501n 10000 m 5000 naive compares 25005000 kmp compares 15001n 100000 m 50000 naive compares 2500050000 kmp compares 150001

Ten times more text gives a hundred times more naive work (that is n x m, which is quadratic when m is half of n). KMP stays at about 1.5 n. The idea of KMP is the answer to the question "why throw the work away?".

KMP: never move backwards in the text

When the pattern ababaca has matched ababa and then fails, we do not know only that there is a mismatch. We know the last five text characters are ababa. The longest piece of that which is also a prefix of the pattern is aba (a border of ababa). So we can continue as if we had just matched aba, without looking at the text again.

KMP precomputes that answer for every length. The failure function f[i] is the length of the longest border of pattern[0..i]:

function failure(p) {  const f = new Array(p.length).fill(0);  let k = 0;                              // length of the current border  for (let i = 1; i < p.length; i++) {    while (k > 0 && p[i] !== p[k]) k = f[k - 1];   // fall back to a shorter border    if (p[i] === p[k]) k++;    f[i] = k;  }  return f;}console.log(failure("ababaca").join(" "));console.log(failure("aabaaab").join(" "));

0 0 1 2 3 0 10 1 0 1 2 2 3

Read the first line by hand to be sure you see it:

The search runs the same idea over the text. k is "how many pattern characters are matched right now". On a mismatch we do not move back in the text; we only reduce k to f[k - 1]:

function kmp(t, p) {  const m = p.length;  if (m === 0) return 0;  const f = failure(p);  let k = 0;  for (let i = 0; i < t.length; i++) {    while (k > 0 && t[i] !== p[k]) k = f[k - 1];    if (t[i] === p[k]) k++;    if (k === m) return i - m + 1;        // match ends at i  }  return -1;}

Here is a trace for text abababaca and pattern ababaca. I added a print line to the loop above:

i=0 t[i]=a k=0 => k=1i=1 t[i]=b k=1 => k=2i=2 t[i]=a k=2 => k=3i=3 t[i]=b k=3 => k=4i=4 t[i]=a k=4 => k=5i=5 t[i]=b k=5 -> fall to 3 => k=4i=6 t[i]=a k=4 => k=5i=7 t[i]=c k=5 => k=6i=8 t[i]=a k=6 => k=7match starts at 2indexOf 2

The key line is i=5. We had matched ababa (k = 5) and the text has b, but the pattern wants c. The naive method would go back to text position 1. KMP looks up f[4] = 3, keeps the last three matched characters aba, and sees that b matches the next pattern character b, so k becomes 4. The text index i only ever went forward. The answer, 2, equals indexOf.

Why it is linear. Each step either raises k by one or lowers it. k can go up only once per text character, so in total it can come down at most n times. The inner while loop therefore runs at most n times over the whole search. The failure function has the same argument, so building it is O(m). Total: O(n + m), and extra memory O(m).

Rabin-Karp: compare numbers instead of strings

Idea: compute a hash of the pattern. Slide a window of length m along the text, keep a hash of the window, and only when the two hashes are equal, compare the actual characters.

The trick that makes it fast is the rolling hash. Treat a string as a number in some base (here 257, bigger than any character code), then take the remainder after dividing by a modulus (a big prime, to keep the number small):

hash("abc") = ((97 * B + 98) * B + 99) mod M      (B = base, M = modulus)

When the window moves one step, remove the old first character and add a new last one. In constant time:

new = ((old - first * B^(m-1)) * B + next) mod M

function rk(t, p, mod = 1000003, base = 257, stats) {  const n = t.length, m = p.length;  if (m === 0) return 0;  if (m > n) return -1;  let hp = 0, ht = 0, pow = 1;                      // pow = base^(m-1) mod mod  for (let i = 0; i < m; i++) {    hp = (hp * base + p.charCodeAt(i)) % mod;    ht = (ht * base + t.charCodeAt(i)) % mod;    if (i > 0) pow = (pow * base) % mod;  }  for (let i = 0; ; i++) {    if (hp === ht) {                                // hashes agree: verify for real      if (stats) stats.checks++;      if (t.startsWith(p, i)) return i;      if (stats) stats.falsePositives++;    }    if (i + m >= n) return -1;    ht = ((ht - t.charCodeAt(i) * pow % mod + mod) * base + t.charCodeAt(i + m)) % mod;  }}

(The + mod keeps the number from going negative, because JavaScript's % can return a negative value. With mod near a million and base 257, every product stays well inside the exact-integer range of a JavaScript number.)

Collisions, shown on purpose

Equal strings always give equal hashes, but the reverse can fail. With a small modulus it is easy to find two different strings with the same hash. I searched all two-letter pairs with modulus 101 and base 257:

collision mod 101 base 257 [ 'aa', 'ht', 79 ]

So aa and ht have the same hash, 79. Search for ht in xxaayyzz with modulus 101:

-1 { checks: 1, falsePositives: 1 }

The hash matched once (at aa), the character check said no, and the answer -1 is still correct. This is why the verification step is not optional: the hash only filters. With it, the result is always right and the hash only affects speed. How often does the filter let a wrong window through? I searched a 6-letter pattern in 200,000 random lowercase letters:

random text 200000, mod 101 false positives 2225random text 200000, mod 1009 false positives 266random text 200000, mod 1000003 false positives 0

With a tiny modulus about 1 window in 90 was a false alarm; with a modulus near a million, none appeared. (Rough rule: with a modulus M, a random wrong window passes about 1 time in M. This matches the numbers: 200,000 / 101 is about 1,980 and I saw 2,225.) False positives cost m extra comparisons each, so the average time is O(n + m) with a large modulus. The worst case, with many collisions, goes back to O(n x m). Attackers can target a fixed, known hash with chosen inputs, so in code that handles untrusted input use a random base or modulus.

Where Rabin-Karp is the better tool

• Many patterns of the same length. Put all pattern hashes in a Set, slide one window over the text, and check each window hash against the set. One pass for all patterns.
• Plagiarism and duplicate detection, comparing many chunks of text.
• Problems where you compare a window with many things, for example "find a repeated substring of length k" (hash every window of length k; a repeated hash means a probable repeat, then verify). Binary search on k with this idea solves "longest repeated substring" and "longest duplicate substring" problems in near-linear time per length.
• A 2-D version (hash a block of a grid) exists as well.

The Z-array: how a string matches itself

z[i] is the length of the longest piece that starts at i and is also a prefix of the string. By convention z[0] is the whole length.

function zArray(s) {  const n = s.length, z = new Array(n).fill(0);  z[0] = n;  let l = 0, r = 0;                       // [l, r) is the right-most match window found so far  for (let i = 1; i < n; i++) {    if (i < r) z[i] = Math.min(r - i, z[i - l]);   // reuse an earlier answer    while (i + z[i] < n && s[z[i]] === s[i + z[i]]) z[i]++;    if (i + z[i] > r) { l = i; r = i + z[i]; }  }  return z;}console.log(zArray("aabxaab").join(" "));console.log(zArray("aaaaa").join(" "));

7 1 0 0 3 1 05 4 3 2 1

Check the first line: at index 4 the string continues aab, which equals the prefix aab, so z[4] = 3. At index 1 it continues abxaab; only a matches the prefix aab..., so z[1] = 1.

How it stays linear: the window [l, r) is a piece of text already known to equal a prefix. If i is inside it, the answer for i is related to the answer at i - l, so we start from a known lower bound and only extend by comparing new characters. r never moves left, so the total number of new comparisons is at most n.

Pattern search with Z. Join pattern + separator + text, where the separator is a character that appears in neither. Any position with z[i] = m is a match, and the separator stops a match from running over the border:

function zSearch(t, p) {  const m = p.length;  if (m === 0) return 0;  const z = zArray(p + "\u0000" + t);  for (let i = m + 1; i < z.length; i++) if (z[i] === m) return i - m - 1;  return -1;}

The Z-array and the KMP failure function carry the same information about a string and can be converted into each other. Pick the one you can write from memory without a bug. Z is often easier to explain; KMP uses less extra memory for a streaming text because it needs only the pattern's table and not a joined string.

Other uses of the Z-array: count how many times each prefix appears, find the smallest period of a string (the shortest p where the string is p repeated), and check if one string is a rotation of another (although for that one, (s + s).includes(t) is the short answer; see DSA Lesson 30).

Tested against the built-in

Writing a string algorithm without a test is asking for an off-by-one. The built-in indexOf is the oracle. I generated 20,000 random cases: an alphabet of 1 to 3 letters (small alphabets create many partial matches, which is where bugs show), a text of 0 to 29 letters and a pattern of 0 to 5 letters, including the empty pattern and a pattern longer than the text. All five searches had to return exactly what indexOf returns:

cases 20000 disagreements {"naive":0,"kmp":0,"rk":0,"rkBig":0,"z":0}

(rk is the version above; rkBig is a second version I wrote with BigInt and a modulus of 1,000,000,007. All five agreed in every case.) The edge cases I fixed on purpose: the empty pattern returns 0, as "abc".indexOf("") does, and an empty text with a non-empty pattern returns -1:

0 0 -1 -1

Timing, labelled as local

These numbers are from my machine only, best of three runs, with Node v22.22.0. The rk, kmp, naive and zSearch functions are the ones above, running as normal JavaScript.

Random lowercase text, 2,000,000 letters, a 13-letter pattern that is not present:

indexOf     0.9 msnaive       14.0 mskmp         13.9 msrabin-karp  13.1 msz           28.9 ms

On ordinary text the naive method is as fast as KMP, because it almost always fails on the first letter. The built-in is about fifteen times faster than any of my JavaScript versions. The Z version is slower because it builds a joined string and a big array.

Bad case: text of 200,000 letters a, pattern of 2,000 letters a followed by b:

aaaa 200k indexOf     0.9 msaaaa 200k naive       2674.2 msaaaa 200k kmp         4.4 msaaaa 200k rabin-karp  1.9 ms

Naive takes 2.7 seconds; KMP takes 4 milliseconds. Rabin-Karp is fast here because the pattern's hash differs from every window's hash, so it never verifies. (Rabin-Karp's own bad case needs many hash collisions, which this input does not produce.) The built-in indexOf was fast on this input too. I do not know which algorithm V8 uses inside, and I did not read its source, so I cannot explain why; I only report the measurement.

When the built-in is enough

For almost all application code, use the built-ins:

indexOf was 15 times faster than my hand-written code on ordinary text and did not slow down on my bad input. Writing KMP by hand in a product is rarely worth it. Write it when:

1. It is an interview or a learning exercise. They want to see that you know why naive can be quadratic.
2. You work on a stream (bytes arriving in pieces) and cannot keep the whole text. KMP keeps just k, so you can feed it one character at a time.
3. You need a result the built-in does not give: the border or period structure, counts for every prefix, or matches in something that is not a string (an array of numbers, a DNA code in a typed array).
4. You search many patterns (next section).
5. You compare windows in a problem like "longest repeated substring" and need the rolling hash.

Many patterns at once: Aho-Corasick

If you must find k patterns, running a single-pattern search k times costs about k passes over the text. For a list of banned words or a dictionary of 10,000 keywords that is too slow. The standard answer is Aho-Corasick, which is KMP generalised to a trie (a tree of letters, see DSA Lesson 58):

1. Put all patterns in a trie.
2. For each trie node, compute a failure link: the node for the longest proper suffix of this node's text that is also a prefix of some pattern. This is the KMP failure function, but on a tree. A breadth-first search computes all links.
3. Walk the text once, one character at a time, following child links, and falling back along failure links on a mismatch. At each node, report all patterns that end there (a node also reports the patterns reached through its failure links).

Time is about the text length plus the pattern lengths plus the number of matches. I wrote a short version (about 20 lines) and ran the classic example:

const words = ["he", "she", "his", "hers"];const ac = buildAC(words);console.log(searchAC(ac, "ushers").map(([i, w]) => `${words[w]} ends at ${i}`).join("; "));

she ends at 3; he ends at 3; hers ends at 5

In ushers, she and its suffix he end at the same place, which is why a failure link must also report the shorter words. I compared it with a loop that calls indexOf for every word, on 3,000 random cases (alphabet ab, 1 to 4 words, text up to 24 letters):

AC vs indexOf loop, 3000 random cases, mismatches: 0

You rarely write this in an interview. Know the name, what it does, and the one-line reason it works (KMP on a trie). In real systems, grep -F -f patterns.txt style tools use this family of algorithms (from memory, not checked), and Rabin-Karp with a Set of hashes is the quick alternative when all patterns have the same length.

Choosing the algorithm

Common mistakes

1. Using k = 0 on a KMP mismatch. That throws away the border and makes the search wrong or slow. Use k = f[k - 1].
2. Skipping verification in Rabin-Karp. Equal hashes are not equal strings; I showed a real collision (aa and ht).
3. Using a negative number in the rolling update. Add the modulus before taking %.
4. Forgetting the separator in the Z search. Without it, a match can run across the pattern/text border.
5. Handling the empty pattern wrongly. indexOf("") is 0. Decide what you return and test it.
6. Writing your own search in production code where includes would do.
7. Testing only on random text. Naive and KMP looked identical there. Test with a one- or two-letter alphabet.

Try it

1. Compute failure("abcabcd") by hand, then run it to check.
2. Use zArray to find the smallest period of "abcabcabc". (Hint: the smallest i where i + z[i] === n and n % i === 0.)
3. Write findAll(t, p) using KMP that returns all start positions (including overlapping ones: "aaaa" and "aa" give 0, 1, 2). After a full match, set k = f[m - 1] and continue.
4. Make Rabin-Karp fail its filter on purpose with modulus 101: count false positives on 100,000 random letters.
5. Check your findAll against a loop over indexOf(p, i + 1) on thousands of random strings over the alphabet ab.

Answers.

1. 0 0 0 1 2 3 0 (I ran it). The border grows with a, ab, abc, then d breaks it.
2. The Z-array of abcabcabc is 9 0 0 6 0 0 3 0 0. At i = 3: 3 + 6 = 9 = n and 9 % 3 = 0, so the period is 3 (the string is abc three times). I ran zArray on it and printed exactly that list.
3. After a full match, record i - m + 1, then do k = f[k - 1] so that overlapping matches are found.
4. Expect about one false positive per 100 windows, as in the numbers above (2,225 in 200,000 for my 6-letter pattern).
5. They should agree. If not, check the case when the pattern is empty (an infinite loop is a classic bug).

Interview questions

Key takeaways

• Naive search is O(n x m) in the worst case (almost-matching text) and fine on ordinary text.
• KMP precomputes the longest border of each pattern prefix, and never moves back in the text: O(n + m). On a mismatch use k = f[k - 1].
• Rabin-Karp compares rolling hashes and verifies on equal hashes. Collisions are real (aa and ht with modulus 101), so verification is required. It shines for many same-length patterns and window comparison.
• The Z-array gives, for each position, the match length with the string's own prefix. Search with pattern + separator + text.
• Use includes and indexOf in real code. Hand-write only for streaming, other data types, many patterns, string structure, or an interview.
• For many patterns of different lengths, name Aho-Corasick: KMP on a trie.
• Test every string algorithm against the built-in on many random inputs with a tiny alphabet.

What's next

This was the last lesson in the series so far, so there is no Lesson 8 yet. To go further, practise the DSA string lessons: DSA Lesson 30, String Patterns, DSA Lesson 31, Substrings and Windows and DSA Lesson 57, DP on Strings. A good exercise: take the kmp function above and turn it into findAll that returns overlapping matches, then check it against a loop over indexOf.