KMP String Matching

KMP string matching finds a pattern inside a text without backing the text cursor up after a mismatch. It first builds an LPS table for the pattern, then uses that table to retain a known matching border instead of restarting from zero. Preprocessing costs O(m), search costs O(n), and auxiliary space is O(m).

Picture the pattern printed on a transparent strip beneath the text. A mismatch does not send the strip all the way back to its first mark. You slide it just far enough for a prefix already known to match to sit under the matching suffix. The current text character stays put while the strip moves. KMP's LPS table tells you which overlap is safe.

When KMP earns its keep

Most production code should call the language's built-in substring search. Write KMP yourself when the input is one-way, such as a socket, pipe, or file chunk you cannot rewind, or when a predictable O(n + m) worst-case bound matters more than average-case shortcuts. Preprocess the pattern once, carry j across chunks, and discard text you have already passed.

How KMP string matching works

LPS stands for "longest proper prefix that is also a suffix." A proper prefix cannot be the whole string. For the pattern prefix ABABA, the longest proper prefix that also appears at the end is ABA, so its LPS value is 3.

KMP builds one LPS value for every pattern position. Let k be the position whose value is being computed and len be the length of the border currently under consideration. If pattern[k] equals pattern[len], the border grows by one and that new length is stored in lps[k]. If they differ and len > 0, KMP sets len = lps[len - 1] and retries the same pattern[k] against a shorter border. It does not advance k on that fallback. If no border remains, lps[k] is 0 and k advances.

The search uses the same idea with two cursors. i points into the text and j points into the pattern. A matching pair advances both. A mismatch at j == 0 advances only i, because there is no verified prefix to save. A mismatch at j > 0 sets j = lps[j - 1] and retries the same text[i].

Retain 3, shift 2

That last assignment is easy to misread. The LPS value is a retained length, not a physical shift. If j falls from 5 to 3, KMP keeps three matched characters and slides the transparent strip by 5 - 3 = 2 positions. The two numbers describe different things.

The text cursor never moves backward, but a text character may be compared more than once. On a fallback, i stays fixed while a shorter pattern prefix comes under it. That distinction is the honest reason KMP is linear; "each text character is compared once" is a tempting slogan and a false one.

KMP string matching step by step

Use the default text ABABABACA and pattern ABABACA.

1. Start the pattern table with lps[0] = 0. The one-character string A has no proper prefix, so it cannot have a non-empty proper border.
2. At pattern index 1, B differs from A and no shorter border exists, giving lps[1] = 0. Indices 2, 3, and 4 extend the alternating border: A matches A, then B matches B, then A matches A. Those entries become 1, 2, and 3.
3. Index 5 is the useful troublemaker. C first disagrees with the character after the length-3 border. The builder falls from len = 3 to len = lps[2] = 1, retries the same C, falls again to len = lps[0] = 0, and finally writes 0. Index 5 never moved during those retries.
4. At index 6, A matches the first pattern character, so lps[6] = 1. The finished table is [0, 0, 1, 2, 3, 0, 1].
5. Search begins with i = 0 and j = 0. The first five pairs match: ABABA. Both cursors advance together until i = 5 and j = 5.
6. Now text[5] is B, while pattern[5] is C. The search reads lps[4] = 3 and changes j from 5 to 3. It retains the border ABA, shifts the pattern strip by two positions, and holds i = 5.
7. Retry that same text[5], now against pattern[3]. B matches B; the remaining A, C, and A match as well. The search ends with i = 9 and j = 7, so the match starts at i - j = 2.

The advance i (bug) variant changes only the fallback branch. After setting j = lps[j - 1], it also increments i. On this exact trace, that extra move skips the B at text index 5 instead of retrying it. The real match still begins at index 2, but the corrupted search runs out of text and returns -1. One innocent-looking increment breaks the invariant the table was built to protect.

Time and space complexity

Let n be the text length and m the pattern length.

The linear time complexity comes from monotone progress, not from a one-comparison-per-character promise. During preprocessing, each iteration either advances k or shortens len; len cannot fall more often than it previously grew. During search, each iteration either advances i or shortens j; the total distance j can fall is bounded by the distance it previously gained. No text cursor reset can create another full scan.

The LPS array accounts for O(m) auxiliary space. The cursors and counters use O(1) space.

Edge cases

• An empty text with a non-empty pattern has no match, so the search returns -1.
• A pattern longer than the text may make partial progress, but it still returns -1 when the text is exhausted.
• A one-character pattern has the table [0]. Search then reduces to scanning for that character.
• Repeated characters such as pattern AAAA produce increasing borders: [0, 1, 2, 3]. A later mismatch may trigger several fallbacks while i remains fixed.
• Overlapping matches are exactly where LPS earns its keep. This implementation returns the first match; a find-all version records a match and then sets j = lps[j - 1] to continue.
• The lesson rejects an empty pattern because APIs disagree on its return convention. A production implementation must choose and document one before reading pattern[0].

Common mistakes

• Using the LPS value as a shift count. Set j = lps[j - 1]; the pattern moves by the distance j fell.
• Incrementing i after a fallback with j > 0. The same text character must be retried. The advance i (bug) variant proves the cost: it misses the valid match at index 2 and returns -1.
• Incrementing k while the LPS builder is falling back. A shorter border still needs to be tested against the current pattern character, so k stays put.
• Restarting j at 0 on every mismatch. That can remain correct, but it discards the table's saved work and gives up KMP's linear bound.
• Calling the full string a proper prefix. "Proper" excludes the whole string; otherwise every prefix would trivially be its own longest border and the table would be useless.
• Claiming that every text character is compared once. Fallback can retry one character against several pattern positions. The useful invariant is narrower and stronger: correct KMP never decreases i and never advances it during a positive-length fallback.