DSA Tracker

Visualize

Find the Index of the First Occurrence in a String (Pattern Matching)

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

time O(n + m)space O(m)

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.

Details

Animated on: text = "abababc", pat = "ababc" — find the first index where the pattern occurs, without re-reading any text character.

Problem:Find the Index of the First Occurrence in a String (Pattern Matching)Easy

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

step 1 / 14

a
[0]
b
[1]
a
[2]
b
[3]
c
[4]

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.

  • i=1· arr[1] = b
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

Every step in words

Show all 14 steps
  1. 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.
  2. pat[1]='b' does not match pat[0]='a' and no shorter border is left to fall back to, so position 1 ends no repeated prefix at all: lps[1] = 0.
  3. pat[2]='a' equals pat[0]='a', so the border grows by one: "a" is both a prefix and the suffix ending at 2. lps[2] = 1, and lps is now [0, 0, 1, 0, 0].
  4. pat[3]='b' equals pat[1]='b', so the border grows by one: "ab" is both a prefix and the suffix ending at 3. lps[3] = 2, and lps is now [0, 0, 1, 2, 0].
  5. pat[4]='c' does not match pat[2]='a', so a border of length 2 cannot be extended. Rather than restart, fall back to that border's own border lps[1]=0 — every shorter candidate in between has already been ruled out.
  6. pat[4]='c' does not match pat[0]='a' and no shorter border is left to fall back to, so position 4 ends no repeated prefix at all: lps[4] = 0.
  7. text[0]='a' matches pat[0]='a', so 1 of 5 characters now line up from text index 0. Both cursors advance to compare text[1]='b' against pat[1]='b'.
  8. text[1]='b' matches pat[1]='b', so 2 of 5 characters now line up from text index 0. Both cursors advance to compare text[2]='a' against pat[2]='a'.
  9. text[2]='a' matches pat[2]='a', so 3 of 5 characters now line up from text index 0. Both cursors advance to compare text[3]='b' against pat[3]='b'.
  10. text[3]='b' matches pat[3]='b', so 4 of 5 characters now line up from text index 0. Both cursors advance to compare text[4]='a' against pat[4]='c'.
  11. text[4]='a' does not match pat[4]='c'. The last 4 characters matched were "abab", and lps[3]=2 says its first 2 characters are already re-matched, so j drops to 2 while i stays at 4 — the text is never re-read.
  12. text[4]='a' matches pat[2]='a', so 3 of 5 characters now line up from text index 2. Both cursors advance to compare text[5]='b' against pat[3]='b'.
  13. text[5]='b' matches pat[3]='b', so 4 of 5 characters now line up from text index 2. Both cursors advance to compare text[6]='c' against pat[4]='c'.
  14. text[6]='c' matches the last character of the pattern, so all 5 characters line up starting at text index 2. Return 2.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Find the Index of the First Occurrence in a String (Pattern Matching) in the editorAll Strings problemsBack to roadmap