How Does the KMP Algorithm Work?

The Knuth–Morris–Pratt algorithm, usually called KMP, is a string-matching algorithm. Its task is straightforward: given a longer sequence of characters called the text and a shorter sequence called the pattern, determine whether the pattern occurs inside the text and, when it does, identify where the match begins.

For example, suppose we want to find the pattern ABACA inside the text ABABACA:

Text:    A B A B A C A
Index:   0 1 2 3 4 5 6

Pattern: A B A C A
Index:   0 1 2 3 4

The pattern occurs beginning at text index 2. A direct search can find it, but a direct search may repeat comparisons that have already provided useful information. KMP avoids much of that repeated work by preprocessing the pattern before scanning the text.

The preprocessing step creates a table called the LPS table. LPS stands for longest proper prefix that is also a suffix. The table describes how the pattern overlaps with itself. When a mismatch occurs, KMP uses that overlap information to decide how the pattern can continue matching. The text pointer does not move backward.

That last point is the central idea of KMP. Instead of shifting the pattern and restarting from the beginning every time a comparison fails, KMP keeps the current text position and changes the pattern position according to the LPS table.

This article explains the process step by step:

1. What the string-matching problem looks like.
2. How naive matching works.
3. Why naive matching can repeat work.
4. What prefixes and suffixes are.
5. What “proper” means in the LPS definition.
6. How to build an LPS table.
7. How KMP uses the table during a mismatch.
8. How the text pointer remains moving forward.
9. A complete trace using a seven-character text and a five-character pattern.
10. Practical ways to understand and apply the technique.

1. The string-matching problem​

A string-matching algorithm receives two sequences:

• The text, which is the larger sequence being searched.
• The pattern, which is the sequence we want to locate.

In the example used throughout this explanation:

Text:    A B A B A C A
Index:   0 1 2 3 4 5 6

Pattern: A B A C A
Index:   0 1 2 3 4

The pattern ABACA appears in the text from index 2 through index 6:

Text:    A B A B A C A
             A B A C A
             ---------

The indentation shows the successful alignment. The pattern starts under the text character at index 2:

Text positions:    2 3 4 5 6
Text characters:   A B A C A
Pattern:           A B A C A

The algorithm must discover that alignment while comparing characters. The challenge is not simply comparing two strings. It is deciding what to do with the information already learned when a comparison fails.

If several characters have matched and the next characters differ, should the algorithm throw away all of that progress? A naive search often behaves as if it should. KMP asks a more useful question:

Does the portion that already matched contain a shorter beginning of the pattern that could still be valid?

The LPS table answers that question quickly.

2. How naive matching works​

The naive approach aligns the pattern with the beginning of the text and compares characters from left to right. If all pattern characters match, the search succeeds. If a mismatch occurs, the pattern is shifted, often by one position, and the comparison starts again.

For the first alignment in our example, the comparison looks like this:

Text:    A B A B A C A
Pattern: A B A C A
         | | | x

The first three comparisons succeed:

• Text index 0 contains A, and pattern index 0 contains A.
• Text index 1 contains B, and pattern index 1 contains B.
• Text index 2 contains A, and pattern index 2 contains A.

The fourth comparison fails:

• Text index 3 contains B.
• Pattern index 3 expects C.

A simple search can shift the pattern one position to the right:

Text:    A B A B A C A
           A B A C A

It then starts comparing again under the new alignment. Depending on the implementation, it may compare characters that were already compared during the previous alignment. Some of those comparisons are unavoidable in a basic approach, but the first alignment already revealed useful structure.

The matched portion was:

A B A

That portion is not just a random collection of characters. Its first character and last character are both A. This means a one-character prefix of the pattern also appears as a suffix of the portion that matched. KMP preserves that fact instead of discarding it.

3. What work can be repeated?​

The naive method treats each shifted alignment as a fresh attempt. Imagine that a pattern begins with a sequence that repeats internally. A search may compare that sequence, encounter a mismatch, shift by one character, and compare much of the same sequence again.

Consider the partial match in the example:

Matched portion: A B A

The pattern itself begins with A:

Pattern: A B A C A
         -
         A

The matched portion also ends with A:

Matched: A B A
             -
             A

Therefore, the final A of the matched portion can act as the first A of a new possible match. KMP does not need to move the text scan back to the beginning of the previous alignment to discover this. It already knows the relationship from the pattern.

This is the kind of repeated work that KMP avoids:

• The text characters that produced the successful prefix are not forgotten.
• The search does not restart the pattern from zero after every mismatch.
• The text pointer continues forward.
• The pattern position falls back to a position chosen by the LPS table.

The pattern may move logically relative to the text, but the text scan itself does not move backward. This distinction is important. KMP does not need to physically redraw the pattern after every mismatch. It can represent the shift by changing the pattern index it is comparing.

4. Prefixes and suffixes​

The LPS table is based on prefixes and suffixes, so these terms need to be precise.

A prefix is a sequence taken from the beginning of a string. For ABACA, the prefixes include:

A
AB
ABA
ABAC
ABACA

A suffix is a sequence taken from the end of a string. Some suffixes of ABACA are:

A
CA
ACA
BACA
ABACA

A sequence can be both a prefix and a suffix. For ABACA, the one-character sequence A is both:

• a prefix, because the string begins with A; and
• a suffix, because the string ends with A.

The complete string ABACA is technically both a prefix and a suffix of itself, but KMP excludes that case when calculating LPS values. This is why the definition uses the word proper.

A proper prefix is a prefix that is shorter than the complete string. For ABACA, the proper prefixes are:

A
AB
ABA
ABAC

The complete string ABACA is not a proper prefix.

The LPS value at a pattern position is the length of the longest proper prefix that is also a suffix of the substring ending at that position.

5. The LPS table for ABACA​

Let us calculate the LPS values for the pattern one position at a time:

Pattern: A B A C A
Index:   0 1 2 3 4

The LPS table is:

LPS:     0 0 1 0 1

Each entry describes the substring from the beginning of the pattern through that index.

Index 0: substring A​

The substring is only one character long:

A

It has no nonempty proper prefix. Therefore:

LPS[0] = 0

Index 1: substring AB​

The proper prefixes are:

A

The suffixes include:

B

There is no nonempty sequence that appears in both lists, so:

LPS[1] = 0

Index 2: substring ABA​

The proper prefixes are:

A
AB

The suffixes are:

A
BA

The longest common sequence is A, with length 1:

LPS[2] = 1

This is the overlap that matters during the search. The substring ABA begins with A and ends with A.

Index 3: substring ABAC​

The proper prefixes are:

A
AB
ABA

The suffixes include:

C
AC
BAC

There is no nonempty common sequence, so:

LPS[3] = 0

Index 4: substring ABACA​

The proper prefixes are:

A
AB
ABA
ABAC

The suffixes include:

A
CA
ACA
BACA

The longest common sequence is again A, so:

LPS[4] = 1

The completed table is:

Pattern: A B A C A
Index:   0 1 2 3 4
LPS:     0 0 1 0 1

6. Reading an LPS value as an overlap​

An LPS value can be understood as the length of an overlap between the beginning and end of a pattern prefix.

For the substring ABA:

A B A
-   -

The first A and final A match. The overlap length is 1.

For the substring ABACA:

A B A C A
-       -

Again, the first and last characters match, so the overlap length is 1.

The LPS value does not mean that the entire pattern has matched. It describes how much of the pattern's beginning is already represented at the end of the portion matched so far.

Suppose the search has matched ABA and then fails on the next character. The LPS value for the matched portion is 1. KMP can therefore preserve one character of progress. It changes the pattern position from 3 to 1, because pattern index 0 through index 0 represents the useful prefix A.

The current text character remains available for comparison. KMP now checks it against pattern index 1 rather than starting a completely new alignment at pattern index 0.

7. Building the LPS table without restarting blindly​

The LPS table is built from the pattern before the text scan begins. Its construction uses the same general principle as the search: preserve known prefix information instead of checking every possibility from scratch.

A typical construction maintains two logical positions:

• A position that moves through the pattern and receives LPS values.
• A length representing the current candidate prefix that also matches a suffix.

For the pattern ABACA, begin with:

Pattern: A B A C A
Index:   0 1 2 3 4
LPS:     0

The first entry is always zero because a one-character substring has no nonempty proper prefix.

Constructing LPS[1]​

The next character is B. The current candidate prefix character is A:

B versus A

They differ. There is no shorter nonempty candidate to try, so the value is zero:

LPS: 0 0

Constructing LPS[2]​

The next character is A, and the current candidate prefix character is also A:

A versus A

They match. The candidate prefix length grows from 0 to 1:

LPS: 0 0 1

This records the overlap in ABA.

Constructing LPS[3]​

The next character is C. The current candidate prefix position expects B:

C versus B

They differ. Instead of immediately restarting every comparison, the construction consults the LPS information for the shorter candidate. In this pattern, no shorter nonempty candidate produces a match for this position. The candidate length becomes zero, and the value is:

LPS: 0 0 1 0

Constructing LPS[4]​

The final character is A. With the current candidate length at zero, compare it with the first pattern character:

A versus A

They match, producing a candidate prefix length of 1:

LPS: 0 0 1 0 1

The completed table is:

Pattern: A B A C A
LPS:     0 0 1 0 1

For longer patterns, the construction may fall back through several earlier LPS values. That fallback is what prevents the table-building phase from repeatedly comparing all prefixes and suffixes independently.

8. How KMP uses the table during matching​

Once the LPS table is ready, KMP scans the text and pattern using two positions:

• t, the current text position.
• p, the current pattern position.

The basic rules are:

1. If Text[t] equals Pattern[p], advance both positions.
2. If the pattern position reaches the pattern length, the pattern has been found.
3. If the characters differ and p is not zero, replace p with the LPS value for the previously matched pattern position. Leave t unchanged.
4. If the characters differ and p is zero, advance t because there is no partial pattern match to preserve.

The third rule is the defining KMP behavior. A mismatch after partial progress does not necessarily advance the text pointer. The algorithm first asks whether the matched pattern prefix has a shorter border, where a border is a sequence that is both a prefix and a suffix.

In the example, the matched portion is ABA, and its LPS value is 1. If the next comparison fails, KMP changes:

p = 3

to:

p = LPS[2] = 1

The text position remains at the mismatching character.

9. Complete trace with the seven-character text​

Now trace the search carefully:

Text:    A B A B A C A
Index:   0 1 2 3 4 5 6

Pattern: A B A C A
Index:   0 1 2 3 4
LPS:     0 0 1 0 1

Let t be the text index and p be the pattern index.

First comparison​

Initially:

t = 0
p = 0

Compare:

Text[0]    = A
Pattern[0] = A

The characters match. Advance both:

t = 1
p = 1

Second comparison​

Text[1]    = B
Pattern[1] = B

They match:

t = 2
p = 2

Third comparison​

Text[2]    = A
Pattern[2] = A

They match:

t = 3
p = 3

At this point, the matched portion is ABA.

The mismatch​

Now compare:

Text[3]    = B
Pattern[3] = C

The characters differ. The pattern position is not zero, so KMP consults the LPS value for the last matched pattern position, index 2:

LPS[2] = 1

KMP changes the pattern position:

p = 1

It does not move the text position:

t = 3

The same text character is now compared with pattern index 1:

Text[3]    = B
Pattern[1] = B

They match. Advance both:

t = 4
p = 2

Continuing after the fallback​

Compare:

Text[4]    = A
Pattern[2] = A

They match:

t = 5
p = 3

Compare:

Text[5]    = C
Pattern[3] = C

They match:

t = 6
p = 4

Compare the final characters:

Text[6]    = A
Pattern[4] = A

They match. The pattern is complete.

The match begins at:

start index = t - pattern length = 7 - 5 = 2

Therefore, the occurrence is:

Text:    A B A B A C A
             A B A C A

The important moment is the mismatch at text index 3. A naive restart might shift the pattern and begin comparing from an earlier text position. KMP keeps t at 3, uses LPS[2], and resumes with pattern index 1.

10. What “the text pointer never moves back” means​

The phrase means that the main text index advances from left to right and is never decreased after the search has moved past a position. When a mismatch occurs after a partial match, KMP changes the pattern position instead of moving the text pointer backward.

This does not mean that a text character can never be compared again. In the example, the character B at text index 3 is first compared with pattern character C, then compared with pattern character B. It is still used twice, but the algorithm does not return to an earlier text index and restart a complete alignment.

The distinction is:

• The text position remains at the mismatch.
• The pattern position falls back according to the LPS table.
• The search continues from the information already established.

KMP uses the current text character again only because a different pattern position may now be appropriate. It does not need to reread the earlier text characters that created the known partial match.

11. Why the pattern's structure matters​

The LPS table belongs to the pattern, not the text. It summarizes the pattern's internal repetition and overlap. A pattern with repeated sequences can preserve more progress after a mismatch.

For example, consider the pattern ABAB:

A B A B

Its beginning AB is also its ending AB:

Prefix: A B
Suffix:     A B

That overlap has length 2. If matching fails after ABAB, the pattern may be able to preserve two characters of useful structure rather than falling all the way back to zero.

By contrast, a pattern with no repeated beginning-and-ending sequence has mostly zero LPS values. The fallback opportunities are smaller, but the algorithm still follows the same rules.

The table gives KMP an explicit answer to the question:

After a mismatch, what is the longest prefix of the pattern that could already be matched by the text characters we just examined?

The answer varies by pattern position. That is why the table has one value for each pattern character rather than one single shift value for the entire pattern.

12. Common misunderstandings about KMP​

KMP does not reverse the pattern​

KMP does not depend on reading the pattern from right to left. Its main information comes from prefix and suffix relationships, and the search can proceed from left to right.

The LPS table is not a general repeated-substring table​

An LPS value is not the length of any repeated sequence anywhere in the substring. The sequence must be both a prefix and a suffix of the substring ending at the relevant position. A repeated sequence in the middle does not count unless it also appears at both ends.

The complete substring is not counted as a proper prefix​

Every string is technically a prefix and suffix of itself. If that complete match were included, every LPS value would simply equal the substring length, which would not describe a useful fallback. “Proper” means shorter than the complete substring.

A mismatch does not always advance both positions​

When the pattern has already matched one or more characters, KMP can change only the pattern position. The text position stays at the mismatch while the algorithm tries the fallback pattern position.

The LPS table is built from the pattern​

The table does not describe the text. It describes how the pattern overlaps with itself. The same pattern can use the same table when it is searched in different text strings.

A fallback is not a claim that the whole pattern matches​

If KMP falls back to pattern position 1, it is not declaring that a new match has already been found. It is saying that one character of the pattern can be treated as already matched, based on the overlap in the characters examined so far.

13. A practical implementation model​

A conceptual implementation has two phases.

Phase one: build the LPS table​

Create an array with one entry for each pattern position. Set the first value to zero. Then move through the remaining pattern characters while maintaining the length of the current candidate prefix.

When the next characters match, extend the candidate and record the new length. When they differ, use an earlier LPS value to try a shorter candidate. If no candidate remains, record zero and continue.

The important implementation idea is that a mismatch during preprocessing does not require starting every comparison from the beginning of the pattern. The table already contains fallback information for shorter prefixes.

Phase two: scan the text​

Maintain a text index and a pattern index.

• On a match, advance both indexes.
• When the pattern index reaches the pattern length, report a match.
• On a mismatch with a nonzero pattern index, replace the pattern index with the LPS value for the previously matched portion.
• On a mismatch with a zero pattern index, advance the text index.

The index details must be handled carefully. In particular, advancing the text pointer immediately after every mismatch would remove the behavior that allows KMP to reuse the current text character after a fallback.

Another common error is using the wrong LPS entry. The fallback corresponds to the portion of the pattern that matched immediately before the mismatch. If the mismatch occurs while comparing pattern index p, the relevant matched portion ends at p - 1.

14. How KMP relates to text search​

KMP is useful whenever one known sequence must be located inside another sequence. A basic text-search feature can treat the user's query as the pattern and a document or stored string as the text.

For example, if a search box receives the query ABACA, a matching routine can scan a larger string and determine whether that exact sequence occurs. When the query contains repeated structure, the LPS table helps retain useful progress after a mismatch. The same general procedure can find the first occurrence, identify a match position, or continue scanning for later occurrences.

KMP is especially valuable as a way to understand the matching step itself. A larger text-search system may use other ways to locate candidate documents or reduce the amount of text that must be inspected. Once a text and pattern are being compared, however, the KMP idea remains relevant: use the pattern's internal structure instead of restarting unnecessarily.

The technique is also useful for teaching and debugging search behavior. When a search routine appears to repeatedly compare the same prefix after a mismatch, the LPS table provides a concrete way to identify which comparisons can be preserved.

15. KMP and search boxes​

A search box often accepts a short query and checks it against text. The exact product behavior may involve many additional concerns, such as case handling, tokenization, or searching multiple records. At the core, however, one operation may still be checking whether a known sequence occurs in another sequence.

KMP offers a disciplined approach to that operation:

1. Prepare the query's prefix and suffix relationships.
2. Scan the text from left to right.
3. Preserve partial progress when the query and text disagree.
4. Use the LPS fallback instead of restarting blindly.

The practical value is not that every search box must use KMP. The appropriate technique depends on the surrounding system and the kind of search required. The value is that KMP clearly demonstrates how preprocessing a pattern can reduce repeated comparison work during matching.

16. KMP and autocomplete​

Autocomplete is related to text matching but is not identical to it. Autocomplete commonly needs to retrieve many possible completions that begin with a user's partial input. That task is naturally concerned with shared beginnings among many stored words or phrases.

KMP's direct job is different: it matches one pattern against a text. It is not a replacement for every structure used to organize many possible completions. Still, the two ideas are connected by a general principle: organize known character relationships so that future queries do not repeat work unnecessarily.

For a particular candidate string, KMP can help explain or perform the matching step. For a collection of candidates, a separate structure may be more appropriate for finding strings that share a prefix. Keeping these roles separate prevents a common misunderstanding: an algorithm designed to match one pattern in one text is not automatically the best structure for retrieving an entire set of autocomplete suggestions.

17. Practical takeaways​

The main lessons of KMP are:

• Naive matching may repeat comparisons after shifting the pattern.
• A partial match can contain an overlap between its beginning and its end.
• The LPS table records the longest proper prefix that is also a suffix for each pattern position.
• The table is built from the pattern before the main text scan.
• On a mismatch after partial progress, KMP uses the appropriate LPS value as a fallback.
• The text pointer does not move backward during the search.
• If no pattern character has matched, the text pointer advances.
• The pattern's repeated structure determines how much progress can be preserved.
• The LPS table can be reused whenever the same pattern is searched in another text.

The seven-character example shows the essential shift clearly. KMP first matches ABA and then encounters a mismatch because the text contains B where the pattern expects C. Instead of discarding the partial match, KMP observes that the final A of ABA is also the beginning of the pattern. The LPS value is 1, so the pattern resumes from its second character while the text pointer remains at the mismatching B.

That is the heart of the algorithm: KMP uses the pattern's own prefix and suffix structure to avoid repeating work, while scanning the text in a forward direction.