String Matching

String matching asks where a pattern appears inside a larger text.

The simplest solution checks every possible starting position.

Core Idea

Given text T and pattern P, the algorithm compares P with each substring of T of the same length. More advanced algorithms avoid repeating comparisons by using information about the pattern or substring hashes.

The naive version has worst-case time complexity O(n * m) for text length n and pattern length m.

Python Example

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

This uses slicing for clarity.

Common Confusions

String matching is not only about exact search in English words. It also appears in arrays, token streams, DNA sequences, and repeated pattern problems.

Python’s in and .find() are useful built-ins, but algorithm study focuses on how matching can be done efficiently.

When To Use It

Use string matching when the problem asks whether a pattern occurs, where it occurs, how often it occurs, or how repeated structure appears in a sequence.