String Searching Algorithms — 12-Min Parser Failure on 2GB

Every production system that processes text does string searching. Log parsers, protocol handlers, search engines, DNA alignment tools, plagiarism detectors — all of them have string search at their core. The algorithm you choose matters more than most engineers realise until they hit the wrong one at scale.

The naive approach is O(nm). For a 1GB log file with n=10^9 and a 100-char pattern, that is 10^11 comparisons — 100 seconds. Boyer-Moore on the same problem: sub-linear O(n/m) in practice — under a second.

This guide maps the landscape. Up front: KMP for guaranteed linear time on repetitive patterns, Boyer-Moore for long patterns in English text (fastest in practice), Rabin-Karp for multi-pattern search, Aho-Corasick when you have thousands of patterns simultaneously.

The Naive / Brute Force Approach

The simplest approach: slide the pattern across the text one character at a time and check for a match at each position.

Time complexity: O(nm) worst case — occurs with patterns like AAAB in text AAAA...A Space complexity: O(1)

Despite being slow, the naive approach performs well in practice for typical English text because mismatches occur early.

def naive_search(text: str, pattern: str) -> list[int]:
    n, m = len(text), len(pattern)
    positions = []
    for i in range(n - m + 1):
        if text[i:i+m] == pattern:
            positions.append(i)
    return positions

print(naive_search('AABAACAADAABAABA', 'AABA'))  # [0, 9, 12]

Algorithm Landscape — When to Use What

Each algorithm solves the same problem but excels in different scenarios:

KMP (Knuth-Morris-Pratt): Best when the pattern has repeated internal structure. Guarantees O(n+m) with no worst-case degradation. The go-to general purpose algorithm.

Rabin-Karp: Best for multiple pattern search or plagiarism detection. Uses hashing — O(n+m) average, O(nm) worst case but rare in practice.

Boyer-Moore: Best for long patterns in English-like text. Skips characters aggressively — sub-linear O(n/m) in practice. Used in most real-world text editors (grep, vi).

Z-Algorithm: Elegant and easy to implement. O(n+m). Great for problems involving pattern matching within a string concatenation trick.

Aho-Corasick: Best when searching for many patterns simultaneously. O(n + total pattern length + matches). Used in antivirus engines and network intrusion detection.

Complexity Comparison Table

A summary of all major string searching algorithms by preprocessing time, search time, and space requirements.

The Sliding Window Mental Model

All string searching algorithms share a sliding window mental model — a window of size m slides across the text. What differs is how each algorithm decides to slide:

• Naive: Always slides by 1
• KMP: Uses failure function to skip ahead — never re-examines matched characters
• Boyer-Moore: Slides by the maximum of bad character and good suffix rules — can skip m characters at a time
• Rabin-Karp: Computes a rolling hash so the window comparison is O(1) average
• Z-Algorithm: Pre-computes how far each suffix matches the pattern prefix

Understanding this model makes it easy to reason about why each algorithm achieves its complexity.

Production-Grade String Search: Real-World Considerations

Beyond algorithm complexity, production string search faces additional challenges:

Unicode and multi-byte encodings: UTF-8 variable-length characters mean you can't just compare bytes — you need to align on code-point boundaries. Python's str handles this, but C/Java must be careful.

Memory impact: For very large texts (GBs), streaming implementations that avoid loading the entire text into memory are critical. Rabin-Karp and KMP can both be implemented as stream algorithms.

Pattern with regex features: Real-world search often needs wildcards, alternation, case-insensitivity. Dedicated regex engines (PCRE, RE2) use automata theory — beyond simple string matching.

Hardware acceleration: Modern CPUs have SIMD instructions (SSE4.2, AVX2) that can compare 16-32 bytes in parallel. libc's memmem uses micro-optimisations. In production, you're almost always better off relying on the standard library.

Frequently Asked Questions