Pattern visualizer

KMP Algorithm (Pattern Matching)

Brute force restarts the pattern at the next text position after every mismatch, re-reading characters it already compared. KMP removes that waste by asking one question about the pattern alone: after matching k characters and failing, how much of that matched run is itself a prefix of the pattern? That number is the LPS table, built once in the first phase. In the second phase a mismatch never moves the text cursor — only the pattern cursor slides back to the length the table names, so each text character is read exactly once. Animated on: text = "abababc", pat = "ababc" — find the first index where the pattern occurs, without re-reading any text character..

Precompute the pattern's borders, then scan the text without ever going back

time O(n + m)space O(m)step 1 / 14

[0]

[1]

[2]

[3]

[4]

line 2

Pattern "ababc". Before searching, KMP measures the pattern against itself: lps[k] is the length of the longest prefix of "ababc" that also ends at k. lps[0] is always 0 because a whole prefix does not count as its own border.

Pseudocode

1FUNCTION KMP(text, pat):
2  lps <- BUILD_LPS(pat)
3  i <- 0
4  j <- 0
5  WHILE i < LENGTH(text):
6    IF text[i] = pat[j]:
7      i <- i + 1
8      j <- j + 1
9      IF j = LENGTH(pat): RETURN i - j
10    ELSE IF j > 0: j <- lps[j - 1]
11    ELSE: i <- i + 1
12  RETURN -1

← / → step · space play · Home restart

Where to practice Strings

Practice Strings problems All Strings problems Back to roadmap