String Searching Algorithms — Overview and Comparison

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.

Frequently Asked Questions