Problem Statement

KMP Algorithm

Here is the problem. You have a long piece of text and a shorter pattern, and you want to find every place where the pattern shows up inside the text. The slow way is to line the pattern up at position 0, check letter by letter, and if it fails, slide the pattern over by one and start the whole check again. KMP (Knuth-Morris-Pratt) is a faster way that never re-checks the same text letter twice. The trick is a small helper table called the LPS array. LPS stands for "longest proper prefix that is also a suffix." For each spot in the pattern, it records how much of the pattern start is repeated at that spot. A prefix is a chunk taken from the front, a suffix is a chunk taken from the end, and "proper" just means not the whole thing. Why does that help? When a mismatch happens partway through, the LPS table tells us how far the matched part already overlaps the pattern's own beginning, so we can jump the pattern forward to that overlap instead of starting over. The result is O(n+m) time, where n is the text length and m is the pattern length.

mediumStringPattern MatchingStringsTime: O(n + m) · Space: O(m)

Signals to notice

efficient pattern matchingfailure functionno text backtracking

Brute force first

Check each position — O(nm).

The key insight

KMP: precompute failure function (longest prefix-suffix). On mismatch, jump to failure[j-1]. O(n+m).

Trace it on `text="ABABDABACDABABCABAB", pattern="ABABCABAB"`

build_lps("ABABCABAB") -> lps=[0,0,1,2,0,1,2,3,4]
i=0..3 match A,B,A,B -> i=4,j=4 (matched prefix "ABAB")
i=4: text[4]='D' != pattern[4]='C', j>0 -> j=lps[3]=2
i=4: text[4]='D' != pattern[2]='A', j>0 -> j=lps[1]=0
i=4: text[4]='D' != pattern[0]='A', j==0 -> i=5
i=5..7 match A,B,A -> i=8,j=3; text[8]='C' != pattern[3]='B' -> j=lps[2]=1, then 'C'!=pattern[1]='B' -> j=lps[0]=0, then 'C'!=pattern[0]='A',j==0 -> i=9; text[9]='D'!=pattern[0]='A' -> i=10
i=10..18 match all 9 chars of "ABABCABAB" -> i=19,j=9
j==9==len(pattern) -> results.append(i-j)=append(19-9)=10; j=lps[8]=4
i==19 not < 19 -> loop ends; return results=[10]  (Found at index 10)

What must stay true

Failure function tells you how far back to jump in the pattern without re-examining text characters. Text pointer never moves backward.

Shape of the loop

lps = buildLPS(pattern)            # longest proper prefix==suffix per position
i = j = 0                          # i scans text, j scans pattern
results = []
while i < len(text):
    if text[i] == pattern[j]:      # chars match -> advance both
        i += 1; j += 1
    if j == len(pattern):          # full pattern matched
        results.append(i - j)      # record start index
        j = lps[j - 1]             # shift to look for overlapping matches
    elif i < len(text) and text[i] != pattern[j]:
        if j > 0: j = lps[j - 1]   # fall back in pattern, text pointer stays
        else:     i += 1           # no prefix to reuse, advance text
return results

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not understanding failure function construction — it's self-matching of the pattern.

Strings Pattern