String Matching

Exact string matching asks where a pattern occurs in a longer text. The baseline compares characters at every alignment. Faster algorithms avoid repeating comparisons by remembering different information: Rabin–Karp remembers a rolling numeric fingerprint, KMP remembers the pattern’s prefix-suffix structure, and finite-automaton matching precomputes every state transition.

Matching Model

Let text T have length n, pattern P length m, and alphabet Sigma. A match at shift s satisfies:

Valid shifts are 0 <= s <= n-m. The interface must define edge cases:

• the empty pattern mathematically matches every boundary, but an API may report all boundaries or only the first;
• a pattern longer than the text has no match;
• overlapping matches may or may not all be reported;
• C strings cannot represent embedded zero bytes with strlen, so binary data requires explicit lengths;
• character equality may compare raw bytes, Unicode code points, normalized text, or locale-aware units—different problems with different preprocessing.

This chapter uses non-null C byte strings, strlen-derived lengths, exact byte equality, and zero-based indices. Each algorithm reports every overlapping occurrence of a nonempty pattern. By interface policy, an empty pattern is reported once at index 0.

Naive Matching

Naive matching tests every valid alignment and compares from the pattern’s first byte until a mismatch or a complete match.

#include <stdio.h>
#include <string.h>

void naive_search(const char *text, const char *pattern) {
    size_t n = strlen(text);
    size_t m = strlen(pattern);
    if (m == 0U) {
        printf("Match found at index 0\n");
        return;
    }
    if (m > n) {
        return;
    }

    for (size_t i = 0; i <= n - m; i++) {
        size_t j = 0U;
        while (j < m && text[i + j] == pattern[j]) {
            j++;
        }
        if (j == m) {
            printf("Match found at index %zu\n", i);
        }
    }
}

If most alignments fail on their first byte, the scan uses Theta(n) comparisons. Searching for "aaaaaaaaab" in a long all-a text compares nearly all m pattern bytes at each of n-m+1 alignments, giving Theta(nm) worst-case time. Repetitive data makes this behavior relevant in DNA, logs, and generated text.

Correctness follows directly from exhaustive alignment. The outer loop visits every valid shift exactly once. At one shift, the inner loop either finds a mismatching position, proving that shift is not a match, or reaches j==m, proving all required equalities. No invalid shift is inspected because i <= n-m keeps the final access within text[n-1]. Reporting is therefore sound and complete, including overlaps because the next outer iteration advances by only one.

The worst case repeatedly matches almost the entire pattern before failing. It resembles adversarial quicksort partitions or a search tree degraded by insertion order: an input preserves enough apparent structure to maximize wasted work. Rabin–Karp and KMP retain information across alignments so those comparisons need not all be repeated.

Rabin-Karp

Rabin–Karp compares a numeric hash of the pattern with a hash of each text window. Different hashes prove the strings differ. Equal hashes are only candidates because distinct strings can collide, so a byte comparison must verify every hash hit.

Interpret an m-byte window as a base-256 polynomial modulo a prime. When the window moves one position, subtract the outgoing byte’s highest-order contribution, multiply by the base, and add the incoming byte. This rolling hash update takes constant time.

For byte values $x_0,\ldots,x_{m-1}$, define

Let h=B^(m-1) mod q. Moving from text window at shift s to shift s+1 gives

The outgoing highest-order term is removed, multiplication shifts every remaining term one power higher, and the incoming byte fills the constant term. Modular arithmetic preserves this polynomial identity. It does not preserve uniqueness: equality of residues is a necessary filter, while memcmp establishes exact equality.

#include <stdint.h>
#include <stdio.h>
#include <string.h>

#define BASE UINT64_C(256)
#define MODULUS UINT64_C(1000000007)

void rabin_karp_search(const char *text, const char *pattern) {
    size_t n = strlen(text);
    size_t m = strlen(pattern);
    if (m == 0U) {
        printf("Match found at index 0\n");
        return;
    }
    if (m > n) {
        return;
    }

    uint64_t high_order = 1U;
    for (size_t i = 1; i < m; i++) {
        high_order = (high_order * BASE) % MODULUS;
    }

    uint64_t pattern_hash = 0U;
    uint64_t window_hash = 0U;
    for (size_t i = 0; i < m; i++) {
        uint64_t pattern_byte = (unsigned char) pattern[i];
        uint64_t text_byte = (unsigned char) text[i];
        pattern_hash = (pattern_hash * BASE + pattern_byte) % MODULUS;
        window_hash = (window_hash * BASE + text_byte) % MODULUS;
    }

    for (size_t i = 0; i <= n - m; i++) {
        if (pattern_hash == window_hash && memcmp(text + i, pattern, m) == 0) {
            printf("Match found at index %zu\n", i);
        }
        if (i < n - m) {
            uint64_t outgoing = (unsigned char) text[i];
            uint64_t incoming = (unsigned char) text[i + m];
            uint64_t contribution = (outgoing * high_order) % MODULUS;
            window_hash = (window_hash + MODULUS - contribution) % MODULUS;
            window_hash = (window_hash * BASE + incoming) % MODULUS;
        }
    }
}

Preprocessing and rolling cost Theta(n+m). If v windows have the same hash as the pattern, verification adds O(vm), so the deterministic worst case is Theta(nm). Expected linear time requires an explicit probabilistic model, such as selecting a hash function independently at random from a suitable universal family or assuming inputs independent of a well-distributed hash. A fixed public modulus alone does not provide that guarantee against adversarial input.

All hashed bytes are converted through unsigned char. With the chosen constants, every product is below 256 * MODULUS, which fits in uint64_t. Adding MODULUS before subtracting the outgoing contribution keeps unsigned modular subtraction in the intended range.

For many equal-length patterns, hash each pattern once and index candidates by hash. One rolling pass over the text then probes that index and verifies only candidate strings. Patterns of different lengths need separate window lengths or a different multi-pattern structure such as Aho–Corasick.

KMP

The Knuth–Morris–Pratt algorithm (KMP) guarantees Theta(n+m) worst-case time without hashing. It never moves the text index backward. A mismatch may compare the current text byte with several pattern positions, but previously matched prefix-suffix structure determines those positions without restarting the text scan.

Suppose "ABAB" of pattern "ABABC" has matched before a mismatch. A suffix of the confirmed text may already equal a prefix of the pattern. KMP shifts to the longest such prefix rather than discarding all progress.

This shift depends only on the pattern. The failure function, also called the prefix function, stores at failure[i] the length of the longest proper prefix of the pattern that is also a suffix of pattern[0..i].

#include <stddef.h>

void build_failure_table(const char *pattern, size_t m, size_t failure[]) {
    failure[0] = 0U;
    size_t matched = 0U;

    for (size_t i = 1; i < m; i++) {
        while (matched > 0U && pattern[i] != pattern[matched]) {
            matched = failure[matched - 1U];
        }
        if (pattern[i] == pattern[matched]) {
            matched++;
        }
        failure[i] = matched;
    }
}

The helper requires m > 0 and arrays of at least m elements. The assignment matched = failure[matched - 1] reuses an already-computed border length to test the next shorter candidate. Across the complete construction, matched increases at most m - 1 times. Every fallback decreases it and can be charged to an earlier increase, so all executions of the inner while total O(m). This is the same aggregate argument used for dynamic-array growth in the Complexity chapter.

With the failure table built, the search itself becomes a single pass over the text that never backs up:

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void kmp_search(const char *text, const char *pattern) {
    size_t n = strlen(text);
    size_t m = strlen(pattern);
    if (m == 0U) {
        printf("Match found at index 0\n");
        return;
    }
    if (m > n || m > SIZE_MAX / sizeof(size_t)) {
        return;
    }

    size_t *failure = malloc(m * sizeof(*failure));
    if (failure == NULL) {
        return;
    }
    build_failure_table(pattern, m, failure);

    size_t matched = 0U;
    for (size_t i = 0; i < n; i++) {
        while (matched > 0U && text[i] != pattern[matched]) {
            matched = failure[matched - 1U];
        }
        if (text[i] == pattern[matched]) {
            matched++;
        }
        if (matched == m) {
            printf("Match found at index %zu\n", i - m + 1U);
            matched = failure[matched - 1U];
        }
    }

    free(failure);
}

The outer index advances exactly n times. matched increases at most once per outer iteration, and every fallback decreases it, so total fallbacks are O(n). Failure-table construction is Theta(m), giving deterministic Theta(n+m) time. On repetitive inputs such as an all-a text with pattern "aaaab", KMP may compare one text byte against several pattern positions, but aggregate fallback work remains linear.

KMP Invariant

Immediately before processing text[i], matched is the length of the longest pattern prefix that equals a suffix of text[0..i). Suppose the next byte mismatches pattern[matched]. Any shorter candidate that could still end at the current text boundary must be both a suffix of the already matched prefix and a prefix of the pattern. failure[matched-1] is the longest such candidate; repeatedly following failure links tests all possible borders from longest to shortest without losing a valid one.

When the byte matches, extending both suffix and prefix increases matched by one and preserves the invariant for text[0..i+1). When matched==m, the last m text bytes equal the whole pattern, so reporting i-m+1 is sound. Resetting to failure[m-1] keeps the longest proper border of that match, which is exactly the state needed to find an overlapping occurrence.

Completeness follows from the same invariant. If a match ends at i, the whole pattern is a suffix of text[0..i+1), so the longest matching prefix has length at least m and the algorithm reaches the reporting state. Since no prefix is longer than the pattern, it reaches exactly m.

For pattern "ABABCABAB", the failure table is [0,0,1,2,0,1,2,3,4]. Tracing it against "ABABCABABABABCABAB" shows that i only increases, while matched falls back through earlier table values when needed.

Finite Automata

Finite-automaton matching makes the current match length an explicit state. State q means the longest pattern prefix matching a suffix of the text read so far has length q. A deterministic transition table gives the next state for every current state and byte, so scanning uses one table lookup per text byte.

The DFA has m + 1 states. State m means a complete match. For state q and byte c, delta[q,c] is the longest pattern prefix that is a suffix of pattern[0..q) + c.

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALPHABET_SIZE 256U

void build_failure_table(const char *pattern, size_t m, size_t failure[]);

bool build_transition(const char *pattern, size_t m, size_t **out) {
    if (pattern == NULL || out == NULL || m == SIZE_MAX) {
        return false;
    }
    size_t states = m + 1U;
    if (states > SIZE_MAX / ALPHABET_SIZE) {
        return false;
    }
    size_t entries = states * ALPHABET_SIZE;
    if (entries > SIZE_MAX / sizeof(size_t)) {
        return false;
    }
    size_t *delta = malloc(entries * sizeof(*delta));
    if (delta == NULL) {
        return false;
    }
    size_t *failure = NULL;
    if (m > 0U) {
        if (m > SIZE_MAX / sizeof(*failure)) {
            free(delta);
            return false;
        }
        failure = malloc(m * sizeof(*failure));
        if (failure == NULL) {
            free(delta);
            return false;
        }
        build_failure_table(pattern, m, failure);
    }

#define DELTA(q, c) delta[(q) * ALPHABET_SIZE + (c)]
    for (size_t c = 0; c < ALPHABET_SIZE; c++) {
        DELTA(0U, c) = (m > 0U && (unsigned char) pattern[0] == c) ? 1U : 0U;
    }
    for (size_t q = 1; q <= m; q++) {
        for (size_t c = 0; c < ALPHABET_SIZE; c++) {
            if (q < m && (unsigned char) pattern[q] == c) {
                DELTA(q, c) = q + 1U;
            } else {
                DELTA(q, c) = DELTA(failure[q - 1U], c);
            }
        }
    }
    free(failure);
    *out = delta;
#undef DELTA
    return true;
}

bool automaton_search(const char *text, const char *pattern) {
    if (text == NULL || pattern == NULL) {
        return false;
    }
    size_t m = strlen(pattern);
    size_t n = strlen(text);
    if (m == 0U) {
        printf("Match found at index 0\n");
        return true;
    }
    size_t *delta = NULL;
    if (!build_transition(pattern, m, &delta)) {
        return false;
    }

    size_t q = 0U;
    for (size_t i = 0; i < n; i++) {
        unsigned char byte = (unsigned char) text[i];
        q = delta[q * ALPHABET_SIZE + byte];
        if (q == m) {
            printf("Match found at index %zu\n", i - m + 1U);
        }
    }
    free(delta);
    return true;
}

build_transition first builds KMP failure values, then reuses the transition from the failure state whenever a byte does not extend state q. Construction takes Theta(m |Sigma|) time and space; each text scan takes Theta(n) time. KMP and the DFA encode the same prefix-suffix structure at different preprocessing and memory points. An API intended to reuse one pattern should return the table separately rather than rebuild it inside every search.

Shared Trace

Use text T="ABABABAC" and pattern P="ABABAC". The only match begins at shift 2. Running every method on the same pair reveals exactly what each one remembers.

Naive alignments. At shift 0, the first five bytes match and T[5]='B' fails against P[5]='C', costing six comparisons. Shift 1 fails immediately on 'B' versus 'A'. Shift 2 matches all six bytes. Total: thirteen byte comparisons, including a repeated comparison of structure already confirmed at shift 0.

Rolling hash. For a hand-sized trace, encode A=1, B=2, C=3, use base 5, and reduce modulo 101. The production code uses different constants, but the recurrence is identical. The pattern hash is 13; the three window hashes are:

Here 5^5 mod 101 = 95. The first roll removes outgoing A and adds incoming A:

The next roll removes B and adds C, producing 13. A collision would add a failed verification but never a false reported match.

KMP fallback. The failure table for ABABAC is [0,0,1,2,3,0]. Text positions 0..4 advance matched from 0 to 5. At position 5, 'B' mismatches expected 'C'; KMP falls back to failure[4]=3, where the same text byte matches pattern position 3, leaving matched=4 without moving the text index backward. Positions 6 and 7 then advance to 6, reporting shift 7-6+1=2.

Automaton states. The DFA follows states

0 --A--> 1 --B--> 2 --A--> 3 --B--> 4 --A--> 5
5 --B--> 4 --A--> 5 --C--> 6

State 6 reports the match. Its transition 5 --B--> 4 precomputes the same fallback KMP performs at run time. The naive method stores no cross-alignment state, Rabin–Karp stores a window fingerprint, KMP stores border lengths, and the DFA stores every next-state decision.

Multiple Patterns

Searching separately for k patterns repeats text scanning. Aho–Corasick combines a trie with KMP-like failure links so a fixed pattern collection can be matched in one pass.

1. Insert every pattern into a trie. A state represents a pattern prefix.
2. Mark terminal states with the patterns ending there.
3. In breadth-first order, give each state a failure link to the longest proper suffix of its trie string that is also a trie prefix.
4. Inherit outputs from the failure state, because one text suffix can complete several patterns.
5. Scan the text by following trie edges; on a missing edge, follow failure links until a transition exists or the root is reached.

For patterns he, she, his, and hers in text ushers, reading the prefix ush reaches state sh. The next e completes she; that state’s failure suffix is he, so both she at index 1 and he at index 2 are reported. Continuing through r,s completes hers at index 2 without restarting from that position.

The invariant matches the DFA model: after each text symbol, the current state is the longest trie prefix that is also a suffix of text read so far. Failure links enumerate shorter candidate suffixes without backing up the text. With suitable constant-time transitions, construction is linear in total pattern length plus transition representation, and searching costs Theta(n+z), where z is the number of reported matches. Sparse maps save memory for large alphabets but make transition cost depend on the map implementation.

Rabin–Karp remains attractive for many equal-length patterns when a compact hash index is sufficient and collisions are verified. Aho–Corasick gives a deterministic structural solution for mixed lengths and overlapping outputs at the cost of a larger automaton.

Symbol Streams

The algorithms operate on sequences of symbols; an application must decide what one symbol means. For binary records, pass explicit byte lengths because strlen stops at a zero byte. For UTF-8 text, exact byte matching correctly finds an identical encoded byte sequence, but a user-perceived character can occupy several bytes.

If matching should treat canonically equivalent Unicode spellings as equal, normalize both text and pattern to the same form before searching. If matching is by code point, decode first and run the algorithm on code points. If matching is by grapheme cluster, segment first. Case folding can change sequence length, so a match position in the transformed stream may need a mapping back to original byte offsets.

These transformations affect contracts and indices but not the core proofs: naive search, rolling hashes, KMP borders, and automaton states remain valid over any consistently represented finite symbol sequence. Hash arithmetic and transition storage must then support the chosen alphabet rather than assuming 256 byte values.

Reporting Matches

Printing inside a matcher fixes output format, hides I/O failure, and prevents a caller from stopping after the first match. A callback separates matching from result handling and explicit lengths support binary data:

#include <stdbool.h>
#include <stddef.h>

typedef bool (*MatchCallback)(size_t index, void *context);

typedef enum {
    MATCH_OK,
    MATCH_INVALID,
    MATCH_CANCELLED
} MatchStatus;

MatchStatus naive_find_all(const unsigned char text[], size_t n,
                           const unsigned char pattern[], size_t m,
                           MatchCallback report, void *context) {
    if (report == NULL || (n > 0U && text == NULL) ||
        (m > 0U && pattern == NULL)) {
        return MATCH_INVALID;
    }
    if (m == 0U) {
        return report(0U, context) ? MATCH_OK : MATCH_CANCELLED;
    }
    if (m > n) {
        return MATCH_OK;
    }

    for (size_t shift = 0U; shift <= n - m; shift++) {
        size_t matched = 0U;
        while (matched < m &&
               text[shift + matched] == pattern[matched]) {
            matched++;
        }
        if (matched == m && !report(shift, context)) {
            return MATCH_CANCELLED;
        }
    }
    return MATCH_OK;
}

The same callback contract can wrap Rabin–Karp, KMP, DFA, and Aho–Corasick scans. A caller may append indices to a checked vector, count matches, stream them elsewhere, or return false after the first. Algorithms that allocate preprocessing state add allocation-failure statuses. Unless strong failure atomicity is promised, callbacks invoked before a later failure remain observable.

Choosing a Matcher

Naive matching remembers nothing between alignments. Rabin–Karp retains a hash summary and verifies possible collisions. KMP retains the pattern’s exact prefix-suffix structure and obtains a deterministic linear bound. Finite-automaton matching materializes all next-state decisions. These are different preprocessing and memory choices for eliminating repeated work.

Complexity Comparison

Every algorithm must inspect enough input to report matches, so Omega(n+m) is the natural worst-case target for one pattern and one text under direct access. Outputting z match positions adds Omega(z).

Matching Failures

• Calling strlen repeatedly inside a search loop and accidentally adding an extra linear factor.
• Failing to verify equal Rabin–Karp hashes and reporting collisions as matches.
• Using signed char directly as a transition-table index; cast to unsigned char.
• Letting modular subtraction stay negative in C.
• Building the KMP failure table with an off-by-one definition inconsistent with the search routine.
• Forgetting to fall back after a full KMP match when overlapping matches are required.
• Treating Unicode bytes as characters or comparing differently normalized strings.
• Allocating a full alphabet transition table for a huge alphabet without sparse transitions.
• Leaving empty-pattern behavior undefined.

Matching Review

• Exact matching compares a length-m pattern at shifts within a length-n text.
• Naive matching performs no preprocessing and can repeat nearly all comparisons at adjacent shifts.
• Rabin–Karp updates a rolling hash in constant time per shift and verifies collisions.
• KMP’s failure function records the longest reusable proper prefix after a mismatch and guarantees Theta(n+m) time.
• A finite automaton makes match length explicit as state and trades larger preprocessing space for one transition per text byte.
• Aho–Corasick extends failure links to a trie and reports a fixed pattern collection in one text pass.
• Preprocessing cost, pattern reuse, alphabet size, worst-case guarantees, collision policy, and text representation determine the appropriate method.

Matching Problems

Alignment Traces

1. Trace every naive alignment for text AAAAAAAAB and pattern AAAAB. Count successful and failed byte comparisons separately.
2. Repeat the chapter’s common trace for text ABABABAC and pattern ABABAC, recording naive comparisons, rolling hashes, KMP states, and DFA states in one table.
3. Find every overlapping occurrence of AAA in AAAAA. Show the KMP fallback after each complete match and the automaton state that permits overlap.
4. Define and test empty-pattern, pattern-longer-than-text, embedded-zero, and non-overlapping-report policies as separate API contracts.

Border Tables

5. Build failure tables for AABAACAABAA, ABABAC, and AAAAA. At every fallback, name the border being replaced by its next shorter border.
6. Prove failure-table construction is linear by charging every decrement of matched to an earlier increment.
7. Given only a failure table and its pattern length, determine which prefix lengths are also suffixes of the complete pattern by following failure links.
8. Implement the Z-function and derive pattern matching on pattern + separator + text. Compare Z values with KMP failure values on the same pattern.

Hash Engineering

9. Derive the rolling update algebra from the base-polynomial definition, including modular subtraction of the outgoing highest-order byte.
10. Construct a collision under a deliberately small modulus and verify that byte comparison prevents a false match.
11. Implement a randomized double-hash matcher with an explicit seed/source contract. Quantify collision probability under its stated model without calling it zero.
12. Extend rolling hashes to two-dimensional rectangular matching by first hashing row windows and then rolling those hashes vertically. State preprocessing, update, and verification costs.

Matcher Implementations

13. Replace printed output in all chapter matchers with a callback that can stop early. Distinguish successful completion, callback cancellation, allocation failure, and invalid input.
14. Convert all matchers to explicit byte spans (pointer,length) so embedded zeros are searchable. Keep empty-pattern behavior consistent.
15. Build a reusable compiled-KMP object containing pattern bytes and its failure table. Search many texts without rebuilding and define ownership cleanup.
16. Store DFA transitions sparsely for a large alphabet. Compare sorted edge arrays, hash maps, and default failure transitions.

Pattern Collections

17. Build the Aho–Corasick trie, failure links, and output sets for he, she, his, and hers. Trace ushers and report exact start indices.
18. Compare one Aho–Corasick scan with k separate KMP scans and grouped-length Rabin–Karp in terms of total pattern length, text length, alphabet, memory, and output count.
19. Design dynamic pattern insertion. Identify which failure links may become invalid and why a fully dynamic automaton is harder than adding a trie leaf.

Adversarial Matchers

20. Instrument naive, Rabin–Karp, and KMP character or hash work on random, periodic, and almost-matching inputs. Separate deterministic counts from assumptions about generated data.
21. Prove a one-pattern matcher cannot run in o(n+m+z) time when it must read arbitrary input and emit z positions.
22. Design a normalization-aware Unicode matching pipeline that returns original UTF-8 byte ranges. State how transformed positions map back when normalization or case folding changes length.
23. Derive the bad-character shift used by Boyer–Moore–Horspool and construct an input on which it skips many alignments and another on which it performs poorly. Compare its retained information with KMP’s borders.