DSA Strings

String Mastery

Naive search is correct; O(nm) over a 10⁸-byte log is not. Dual conflict: you need every match of a pattern without quadratic backtracking on every shift.

KMP uses a and . Rabin–Karp uses a . Many patterns call for . Always mind .

Algorithm journey

Name the need

One pattern, many patterns, or repeated substring queries?

Fix the text unit

Bytes, code points, or graphemes?

Pick the engine

KMP/Z, rolling hash, Aho–Corasick, suffix index.

Test adversarial text

Periodic patterns, overlaps, hash collisions.

What actually happens

Naive idea: for each text position, compare the pattern. Correct. On periodic patterns it can approach Θ(nm) character comparisons.

Better idea: preprocess the pattern. KMP never rewinds the text: the prefix function says how far to fall back. Rolling hashes compare windows in O(1) then verify. Multi-pattern builds one automaton.

The improved design still fails on wrong index units (UTF-16 vs code points), unverified hash collisions, empty-pattern edge cases, or treating output size as free.

Invariant (KMP)

Before processing text[i], pattern[0..j) equals the suffix of the text processed so far. Fallbacks via π preserve that matched prefix property while decreasing j, so total work stays O(n + m).

How to choose a string algorithm

1. One exact pattern, streaming? KMP or Z.

2. Many patterns? Aho–Corasick.

3. Repeated substring queries? Suffix array/automaton after one index build.

Quantitative check

Text n = 10⁷, pattern m = 10³: naive worst case ~10¹⁰ comparisons; KMP is ~10⁷ + 10³. Aho–Corasick over thousands of patterns is one pass over n plus output size, not thousands of separate scans.

Pattern matching: the heavyweights

Rabin-Karp (Rolling Hash)

Uses a sliding window hash. Instead of comparing characters, it compares hash values. If hashes match, it verifies characters.

Hash('abc') -> Hash('bcd') in O(1)

KMP (Prefix Function)

Never "backtracks" in the text. It uses a Pi Table to know where to start matching if a mismatch occurs.

Guaranteed O(N + M) time.
Critical for streaming data.

Interactive KMP border trace

KMP prefix-function lab

Longest border after each character

π=0

π=?

prefix: a · border: ∅

A one-character prefix has no proper border.

Invariant: π[i] is the longest proper prefix equal to a suffix of pattern[0..i]. Fallback follows already-computed borders, never text positions backward.

KMP: standalone reference implementation

The prefix value π[i] is the longest proper prefix of the pattern that is also a suffix ending at i. On mismatch, following π[j−1] enumerates shorter valid borders without rechecking text. Both implementations below report Unicode code-point indices (not bytes, UTF-16 offsets, or grapheme clusters).

Python

python

def prefix_function(pattern):
    pi = [0] * len(pattern)
    for i in range(1, len(pattern)):
        j = pi[i - 1]
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        pi[i] = j
    return pi

def kmp_find_all(text, pattern):
    if pattern == "":
        return list(range(len(text) + 1))
    pi = prefix_function(pattern)
    matches, j = [], 0
    for i, char in enumerate(text):
        while j > 0 and char != pattern[j]:
            j = pi[j - 1]
        if char == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - len(pattern) + 1)
            j = pi[j - 1]  # overlapping matches
    return matches

assert kmp_find_all("abababa", "aba") == [0, 2, 4]
assert kmp_find_all("🙂🙂", "🙂") == [0, 1]

Java

java

import java.util.ArrayList;
import java.util.List;

public final class KmpSearch {
    static int[] prefixFunction(int[] pattern) {
        int[] pi = new int[pattern.length];
        for (int i = 1; i < pattern.length; i++) {
            int j = pi[i - 1];
            while (j > 0 && pattern[i] != pattern[j]) j = pi[j - 1];
            if (pattern[i] == pattern[j]) j++;
            pi[i] = j;
        }
        return pi;
    }

    static List<Integer> findAll(String text, String pattern) {
        List<Integer> matches = new ArrayList<>();
        int[] textPoints = text.codePoints().toArray();
        int[] patternPoints = pattern.codePoints().toArray();
        if (patternPoints.length == 0) {
            for (int i = 0; i <= textPoints.length; i++) matches.add(i);
            return List.copyOf(matches);
        }
        int[] pi = prefixFunction(patternPoints);
        int j = 0;
        for (int i = 0; i < textPoints.length; i++) {
            while (j > 0 && textPoints[i] != patternPoints[j]) j = pi[j - 1];
            if (textPoints[i] == patternPoints[j]) j++;
            if (j == patternPoints.length) {
                matches.add(i - patternPoints.length + 1);
                j = pi[j - 1];
            }
        }
        return List.copyOf(matches);
    }

    public static void main(String[] args) {
        if (!findAll("abababa", "aba").equals(List.of(0, 2, 4))) throw new AssertionError();
        if (!findAll("🙂🙂", "🙂").equals(List.of(0, 1))) throw new AssertionError();
    }
}

KMP correctness and cost

Invariant

Before text[i], pattern[0..j) equals the suffix of text processed so far.

Fallback

π[j−1] is the longest smaller border still capable of matching; discarded candidates are provably impossible.

Linear bound

j increases at most n times while scanning text; every fallback decreases j, so total fallback work is O(n+m).

🛡️ Aho-Corasick: The Grep Engine

Malware Detection

Multi-Pattern Optimization

Traditional search tools search for 1 pattern at a time. Aho-Corasick builds aFinite Automaton (Trie + Failure Links) to search for thousands of patternssimultaneously in a single pass over the text.

Finding ['virus', 'worm', 'trojan'] in a binary file...

🧬 Suffix Structures: DNA & Bioinfo

Suffix Trees

The Swiss Army Knife

A path-compressed trie of all suffixes. It has O(n) nodes and supports substring lookup in O(pattern length) after construction; the uncompressed suffix trie can require Θ(n²) nodes.

Caveat: linear asymptotic space can still have large pointer/edge-label constants in practice.

Suffix Arrays

Space-Efficient Alternative

A sorted array of suffix indices. When combined with an LCP (Longest Common Prefix) array, it provides the same power as Suffix Trees with massive memory savings.

Standard in modern Genome Sequencing pipelines.

📦 Data Compression: BWT

Burrows-Wheeler Transform

BWT doesn't compress data on its own; it rearranges it to make it highly compressible by group similar characters together. This is the heart of bzip2.

'banana

#x27; -> 'annb$aa' (easier for RLE compression)

Algorithm selection map

Need	Tool	Core guarantee	Caveat
One exact pattern	KMP or Z algorithm	O(n+m) deterministic	Z gives prefix-match lengths; KMP is natural for streaming state
Many same-length windows / duplicates	Rolling hash	O(1) window update	Hash equality is probabilistic unless characters are verified; use double/wide hashes carefully
Many patterns	Aho–Corasick	O(text + matches) after automaton build	Alphabet transitions and output volume dominate memory/time
Repeated substring queries	Suffix array + LCP / suffix automaton	Index once, query repeatedly	Construction, memory, and static/dynamic requirements differ
Palindromes	Expand centers / Manacher / palindromic tree	O(n²) simple or O(n) specialized	Choose longest-one-shot vs enumerate distinct/online palindromes

Text contracts and adversarial testing

• Decide bytes, UTF-16 units, code points, or grapheme clusters; reported indices follow that unit.
• Normalize/case-fold only when product semantics require it; locale-sensitive text is not ASCII lowercase.
• Define empty-pattern behavior and whether overlapping matches are returned.
• Streaming chunks must retain matcher state and handle a match spanning boundaries.

• Test repeated prefixes (aaaa…), periodic patterns, overlaps, empty inputs, and near matches.
• Force rolling-hash collisions or mock the hash; always verify when correctness is absolute.
• Cross-check randomized results against a naive oracle.
• Cap output for match explosions and untrusted multi-pattern dictionaries.

Exercises

Compute the for pattern aabaaab. On a mismatch after matching 5 chars, where does KMP fall back?
n = 10⁷, m = 100. Compare worst-case character comparisons for naive vs KMP. When might a verified rolling hash still be preferable?
You must find 5,000 malware signatures in one binary stream. Why is repeated KMP the wrong architecture versus Aho–Corasick?

Primary sources

Knuth, Morris, Pratt (1977): Fast pattern matching in strings.
Aho & Corasick (1975): Efficient string matching (multi-pattern).
Manber & Myers: Suffix arrays (space-efficient substring indexes).

Takeaway

String algorithms trade preprocessing for linear scans. Name the query shape, the text unit, and the adversary before picking KMP, hashes, or an automaton.