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.

Function Contract

find_pattern(text, pattern) expects two strings.

It returns a list of every starting index where pattern appears in text, including overlapping matches. If the pattern does not appear, it returns an empty list.

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.

Step-by-Step Example

For text "ababa" and pattern "aba", the possible starting positions are 0, 1, and 2:

start 0: aba matches
start 1: bab does not match
start 2: aba matches

The matches are at positions 0 and 2.

Why Naive Matching Repeats Work

If a mismatch happens after several matching characters, naive matching moves only one start position and may compare many of the same characters again.

Algorithms such as KMP and rolling hash reduce that repeated comparison in different ways.

Complexity

The simple slicing version may create substrings, so it can hide extra work. Conceptually, naive matching checks up to m characters at each of about n positions, giving O(nm) worst-case time.

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.

Another common mistake is forgetting overlapping matches. In "aaaa", pattern "aa" occurs at positions 0, 1, and 2.

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.

For one small search, built-ins are usually enough. Study algorithms when input size or repeated searches matter.

The Main Point

String matching asks where a pattern appears, and the key distinction is whether repeated comparisons can be avoided.