🎓 A1Learner
🔍

DSA KMP Pattern Matching

The Knuth-Morris-Pratt algorithm finds every occurrence of a pattern in a text while the text pointer only moves forward. Its prefix function records how much of the pattern stays matched after each mismatch.

The prefix table

Each table entry looks at the pattern prefix ending at that index. The entry for ababaca grows while the ab pattern repeats, then drops at the letter c.

def prefix_function(pattern):
    table = [0] * len(pattern)
    length = 0
    for i in range(1, len(pattern)):
        while length > 0 and pattern[i] != pattern[length]:
            length = table[length - 1]
        if pattern[i] == pattern[length]:
            length += 1
        table[i] = length
    return table


print("Pattern: ababaca")
print("Prefix table:", prefix_function("ababaca"))
print("Pattern: aabaab")
print("Prefix table:", prefix_function("aabaab"))

A mismatch falls back

The search below meets a wrong letter after matching ab. The table drops the matched length to a shorter prefix, and the same text letter is tried again.

def prefix_function(pattern):
    table = [0] * len(pattern)
    length = 0
    for i in range(1, len(pattern)):
        while length > 0 and pattern[i] != pattern[length]:
            length = table[length - 1]
        if pattern[i] == pattern[length]:
            length += 1
        table[i] = length
    return table


def find_first(text, pattern):
    table = prefix_function(pattern)
    matched = 0
    comparisons = 0
    for i in range(len(text)):
        while True:
            comparisons += 1
            if text[i] == pattern[matched]:
                matched += 1
                break
            if matched == 0:
                break
            matched = table[matched - 1]
        if matched == len(pattern):
            return i - len(pattern) + 1, comparisons
    return -1, comparisons


start, comparisons = find_first("abxababc", "ababc")
print("First match starts at:", start)
print("Comparisons used:", comparisons)

Overlaps survive

A full match also falls back through the table. The tail of one match can serve as the start of the next.

def prefix_function(pattern):
    table = [0] * len(pattern)
    length = 0
    for i in range(1, len(pattern)):
        while length > 0 and pattern[i] != pattern[length]:
            length = table[length - 1]
        if pattern[i] == pattern[length]:
            length += 1
        table[i] = length
    return table


def find_all(text, pattern):
    table = prefix_function(pattern)
    matched = 0
    found = []
    for i in range(len(text)):
        while matched > 0 and text[i] != pattern[matched]:
            matched = table[matched - 1]
        if text[i] == pattern[matched]:
            matched += 1
        if matched == len(pattern):
            found.append(i - len(pattern) + 1)
            matched = table[matched - 1]
    return found


print("Matches of aaa in aaaaa:", find_all("aaaaa", "aaa"))

Example

def prefix_function(pattern):
    table = [0] * len(pattern)
    length = 0
    for i in range(1, len(pattern)):
        while length > 0 and pattern[i] != pattern[length]:
            length = table[length - 1]
        if pattern[i] == pattern[length]:
            length += 1
        table[i] = length
    return table


def find_all_counted(text, pattern):
    table = prefix_function(pattern)
    matched = 0
    comparisons = 0
    found = []
    for i in range(len(text)):
        while True:
            comparisons += 1
            if text[i] == pattern[matched]:
                matched += 1
                break
            if matched == 0:
                break
            matched = table[matched - 1]
        if matched == len(pattern):
            found.append(i - len(pattern) + 1)
            matched = table[matched - 1]
    return found, comparisons


def find_all_naive(text, pattern):
    comparisons = 0
    found = []
    for start in range(len(text) - len(pattern) + 1):
        matched = 0
        while matched < len(pattern):
            comparisons += 1
            if text[start + matched] != pattern[matched]:
                break
            matched += 1
        if matched == len(pattern):
            found.append(start)
    return found, comparisons


text = "ababcabcababc"
pattern = "ababc"

print("Prefix table:", prefix_function(pattern))
matches, smart = find_all_counted(text, pattern)
plain_matches, plain = find_all_naive(text, pattern)
print("KMP matches:", matches)
print("Naive matches:", plain_matches)
print("KMP comparisons:", smart)
print("Naive comparisons:", plain)

Key points

  • Prefix function: for each pattern position, the length of the longest proper prefix that is also a suffix ending there
  • A proper prefix is a prefix that is not the whole string
  • On a mismatch, the matched length falls back through the table instead of restarting at zero
  • The text pointer never retreats, so the search makes one forward pass over the text
  • After a full match, the same fallback lets overlapping matches be found

In this example, the prefix table for ababc is printed first. Both searches report the same two match positions in the text. The counted comparisons separate them, because the naive search restarts at every position. KMP instead falls back through the table. It never rechecks a text letter against a prefix already ruled out.

Note

Building the table costs one pass over the pattern before the search starts

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

During a KMP search, the current text letter mismatches after four pattern letters matched. What happens next?