Pattern matching answers a single question: where does a short string occur inside a longer one? Browsers run it for Ctrl+F. Genome tools run it across 3 billion base pairs of DNA. Intrusion-detection systems run it at line rate on every network packet that passes through. Naive scanning is O(n*m), and for the last two workloads that is too slow.

This chapter defines the problem, and lists the algorithms that solve it.

What Is Pattern Matching?

Given a text T of length n and a pattern P of length m (where m <= n), find all positions i in T where the substring T[i..i+m-1] equals P.

Terminology:

Text (T): the larger string being searched.
Pattern (P): the shorter string being looked for.
Match position: an index i in T where the pattern begins. For T = "ABCABCABC" and P = "ABC", the match positions are 0, 3, and 6.
Occurrence: each match position is one occurrence of P in T.

The pattern slides along the text. At each position, the characters are compared.

At position 3, every character of the pattern matches the corresponding character in the text. That is a match.

Where Pattern Matching Shows Up

A few representative workloads:

Text editors and IDEs: Ctrl+F and Find-and-Replace in VS Code, Vim, IntelliJ. Has to feel instant on million-line files.
Search engines: extracting keywords and structured fragments from billions of pages during indexing.
Bioinformatics: searching for gene sequences inside a 3.2 billion base-pair genome. O(n*m) is too slow at this scale.
Network security: deep packet inspection at wire speed (gigabits per second), matching every packet against known attack signatures.
Plagiarism detection: tools like Turnitin compare a document against a massive corpus by finding shared substrings.

The last three workloads are why the textbook algorithms matter. The first two work fine with naive search for typical inputs but benefit from better algorithms on large files.

The Problem

Given a text T of length n and a pattern P of length m, return all starting indices where P occurs in T.

Input:

Text T: a string of length n
Pattern P: a string of length m, where 1 <= m <= n

Output:

A list of integers representing each starting index i (0-indexed) where T[i..i+m-1] equals P

Single occurrence vs. all occurrences

Some problems ask only for the first occurrence (return -1 if not found). Others ask for all occurrences, or just a count. Every algorithm covered here handles all three variants with minor changes.

Approximate matching: positions where P matches with at most k mismatches or edits. Common in bioinformatics.
Wildcard matching: P contains ? (any single character) or * (any sequence).
Regular expressions: P is a regex. Harder problem; not covered here.

Function signature for the basic problem:

The Algorithm Landscape

The four algorithms covered in this course, plus two more worth knowing about:

Algorithm	Time (Worst)	Time (Average)	Space	Preprocessing	Best For
Brute Force	O(n * m)	O(n)	O(1)	None	Short patterns, simple cases
KMP (Knuth-Morris-Pratt)	O(n + m)	O(n + m)	O(m)	Failure function	Guaranteed linear time
Rabin-Karp	O(n * m)	O(n + m)	O(1)	Hash computation	Multiple pattern search
Z-Algorithm	O(n + m)	O(n + m)	O(n + m)	Z-array	Prefix-based problems

Brute force has no preprocessing. On short patterns or average-case inputs it does fine; on adversarial inputs it hits O(n*m).

KMP and Z-Algorithm guarantee O(n+m) in the worst case by preprocessing the pattern to avoid redundant comparisons. The O(m) preprocessing pays for itself on long texts.

Rabin-Karp's worst case matches brute force, but its expected case is O(n+m) and it can search for many patterns in a single pass over the text by hashing each pattern and looking up window hashes in a hash set.

Two algorithms not covered but worth knowing:

Boyer-Moore: scans the pattern right-to-left and uses two heuristics (bad-character and good-suffix) to skip ahead by up to m characters at a time. Sub-linear in the average case. This is what most production string search code actually uses, including grep, glibc's memmem, and JDK's modern String.indexOf for long patterns.
Aho-Corasick: extends a trie with failure links to search for many patterns at once in O(n + total pattern length + matches). Used in antivirus scanners, dictionary matchers, and fgrep -f. The multi-pattern extension of KMP.

This course focuses on Brute Force, KMP, Rabin-Karp, and Z-Algorithm because they are the algorithms most commonly tested in interviews and most commonly composed into other string problems.

When to Use Which

The flowchart below maps common situations to the right algorithm:

Brute Force: short patterns, non-adversarial text, or when pattern matching is a small step in a larger algorithm. The standard library implementation is good enough.
KMP: single pattern, need guaranteed O(n+m) worst case, possibly adversarial input.
Rabin-Karp: many patterns to search simultaneously, plagiarism or duplicate detection, problems where a rolling hash is useful for something else (e.g., longest duplicate substring).
Z-Algorithm: single pattern with a clean, short implementation; problems framed around prefix matches (string periods, longest happy prefix).
Boyer-Moore: production string search where the pattern is long and the alphabet is large. Almost never appears in interviews.
Aho-Corasick: many patterns of varying lengths searched in one pass. Used in malware scanning and fgrep -f.

Quiz

Introduction to Pattern Matching Quiz

10 quizzes