KMP Algorithm (LPS Table and Linear Search)

Knuth–Morris–Pratt (KMP) preprocesses the pattern to know how far to shift when a mismatch happens—avoiding naive re-scans. The LPS (longest proper prefix which is also suffix) array is the heart of the skip table.

Why this shows up in the real world

DNA motif search on huge genomes uses linear-time substring engines. IDE find-in-files engines combine Boyer–Moore-style skips with KMP-like fallbacks for pathological patterns.

Core idea (explained for students)

Build lps where lps[i] is longest len of prefix of pat[0:i+1] that is also a proper suffix. Match text with two pointers i on text, j on pattern; on mismatch j = lps[j-1] until j==0, then advance i.

Try this in Python

def compute_lps(pat: str) -> list[int]:
    m = len(pat)
    lps = [0] * m
    length = 0
    i = 1
    while i < m:
        if pat[i] == pat[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length:
            length = lps[length - 1]
        else:
            lps[i] = 0
            i += 1
    return lps


print(compute_lps("ababac"))

Common mistakes

• Off-by-one when j reaches m—report match index i - m + 1.
• Building LPS naively O(m³)—use the standard O(m) builder.

Key takeaways

• Start by mastering LPS construction on paper before coding full KMP.
• Compare with Rabin–Karp trade-offs (hash collisions vs guaranteed linear).