Naive String Matching and KMP

Analogy categoryAnalogies

Introduction

String matching asks: given a text of length n and a pattern of length m, find all positions where the pattern occurs inside the text. The naive approach tries every possible starting position and compares characters one by one, discarding all progress on a mismatch. The Knuth-Morris-Pratt (KMP) algorithm improves on this by precomputing information about the pattern itself so the search never re-examines a text character it has already matched, achieving linear time overall.

🏏

Cricket analogy: Finding every over in a season's log where a specific bowling pattern occurred, the naive way rechecks from scratch at every starting ball and discards progress on a mismatch, while KMP precomputes pattern structure so it never re-examines an over it already matched, like Virat Kohli precomputing a bowler's tendencies before facing them again.

Algorithm/Syntax

python

def naive_search(text: str, pattern: str) -> list[int]:
    n, m = len(text), len(pattern)
    matches = []
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            matches.append(i)
    return matches


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


def kmp_search(text: str, pattern: str) -> list[int]:
    n, m = len(text), len(pattern)
    if m == 0:
        return []
    lps = build_lps(pattern)
    matches = []
    i = j = 0
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == m:
                matches.append(i - j)
                j = lps[j - 1]
        elif j != 0:
            j = lps[j - 1]
        else:
            i += 1
    return matches

Explanation

The naive method restarts comparison from scratch at every shift, so a mismatch after k matched characters wastes all k comparisons. KMP avoids this by precomputing the Longest Proper Prefix which is also a Suffix (LPS) array for the pattern: lps[i] is the length of the longest prefix of pattern[0..i] that is also a suffix of it. During the search, on a mismatch at pattern index j, instead of resetting j to 0, KMP jumps to j = lps[j-1], because that many characters are already known to match (they form a prefix of the pattern that matched as a suffix of the text so far). This guarantees the text pointer i never moves backward, giving O(n+m) time: O(m) to build lps and O(n) for the scan.

🏏

Cricket analogy: The naive method restarts scanning the scorecard from scratch after every mismatched over, wasting all prior matched overs, while KMP's LPS table tells it, on a mismatch, exactly how many already-matched overs it can skip re-checking because they form a known repeating pattern, keeping the ball-by-ball pointer moving only forward.

Example

python

text = "ababcabababcabab"
pattern = "abab"

print("Naive:", naive_search(text, pattern))
print("LPS array:", build_lps(pattern))
print("KMP:  ", kmp_search(text, pattern))

# Trace of pattern "abab":
# index:   0 1 2 3
# char:    a b a b
# lps:     0 0 1 2
# lps[3]=2 because "ab" is both a prefix and suffix of "abab"

Complexity

Naive matching runs in O(n*m) worst case, e.g. text 'aaaa...a' and pattern 'aaa...ab', since every shift can re-compare almost the whole pattern. KMP runs in O(n+m): O(m) to build the LPS array with an amortized-linear two-pointer construction, and O(n) for the scan because the total number of successful matches plus lps-driven jumps is bounded by n. Space is O(m) for the LPS array in both approaches beyond the input itself.

🏏

Cricket analogy: Naive matching against a scorecard full of near-identical dot balls costs O(n*m) since every shift re-compares almost the whole bowling pattern, while KMP builds its LPS table in O(m) and scans in O(n) for O(n+m) total, using O(m) space for the LPS array beyond the scorecard itself.

Key Takeaways

Naive matching is O(n*m) worst case because it discards all prior comparison progress on a mismatch.
KMP precomputes the LPS (failure function) array in O(m) time to know how far to safely skip.
On a mismatch at pattern index j, KMP sets j = lps[j-1] instead of resetting to 0, and never moves the text pointer backward.
KMP guarantees O(n+m) worst-case time, making it ideal for large texts or repeated searches with the same pattern.

Practice what you learned

1. What is the worst-case time complexity of the naive string matching algorithm?

2. What does lps[i] represent in the KMP failure function?

3. When KMP encounters a mismatch at pattern index j (j != 0), what does it do?

4. What is the overall time complexity of the KMP algorithm including preprocessing?

5. For the pattern "aaaa", what is lps[3]?

Was this page helpful?

Rabin-Karp Algorithm

Topics covered

#Python#AlgorithmsStudyNotes#Algorithms#NaiveStringMatchingAndKMP#Naive#String#Matching#KMP#StudyNotes#SkillVeris