String Algorithms

String Fundamentals

String algorithms underpin text search, bioinformatics, compilers, log processing and version control. The recurring theme in this chapter is that the obvious O(nm) approach to pattern matching can almost always be reduced to O(n + m) — by preprocessing the pattern so that a mismatch tells you something useful instead of forcing you to start over.

Two implementation notes before the algorithms. In Python, strings are immutable, so building one up with s += c in a loop is O(n²) — collect the pieces in a list and "".join() once. And if you are working with human text rather than ASCII, remember that a Python character is a Unicode code point, not a user-perceived character: an emoji or an accented letter may be several code points, so naive slicing and reversal can corrupt it.

Pattern Matching: The Naive Approach

Find every occurrence of a pattern of length m inside a text of length n. The direct method tries the pattern at each of the n − m + 1 starting positions: 

def naive_search(text, pattern):
    n, m = len(text), len(pattern)
    matches = []
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            matches.append(i)
    return matches

# Time: O(n * m)    Space: O(1)

On ordinary text this is usually fine — mismatches typically happen on the first character, so the inner loop rarely runs. The worst case is a text and pattern that almost match everywhere: searching "AAAAAB" in "AAAAAAAAAAAAAAAA" compares 5 characters at every position before failing. Every algorithm below exists to eliminate that repeated work.

KMP (Knuth-Morris-Pratt)

The insight: when a mismatch occurs after matching k characters, you already know what those k characters were — they are a prefix of the pattern. If that prefix has a proper suffix which is also a prefix of the pattern, you can slide the pattern forward to align them and resume, without ever moving backwards in the text.

The failure function

Precompute, for each position i, the length of the longest proper prefix of pattern[0..i] that is also a suffix of it. This array is usually called LPS (longest proper prefix which is also suffix). 

pattern:  A  B  A  B  C  A  B  A  B
index:    0  1  2  3  4  5  6  7  8
lps:      0  0  1  2  0  1  2  3  4
                            ^
        lps[8] = 4: "ABAB" is both a prefix and a suffix of "ABABCABAB",
        so after a mismatch here we resume with 4 characters already matched.
                
def build_failure(pattern):
    """lps[i] = length of the longest proper prefix of pattern[:i+1]
       that is also a suffix of it."""
    lps = [0] * len(pattern)
    length = 0          # length of the current matching prefix
    i = 1

    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length > 0:
            length = lps[length - 1]     # fall back to the next shorter candidate
        else:
            lps[i] = 0
            i += 1

    return lps

The search

def kmp_search(text, pattern):
    """Return the start index of every occurrence of pattern in text."""
    if not pattern:
        return list(range(len(text) + 1))

    lps = build_failure(pattern)
    matches = []
    i = j = 0                            # i indexes text, j indexes pattern

    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == len(pattern):
                matches.append(i - j)
                j = lps[j - 1]           # keep going: find overlapping matches too
        elif j > 0:
            j = lps[j - 1]               # slide the pattern, do NOT rewind i
        else:
            i += 1

    return matches

# Time: O(n + m)    Space: O(m)

i never decreases, which is what guarantees linear time: each character of the text is examined at most twice. Because the search continues after a match using j = lps[j-1], KMP correctly reports overlapping occurrences — searching for "AA" in "AAAA" yields 0, 1 and 2.

The failure function is useful on its own. The shortest repeating unit of a string s is len(s) - lps[-1] when that divides len(s), which solves "is this string built from a repeated substring?" in linear time.

Rabin-Karp

Compare hashes instead of characters. A rolling hash updates in O(1) as the window slides, so the whole scan is O(n + m) on average — and unlike the other algorithms here, it extends naturally to searching for many patterns at once, or to 2-D pattern matching. 

def rabin_karp(text, pattern, base=256, mod=(1 << 61) - 1):
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []

    high = pow(base, m - 1, mod)         # value of the leading digit's place
    pattern_hash = text_hash = 0

    for i in range(m):                   # hash the pattern and the first window
        pattern_hash = (pattern_hash * base + ord(pattern[i])) % mod
        text_hash    = (text_hash    * base + ord(text[i]))    % mod

    matches = []
    for i in range(n - m + 1):
        # Hash equality is necessary but not sufficient - always verify.
        if pattern_hash == text_hash and text[i:i + m] == pattern:
            matches.append(i)

        if i < n - m:                    # roll: drop text[i], append text[i+m]
            text_hash = ((text_hash - ord(text[i]) * high) * base
                         + ord(text[i + m])) % mod

    return matches

# Time: O(n + m) average, O(n * m) worst case (every window collides)
# Space: O(1)

Two things matter for correctness and speed. Always verify a hash match with a real comparison — equal hashes do not mean equal strings. And choose the modulus carefully: a small or predictable modulus lets an adversary construct input where every window collides, degrading the search to O(nm). This is the same hash-flooding concern that affects hash tables; randomising the base per run is the standard defence.

Boyer-Moore and Boyer-Moore-Horspool

Boyer-Moore matches the pattern right to left and, on a mismatch, uses the offending text character to jump forward — often by the pattern's whole length. It is the only algorithm here that is sublinear in practice: it can skip characters entirely without ever looking at them. This is what makes it the basis of most real-world implementations, including GNU grep and many memmem routines.

Horspool's simplification keeps only the bad-character rule, which is most of the benefit for a fraction of the complexity: 

def bmh_search(text, pattern):
    """Boyer-Moore-Horspool."""
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []

    # For each character, how far we can safely shift if it is the mismatch.
    # Characters absent from the pattern let us skip the full pattern length.
    shift = {pattern[i]: m - 1 - i for i in range(m - 1)}

    matches = []
    i = 0
    while i <= n - m:
        if text[i:i + m] == pattern:
            matches.append(i)
        i += shift.get(text[i + m - 1], m)

    return matches

# Time: O(n/m) best case, O(n * m) worst    Space: O(alphabet)

Best case is genuinely O(n/m): searching a 20-character pattern in a text sharing none of its characters examines only every 20th character. Full Boyer-Moore adds a second heuristic (the good suffix rule), which bounds the worst case at O(n + m) at the cost of a more involved preprocessing step.

Which to use? Boyer-Moore for long patterns over large alphabets — searching natural-language text. KMP when you need a guaranteed linear bound, when the alphabet is tiny (DNA), or when the input arrives as a stream and cannot be rewound. Rabin-Karp for multiple patterns or multi-dimensional matching. In practice, call your language's built-in find first; it is usually a tuned hybrid.

Z-Algorithm

For each position i, z[i] is the length of the longest substring starting at i that is also a prefix of the whole string. It carries the same information as KMP's failure function but is often easier to reason about, and it solves several problems more directly. 

def z_function(s):
    n = len(s)
    z = [0] * n
    if n:
        z[0] = n
    l = r = 0                            # [l, r) is the rightmost match found so far

    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])  # reuse what we already know
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1                    # extend by brute force
        if i + z[i] > r:
            l, r = i, i + z[i]

    return z

def z_search(text, pattern, sep="\x00"):
    """Pattern matching: build pattern + separator + text, then read off z."""
    if not pattern:
        return []
    combined = pattern + sep + text      # sep must not occur in either string
    z = z_function(combined)
    m = len(pattern)
    return [i - m - 1 for i in range(m + 1, len(combined)) if z[i] >= m]

# Time: O(n + m)    Space: O(n + m)

Common String Problems

Longest Palindromic Substring — Manacher's Algorithm

The obvious approach expands around each of the 2n − 1 possible centres in O(n²). Manacher's does it in O(n) by reusing palindromes already found: inside a known palindrome, the radius at a position mirrors the radius at its reflection. 

def longest_palindrome(s):
    if not s:
        return ""

    # Interleave with '#' so even- and odd-length palindromes are handled
    # uniformly: "aba" -> "#a#b#a#",  "abba" -> "#a#b#b#a#"
    t = "#" + "#".join(s) + "#"
    n = len(t)
    p = [0] * n              # p[i] = palindrome radius centred at i
    centre = right = 0

    for i in range(n):
        if i < right:
            p[i] = min(right - i, p[2 * centre - i])   # mirror position
        while (i - p[i] - 1 >= 0 and i + p[i] + 1 < n
               and t[i - p[i] - 1] == t[i + p[i] + 1]):
            p[i] += 1
        if i + p[i] > right:
            centre, right = i, i + p[i]

    k = max(range(n), key=lambda i: p[i])
    start = (k - p[k]) // 2              # map back to the original string
    return s[start:start + p[k]]

# Time: O(n)    Space: O(n)

Longest Common Substring

Distinct from longest common subsequence — a substring must be contiguous. The DP recurrence differs accordingly: a mismatch resets the running length to 0 rather than carrying the best result forward. 

def longest_common_substring(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    best, end = 0, 0

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > best:
                    best, end = dp[i][j], i
            # else: dp[i][j] stays 0 - contiguity is broken

    return s1[end - best:end]

# Time: O(m * n)    Space: O(m * n), reducible to O(n) with two rows.
# Suffix automata solve this in O(m + n) if you need it.

Anagram Detection

from collections import Counter

def is_anagram(a, b):
    return Counter(a) == Counter(b)          # O(n), beats sorting's O(n log n)

def group_anagrams(words):
    """Group words that are anagrams of one another."""
    groups = {}
    for w in words:
        key = tuple(sorted(w))               # canonical form; a 26-tuple of
        groups.setdefault(key, []).append(w) # counts is faster for long words
    return list(groups.values())

String Compression (Run-Length Encoding)

def compress(s):
    """'aabcccccaaa' -> 'a2b1c5a3'. Returns the original if that is shorter."""
    if not s:
        return s

    parts = []                    # build a list, then join once:
    count = 1                     # repeated s += c would be O(n^2)
    for i in range(1, len(s) + 1):
        if i < len(s) and s[i] == s[i-1]:
            count += 1
        else:
            parts.append(s[i-1] + str(count))
            count = 1

    compressed = "".join(parts)
    return compressed if len(compressed) < len(s) else s

Related, and covered elsewhere on the site: Edit distance and longest common subsequence are both DP problems, and tries are the structure of choice for prefix matching and autocomplete.

Further Topics

  • Aho-Corasick: searches for many patterns simultaneously in O(n + total pattern length + matches). It is a trie augmented with KMP-style failure links, and it is what intrusion-detection systems and virus scanners use to match thousands of signatures in one pass.
  • Suffix arrays: all suffixes of a string in sorted order, buildable in O(n log n) or O(n). With an LCP array alongside, they answer substring queries, longest repeated substring, and longest common substring efficiently. Far more memory-friendly than suffix trees, which is why they dominate in practice.
  • Suffix automaton: recognises every substring of a string, built online in O(n). The most powerful tool here, and the least widely known.
  • Burrows-Wheeler Transform: a reversible permutation that clusters similar characters together, making text far more compressible. It is the core of bzip2 and of read aligners such as BWA and Bowtie.
  • Regular expressions: Thompson's construction compiles a regex to an NFA and matches in guaranteed O(nm). Note that most language runtimes (Python, Java, JavaScript, Perl) instead use backtracking engines, which support backreferences but can blow up exponentially — the cause of ReDoS vulnerabilities. Go and Rust use RE2-style automata specifically to avoid this.
  • Approximate matching: the bitap (shift-or) algorithm handles fuzzy search with a bounded number of errors, using bit-parallelism to process a whole word at a time.

What's Next?

Now that you understand string algorithms, explore related topics: