DSA String Matching

String matching means finding where a short piece of text, called the pattern, appears inside a longer text. Every "Find" box in a document or browser performs this task. Fast matching matters when the text holds millions of characters.

Imagine searching a thick book for the word "ocean". You can compare the word at every starting letter on every page. A smarter reader remembers which letters already matched and avoids repeating that effort. The methods below follow those two styles.

Naive Matching

The simple method slides the pattern along the text one position at a time. At each position, it compares letters from left to right.

def naive_search(text, pattern):
    matches = []
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):
        if text[i:i + m] == pattern:
            matches.append(i)
    return matches

print(naive_search("ABABABC", "ABC"))   # [4]

Text:    A B A B A B C
Try 0:   A B C   -> mismatch at 3rd letter
Try 1:     A B C -> mismatch at 1st letter
Try 2:       A B C -> mismatch at 3rd letter
Try 3:         A B C -> mismatch at 1st letter
Try 4:           A B C -> full match at index 4

The naive method costs O(n × m) time in the worst case, since each position may compare many letters before failing.

The Smarter Idea: KMP

The Knuth-Morris-Pratt algorithm, called KMP, avoids repeating comparisons. When a mismatch occurs, the algorithm uses what it already learned about the pattern to skip ahead. The text pointer never moves backward.

The LPS Table

KMP prepares a table called LPS, short for longest proper prefix that doubles as a suffix. For each position in the pattern, the table stores the length of the longest beginning piece that matches the ending piece. A proper prefix excludes the whole string.

Pattern: A B A B C

Index:   0  1  2  3  4
Letter:  A  B  A  B  C
LPS:     0  0  1  2  0

At index 3, "AB" is both a prefix and a suffix of "ABAB", so LPS = 2.

def build_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 1
    while i < len(pattern):
        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

print(build_lps("ABABC"))   # [0, 0, 1, 2, 0]

The KMP Search

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

print(kmp_search("ABABABC", "ABABC"))   # [2]

Text:    A B A B A B C
Pattern: A B A B C       matches 4 letters, C vs A fails

LPS says the last "AB" of the match can still start a new match.
Slide the pattern so its first 2 letters line up with text index 2-3:

Text:    A B A B A B C
Pattern:     A B A B C   full match at index 2

The pattern jumps forward and skips letters that already matched. Total time drops to O(n + m).

Rolling Hash Idea

Another approach, Rabin-Karp, assigns each window of text a numeric fingerprint called a hash. Windows with a different hash cannot match, so the program skips them without comparing letters. Sliding the window updates the hash in constant time. Matching hashes trigger a final letter-by-letter check to rule out accidental clashes. Rabin-Karp shines when searching for many patterns at once.

Choosing a Method

• Python's built-in find suits everyday work, since the language already optimizes it.
• Naive matching suits short texts and small patterns.
• KMP suits long texts and guarantees linear time.
• Rabin-Karp suits multiple pattern searches.

Real-Life Uses

Text editors highlight every match of a searched word. Antivirus scanners look for known byte patterns inside files. Biology tools search DNA strings for short gene markers. Plagiarism checkers find copied phrases inside long documents.

Practice Ideas

Write the LPS table by hand for the patterns "AAAA", "ABCABC", and "AABAA". Run the code to confirm each table. Search for the pattern "ANA" inside the text "BANANA" and note that overlapping matches appear at indexes 1 and 3. Overlap handling shows why KMP resets j through the LPS table after a full match.

Common Mistakes

Confusing the LPS table with the pattern itself causes bad jumps. Forgetting to reset j after a full match skips overlapping matches. Using slicing in the naive loop copies characters and hides extra cost. Test patterns with repeated letters, like "AAAA", to expose these issues.

Complexity Summary

• Naive: O(n × m) time, O(1) space.
• KMP: O(n + m) time, O(m) space for the LPS table.
• Rabin-Karp: O(n + m) on average, O(n × m) in rare worst cases.

Key Points

• String matching finds a pattern inside a longer text.
• Naive matching compares at every position and may repeat work.
• KMP uses the LPS table to skip repeated comparisons.
• The text pointer in KMP never moves backward.
• Rabin-Karp compares fingerprints before comparing letters.