cf.completefrontend
STRING ALGORITHMS · CORE

KMP pattern search

Find every place a pattern appears in a text without ever moving backward in the text, using a table of the pattern's own repeats.

Time O(n + m)Space O(m)6 practice problemsStep-through picture

The idea

The simple way to find a pattern in a text is to try every start position and compare letter by letter. When a comparison fails, you move the start by one and compare again from the pattern's first letter. On text like aaaaaaab with the pattern aaab, that redoes the same comparisons again and again.

KMP, named after Knuth, Morris, and Pratt, never re-reads a text character. When a mismatch happens after some letters matched, it already knows those letters: they are the start of the pattern. So it asks: how much of the pattern's start is also at the end of what just matched? It can keep that much and continue.

That answer is stored in a table called lps, short for longest proper prefix that is also a suffix. lps[i] says: for the first i + 1 letters of the pattern, how long is the longest start that also appears at the end (not counting the whole thing)? With it, the search runs in O(n + m) time for a text of length n and a pattern of length m.

An everyday example

Following a dance routine

You know a routine: step, clap, step, clap, spin. You watch a dancer and count how far into the routine they are. They do step, clap, step, clap, and then a step instead of a spin. You don't start counting from zero. The last two moves were step, clap, which is how the routine begins, so you are already two moves in, and the new step might continue it. A small cheat sheet tells you, for each point in the routine, how far back to fall when the next move is wrong.

How the example maps to the code
In the exampleIn the code
The routine you are looking forpattern
The moves the dancer makestext, read once from left to right with i
How many moves of the routine you've matchedj
The cheat sheet of where to fall back toThe lps table
Falling back after a wrong movej = lps[j - 1]

From the slow way to kmp pattern search

  1. The simple search tries each start in the text and compares the pattern letter by letter. When a start fails after matching many letters, the next start re-reads most of those letters. With text and pattern full of near-matches, that is O(n · m) comparisons.
  2. But when a mismatch happens after j letters matched, those j text letters aren't unknown: they equal the first j letters of the pattern. So which later starts could still work is a question about the pattern alone, and it can be answered before the search begins.
  3. A later start can only work if the pattern's beginning lines up with the end of those j letters. The longest such overlap is the longest proper prefix of pattern[0..j-1] that is also its suffix, where proper means shorter than the whole thing. Store it as lps[j - 1]. On a mismatch, keep that many letters matched and try the same text letter again, without moving back in the text.
  4. Building lps is the same search, run on the pattern against itself, with len playing the part of j. Then the search walks the text once with i, matching, falling back through lps, and recording a match whenever j reaches the pattern's length. That loop is KMP.

How it works

  1. Build lps for the pattern. len is the length of the current start that matches; it starts at 0, and lps[0] is 0.
  2. For each i from 1, while len > 0 and pattern[i] doesn't continue that start, fall back with len = lps[len - 1]. If it does continue, add one to len. Store lps[i] = len.
  3. Search the text with j, the number of pattern letters matched so far, starting at 0.
  4. For each text index i, while j > 0 and text[i] doesn't match pattern[j], fall back with j = lps[j - 1].
  5. If text[i] matches pattern[j], add one to j.
  6. If j reaches the pattern's length, a match ends at i, so it starts at i - j + 1. Record it and fall back with j = lps[j - 1] to look for overlapping matches.

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 kmpSearch(text, pattern) {
  2. const lps = new Array(pattern.length).fill(0);
  3. let len = 0;
  4. for (let i = 1; i < pattern.length; i++) {
  5. while (len > 0 && pattern[i] !== pattern[len]) {
  6. len = lps[len - 1];
  7. }
  8. if (pattern[i] === pattern[len]) len++;
  9. lps[i] = len;
  10. }
  11. const matches = [];
  12. let j = 0;
  13. for (let i = 0; i < text.length; i++) {
  14. while (j > 0 && text[i] !== pattern[j]) {
  15. j = lps[j - 1];
  16. }
  17. if (text[i] === pattern[j]) j++;
  18. if (j === pattern.length) {
  19. matches.push(i - j + 1);
  20. j = lps[j - 1];
  21. }
  22. }
  23. return matches;
  24. }

How fast it is

TimeO(n + m)
Extra memoryO(m)

The text index only moves forward and every fall back undoes an earlier step forward, so the search is O(n). Building the table is O(m) for the same reason. Only the lps table grows with input size.

  • Best caseO(n + m)

    The pattern's first letter never appears in the text: j stays 0, and each text letter is checked once after the O(m) table.

  • Average caseO(n + m)

    Any text: i only moves forward, and every fall back undoes an earlier step forward.

  • Worst caseO(n + m)

    Text full of near-matches, like the pattern aab in aaaaaaaa: many fall backs, but never more than the steps forward, so about 2n comparisons at most.

Common mistakes

  • Moving the text index backward after a mismatch, like the simple search does. That throws away KMP's whole advantage.
  • Using if instead of while for the fall back. One fall back might not be enough; keep falling back until the letter fits or j is 0.
  • Setting j = 0 after a full match. That misses overlapping matches, such as aa appearing at 0, 1, and 2 in aaaa. Fall back to lps[j - 1] instead.
  • Calling it with an empty pattern. j === pattern.length is true right away and lps[-1] is undefined. Decide what an empty pattern means and handle it before the loop.

When to use it

Look for these clues in a problem:

  • You need every position where a pattern appears in a text, including overlapping ones.
  • The text or pattern is long (say 10^5 characters), so trying every start is too slow.
  • The question is about a string's repeats, like its shortest repeating unit or the longest start that is also an end.
  • You must read the text once, as a stream, without going back.

Check yourself

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

What is lps for the pattern aabaab?

[0, 1, 0, 1, 2, 3]. For example, lps[5] = 3, because aab both starts and ends aabaab.

Why must the prefix in lps be proper, shorter than the whole piece?

If lps[j - 1] could equal j, a fall back would leave j unchanged, and the while loop would never end.

After a full match, why does the code set j = lps[j - 1] and not 0?

The next match may overlap this one. Keeping the longest overlap finds aa at 0, 1, and 2 in aaaa; j = 0 misses 1.

Why does the text index i never move back?

On a mismatch, j falls back instead. lps already says which of the recent letters still match, so there's nothing to re-read.

Practice problems

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

Not started

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

Start practicing

easy

medium

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 search keeps one rule at the top of each step: j is the length of the longest start of the pattern that ends right before text[i], and it is shorter than the whole pattern. At the start, j = 0 and nothing has been read, so the rule holds.

When text[i] doesn't continue the match, the candidates for the new longest match are the starts of the pattern that are also ends of pattern[0..j-1]. lps[j - 1] is the longest of them, lps[lps[j - 1] - 1] the next longest, and so on. The while loop tries them from longest to shortest, so the first one that text[i] continues is the correct new j. No possible match is skipped.

After a full match, j = lps[j - 1] restores the rule, because the next match may overlap this one by exactly that much. Every fall back makes j smaller, and j grows by at most one per text letter, so all fall backs together are at most n. The search ends after n steps with every match recorded. Building lps follows the same argument on the pattern, in O(m).

Going deeper

3 more ideas

Why falling back to lps[j - 1] never skips a match

When j letters have matched, the last j text letters equal pattern[0..j-1]. Any match that starts later and overlaps them must begin with a start of the pattern that is also an end of those j letters. The longest such overlap is lps[j - 1], so jumping there is the biggest jump that can't skip a possible match. Smaller overlaps are tried next if this one fails too.

Why it is linear

In the search, i only moves forward, n times. j grows by at most one per step and every fall back makes it smaller, so the total number of fall backs can't be more than the total growth, n. That makes the search O(n). The same argument makes building lps O(m). The table uses O(m) memory.

Uses of the table on its own

lps[m - 1] is the longest start of the pattern that is also its end. If m is divisible by m - lps[m - 1], the pattern is a smaller unit repeated, and that unit has length m - lps[m - 1]. For example abcabcabc has lps[8] = 6, so it is abc repeated three times.

Work it by hand

Every step in a table, with why

Find every start of rara in a 9-letter text. One mismatch needs two fall backs, and the two matches overlap.

text = "rarrarara", pattern = "rara"

StepPhaseiLetterFall backlen or jWhat happensWhy
1build1a-len = 0a !== r: lps[1] = 0ra has no start that is also an end.
2build2r-len = 1r === r: lps[2] = 1rar starts and ends with r.
3build3a-len = 2a === a: lps[3] = 2rara starts and ends with ra. The table is [0, 0, 1, 2].
4search0r-j = 1matchThe search starts with j = 0.
5search1a-j = 2matchra matched so far.
6search2r-j = 3matchrar matched; the pattern wants a next.
7search3r3 → 1 → 0j = 1fall back twice, then matchr isn't pattern[3]. Fall back to j = lps[2] = 1, but pattern[1] is a, still wrong. Fall back to j = lps[0] = 0; pattern[0] is r, which matches. i never moves back.
8search4a-j = 2matchA new attempt that began at index 3.
9search5r-j = 3matchrar again.
10search6a-j = 4 → 2full match at 3j reaches 4, so a match starts at 6 - 4 + 1 = 3. Then j = lps[3] = 2 keeps ra, which may begin the next match.
11search7r-j = 3matchThe kept ra plus this r.
12search8a-j = 4 → 2full match at 5The second match starts at 5, overlapping the first. The text has ended.

It returns [3, 5]. The text index i moved forward 9 times and never back; the only extra work was the two fall backs at i = 3.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
KMP pattern searchO(n + m)O(m)One pattern, with a guaranteed linear time whatever the text looks like.
Simple searchO(n · m)O(1)Short patterns in ordinary text. In practice, use the built-in indexOf or includes, which are heavily tuned.
Rabin-Karp rolling hashO(n + m)O(1)Many patterns of the same length, or quick checks of whether two pieces are equal. Its worst case is slower.
Z-algorithmO(n + m)O(n + m)The same result from a different idea that some people find easier to remember.

Extra memory: O(m) for lps, plus the matches list. The text is read one letter at a time, so it could even come from a stream.

How the steps grow

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

Inputs that need care

5 tricky inputs
An empty pattern: kmpSearch("abc", "")
j === pattern.length is true at once, so it pushes a match at 1, then sets j to lps[-1], which is undefined. It returns [1], which makes no sense. Return early with whatever an empty pattern should mean.
A pattern longer than the text: kmpSearch("ab", "abc")
j can never reach 3, so it returns [] after reading the text once. Comparing lengths first skips building the table.
Overlapping matches: kmpSearch("aaaa", "aa")
Falling back to lps[1] = 1 after each match finds the starts 0, 1, and 2. Setting j = 0 instead finds only 0 and 2.
A pattern with no repeats: "abcd"
lps is all zeros, so every mismatch falls back to j = 0. KMP then acts like the simple search, but still never moves i back.
Accented letters written two ways
é can be one character or e followed by an accent mark, two characters. Then the same-looking text doesn't match. Call normalize("NFC") on both strings first.

Variations and follow-ups

Twists interviewers add

One loop over a joined string

Build lps for pattern + "#" + text, where # appears in neither. Every position whose value equals pattern.length ends a match. It is one loop instead of two, with the same O(n + m) time but more memory.

Shortest palindrome by adding in front

Build lps for text + "#" + reversed text. The last value is the length of the longest palindrome that starts at index 0. Putting the rest of the text, reversed, in front gives the shortest palindrome that ends with text.

A table of next states

For a small alphabet, compute ahead of time, for each j and each letter, what j becomes. The search then does one table lookup per letter with no fall back loop, using O(m · alphabet) memory.

Many patterns at once

To find many patterns in one pass, Aho-Corasick puts all the patterns in a trie and adds fall back links between its nodes. Those links are the same idea as lps, spread across all the patterns.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "find all occurrences" with a time guarantee, "the shortest palindrome by adding letters in front", or "is this string a smaller piece repeated". The lps table alone answers the last two.
  • Explain lps with an example before coding: "for rara, lps[3] = 2, because ra both starts and ends it, so after a mismatch I keep those 2 letters".
  • Point out that both loops are the same idea: building the table matches the pattern against itself. Writing them the same way avoids bugs.
  • Test by hand: overlapping matches like aa in aaaa, a pattern with no repeats, and a fall back that needs two steps. The usual follow-up is the running time: j can fall back at most as many times as it grew.

Where frontend code uses it

The same idea in real UI code
  • Find-in-page and editor search boxes find every occurrence of a query in a long document; a linear-time search like KMP keeps that fast on big files.
  • Highlighting all matches of a search term in a chat log or table cell is the same "every position, overlaps allowed" task.
  • Streaming parsers that look for a marker, such as a multipart boundary in an uploaded body or the end of an event in a streamed response, can use KMP because it never needs to look back at earlier chunks.

Related algorithms