Faangprep Logo
LoginRegister
Browse Curriculum

KMP Algorithm

Visualize the Knuth-Morris-Pratt algorithm for efficient pattern searching using the LPS array.

KMP Algorithm
1. LPS Array Construction
-
0

A

-
1

B

-
2

A

-
3

B

-
4

C

-
5

A

-
6

B

-
7

A

-
8

B

2. Pattern Search
A
0
B
1
A
2
B
3
D
4
A
5
B
6
A
7
C
8
D
9
A
10
B
11
A
12
B
13
C
14
A
15
B
16
A
17
B
18
Controls

Ready

1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.
Unlock VisualizerPREMIUM FEATURE

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".

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep