Faangprep Logo
Log inStart free
Browse curriculum

KMP Algorithm

The Knuth-Morris-Pratt (KMP) algorithm searches for a pattern in a text efficiently using the LPS array.

LPS[k] is how much of the pattern's own beginning reappears at the end of its first k+1 characters. Build that table from the pattern alone — the text is never touched — then scan the text once: whenever a run of matches breaks after j characters, LPS[j-1] says how many of them are still in place, so the pattern slides forward by j − LPS[j-1] and the text cursor never moves backwards. Compares counts every comparison KMP makes, the table included; Naive is what a restart-from-scratch scan would spend on the same input.

SETUP

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

T

A
B
A
B
D
A
B
A
C
D
A
B
A
B
C
A
B
A
B

P

A
B
A
B
C
A
B
A
B

LPS

Start

0

Found

0

Compares

0

Naive

29

 

Two phases, and the first one never looks at the text. Build a table off the pattern alone — for each position, how much of the pattern's own front is repeated at the end of everything up to there — then scan the text once, using the table to decide how far to slide whenever a run breaks. The naive count on the right is what an ordinary scan would spend on this input; the figure keeps both numbers so the comparison is checkable rather than asserted.

Next

LPS[0] is 0 for every pattern, and not by convention: a PROPER prefix has to be shorter than the string it belongs to, so the longest one available to a single character is the empty string. The rest of the table is worked out by matching the pattern against itself — the text is never looked at during this phase, which is why the table can be built before the text is even known.

Text

Pattern

Intuition

The Naive approach backtracks the text pointer unnecessarily. KMP uses the pattern's own structure (LPS array) to skip characters that we know will match, avoiding redundant comparisons.

Concept

  • LPS Array: Stores the length of the longest proper prefix which is also a suffix for each sub-pattern.
  • Optimization: When a mismatch occurs at pattern index j, we don't reset j to 0. We reset it to LPS[j-1].
  • Complexity: O(N + M) time, where N is text length and M is pattern length.

How it Works

Algorithm:

  1. Build LPS: Compute LPS array for the pattern.
  2. Search: Iterate through text with index i and pattern with index j.
  3. If match, increment both.
  4. If mismatch, update j = LPS[j-1] (don't move i).
  5. If j == M, pattern found! Reset j = LPS[j-1].

Step-by-Step Breakdown

Watch the visualization:

  • Phase 1: See how the LPS array is built by comparing prefixes and suffixes.
  • Phase 2: See the pattern slide. Notice how it jumps forward on mismatches instead of sliding by just 1.

When to Use

  • Searching in large texts.
  • Streaming text search.

When NOT to Use

  • Very short patterns (overhead of LPS might not be worth it).

How to Identify

"Pattern matching", "Avoid backtracking", "O(N) search".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Naive Search

Next

Rabin-Karp

Frequently Asked Questions

What does the LPS array actually store?

For each prefix of the pattern, the length of the longest proper prefix of it that is also its suffix. On a mismatch at pattern index j that value is the longest already-matched piece you can keep, so you resume at LPS[j-1] instead of 0.

Why does the text pointer never move backwards?

Because a mismatch is resolved by moving only the pattern pointer. The text index advances at most N times and the pattern index falls only through LPS values, which bounds the total work at O(N + M).

How does it compare with Rabin-Karp?

KMP is O(N + M) in the worst case with no randomness involved. Rabin-Karp matches that on average but degrades toward O(N*M) when hashes collide, while winning when you search for many patterns at once.