5 — Strings and pattern matching

A string is an array of characters, so everything in Arrays and sliding windows applies to it. Two things make strings a subject of their own. First, the alphabet is usually small and known, which turns hash maps into fixed-size count arrays and makes hashing whole substrings practical. Second, the central question, “where does this pattern occur in this text?”, has a deep body of algorithms that avoid re-examining characters already seen. This chapter covers the everyday techniques first, then the matching algorithms, then the index structures (suffix arrays, suffix automata, Aho-Corasick) that answer many queries against one text or many patterns against one text.

Throughout, n is the length of the text and m the length of the pattern. Timings were measured with Python 3.14 on one Mac; exact numbers will differ elsewhere.

How strings are stored

A Python str is an immutable sequence of Unicode code points. Since Python 3.3 (PEP 393), CPython stores each string in the narrowest fixed width that fits its largest code point: 1 byte per character if every code point is below 256, 2 bytes if below 65,536, otherwise 4. Because the width is fixed within a string, s[i] is O(1) address arithmetic and len(s) is a stored field.

import sys

for ch in ["a", "\u00e9", "\u20ac", "\U0001D11E"]:
    print(repr(ch), hex(ord(ch)), sys.getsizeof(ch * 1000))

'a' 0x61 1041
'é' 0xe9 1057
'€' 0x20ac 2058
'𝄞' 0x1d11e 4060

A thousand ASCII characters take 1,041 bytes; one character above U+FFFF anywhere in the string makes every character take 4 bytes. bytes and bytearray are sequences of raw bytes and are what files and sockets actually deliver; algorithms in this chapter work on either.

Immutability and the cost of concatenation

Strings cannot be changed in place. s += "x" conceptually builds a new string of length len(s) + 1 and copies the old contents into it, which makes a loop of n appends $O(n^2)$. CPython has an optimization for exactly this pattern: when the left operand’s reference count is 1 (nothing else refers to it), it resizes the string in place instead of copying, and most such resizes are cheap. The optimization is fragile. Any second reference to the string disables it, and it does not exist for bytes or in other Python implementations.

The aliased version does nothing more than assign alias = s inside the loop, yet at 400,000 appends it is 100 times slower: four times the data, sixteen times the time, which is the quadratic signature. Collecting pieces in a list and calling "".join once (or using io.StringIO, or a bytearray for bytes) is linear by construction and does not depend on an implementation detail.

The same reasoning applies to slicing. s[i:j] copies j − i characters, so code that slices inside a loop (for example, comparing s[i:i+m] == pat at every i) does O(m) work per slice. That is often still the fastest choice in Python because the copy and comparison run in C, but it should be counted as O(m), not O(1).

Frequency maps and ASCII arrays

Many string problems reduce to “how many of each character?”. collections.Counter answers it for any alphabet. When the alphabet is known to be small (lowercase letters, bytes, ASCII), a list of 26, 128 or 256 counters indexed by ord(ch) − ord("a") is faster, has no hashing, and can be compared or used as a dictionary key (after converting to a tuple).

Valid Anagram: two strings are anagrams when their counts match. Incrementing for one and decrementing for the other needs only one array:

def is_anagram(a, b):
    if len(a) != len(b):
        return False
    counts = [0] * 26
    for x, y in zip(a, b):
        counts[ord(x) - 97] += 1
        counts[ord(y) - 97] -= 1
    return not any(counts)

Sorting both strings and comparing is O(m log m) and also correct; Counter(a) == Counter(b) is the idiomatic Python version for arbitrary alphabets.

Group Anagrams: use the count vector as the grouping key. With k words of length at most L, this is O(kL), against O(kL log L) for the sorted-string key.

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = [0] * 26
        for ch in w:
            key[ord(ch) - 97] += 1
        groups[tuple(key)].append(w)
    return list(groups.values())

>>> group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Find All Anagrams in a String combines a count array with a fixed-size sliding window of length m. Comparing two 26-element lists is O(26) per step, so the total is O(26n), which is O(n):

def find_anagrams(s, p):
    m = len(p)
    if m > len(s):
        return []
    need, have = [0] * 26, [0] * 26
    for ch in p:
        need[ord(ch) - 97] += 1
    out = []
    for i, ch in enumerate(s):
        have[ord(ch) - 97] += 1
        if i >= m:
            have[ord(s[i - m]) - 97] -= 1
        if have == need:
            out.append(i - m + 1)
    return out

find_anagrams("cbaebabacd", "abc") is [0, 6]. Keeping a running count of how many of the 26 letters currently match removes the O(26) comparison, but in Python the list comparison runs in C and is usually faster than the extra bookkeeping. Permutation in String is the same loop returning a boolean.

The variable-size window problems on strings (Longest Substring Without Repeating Characters, Minimum Window Substring, Longest Repeating Character Replacement) are worked through in Arrays and sliding windows. When the problem is about prefixes of many words rather than counts, a trie is the right structure; see Tries and range structures.

Two pointers on strings

Palindromes

Valid Palindrome (ignoring case and non-alphanumeric characters) walks two pointers inward, skipping characters that do not count:

def is_palindrome(s):
    lo, hi = 0, len(s) - 1
    while lo < hi:
        if not s[lo].isalnum():
            lo += 1
        elif not s[hi].isalnum():
            hi -= 1
        elif s[lo].lower() != s[hi].lower():
            return False
        else:
            lo += 1
            hi -= 1
    return True

O(n) time and O(1) space, against O(n) space for the shorter t == t[::-1] on a cleaned copy (which is nonetheless faster in Python for moderate sizes).

Valid Palindrome II allows deleting one character. At the first mismatch, the only two candidates are deleting the left character or the right one; check whether either remainder is a palindrome. Trying every deletion would be O(n²); this is O(n).

def valid_palindrome_one_deletion(s):
    def pal(lo, hi):
        while lo < hi:
            if s[lo] != s[hi]:
                return False
            lo += 1
            hi -= 1
        return True

    lo, hi = 0, len(s) - 1
    while lo < hi:
        if s[lo] != s[hi]:
            return pal(lo + 1, hi) or pal(lo, hi - 1)
        lo += 1
        hi -= 1
    return True

Longest palindromic substring is covered with Manacher’s algorithm below.

Isomorphic strings, rotations, compression and reversal

Isomorphic Strings: s and t are isomorphic if a one-to-one character mapping turns s into t. The common bug is checking only one direction: "badc" and "baba" pass a forward-only check (b→b, a→a, d→b, c→a) even though b and d both map to b. Two maps fix it:

def is_isomorphic(s, t):
    if len(s) != len(t):
        return False
    fwd, back = {}, {}
    for a, b in zip(s, t):
        if fwd.setdefault(a, b) != b or back.setdefault(b, a) != a:
            return False
    return True

String rotation: b is a rotation of a exactly when they have equal length and b occurs in a + a, since a + a contains every rotation of a as a substring.

def is_rotation(a, b):
    return len(a) == len(b) and b in a + a

The cost is one substring search on a string of length 2n. With a linear-time matcher (KMP, or Python’s in, discussed below) the whole check is O(n). The length check is essential: "ab" occurs in "abcabc".

String Compression (run-length encoding, "aabcccccaaa" to "a2b1c5a3", returning the original if encoding does not shorten it) is a read pointer finding the end of each run:

def compress(s):
    out = []
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]:
            j += 1
        out.append(s[i] + str(j - i))
        i = j
    enc = "".join(out)
    return enc if len(enc) < len(s) else s

The inner while does not make it quadratic: i jumps to j, so each character is visited once. The in-place version on a character array (LeetCode 443) uses separate read and write pointers, as in the array chapter.

Reversal. In Python, s[::-1] reverses a string, and " ".join(reversed(s.split())) reverses the order of words while collapsing runs of spaces. On a mutable character array the in-place version of Reverse Words in a String reverses the whole array and then reverses each word, the same identity $(AB)^R = B^R A^R$ that rotates arrays.

Brute-force matching

The direct method tries every alignment of the pattern against the text and compares character by character:

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

On random text over a large alphabet most alignments fail on the first or second character, so the expected work is close to n comparisons. The worst case is O(nm): with text aaaa...a and pattern aaa...ab, every alignment matches m − 1 characters before failing. The waste is that the comparisons at alignment i already revealed characters i .. i+m−2, and the next alignment reads most of them again. Every algorithm below is a different way of not throwing that information away.

Knuth-Morris-Pratt

KMP (Knuth, Morris and Pratt, published together in 1977) never moves backward in the text. When a mismatch happens after matching k characters, the matched part is a known string, namely pat[:k]. The algorithm precomputes, for every k, how much of that matched part can be reused as the start of the next possible match.

The failure function

The prefix function (also called the failure function) is defined for each position i of the pattern:

$\pi[i] = \text{length of the longest proper prefix of } p[0..i] \text{ that is also a suffix of } p[0..i]$

“Proper” means shorter than the whole thing. Such a prefix-and-suffix is called a border. If k characters have matched and the next one fails, the longest shorter alignment that is still consistent with what has been seen keeps π[k − 1] characters matched. No alignment in between can work, because it would imply a longer border.

Building it for p = "ababaca":

i  p[i]  prefix so far   longest border    pi[i]
0  a     a               (none)            0
1  b     ab              (none)            0
2  a     aba             a                 1
3  b     abab            ab                2
4  a     ababa           aba               3
5  c     ababac          (none)            0
6  a     ababaca         a                 1

The construction runs the matcher on the pattern against itself. Keep k, the length of the current border. To extend to position i: if p[i] == p[k], the border grows to k + 1. If not, fall back to the next shorter border of the current one, which is π[k − 1], and try again; if k reaches 0 and still fails, the border is 0.

At i = 5 in the example, k = 3 (border aba). p[5] = c and p[3] = b differ, so k = π[2] = 1 (border a). p[1] = b still differs from c, so k = π[0] = 0. p[0] = a differs from c, so π[5] = 0. At i = 6, p[6] = a = p[0], so π[6] = 1.

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

>>> prefix_function("ababaca"), prefix_function("aabaaab")
([0, 0, 1, 2, 3, 0, 1], [0, 1, 0, 1, 2, 2, 3])

Searching

The search loop is the same code with the text in place of the pattern’s own suffix. After a full match, falling back to π[m − 1] lets overlapping matches be found.

def kmp_find(text, pat):
    pi = prefix_function(pat)
    out = []
    k = 0
    for i, ch in enumerate(text):
        while k > 0 and ch != pat[k]:
            k = pi[k - 1]
        if ch == pat[k]:
            k += 1
        if k == len(pat):
            out.append(i - k + 1)
            k = pi[k - 1]
    return out

>>> kmp_find("abababcababa", "ababa")
[0, 7]

Complexity. k increases by at most 1 per text character and every iteration of the inner while decreases it by at least 1, and it never goes below 0. So the total number of fallbacks over the whole run is at most n, and the search is O(n) worst case, O(n + m) including preprocessing, with O(m) extra space. That is an amortized argument (see Complexity): one character can trigger many fallbacks, but not on average.

When to use it. KMP reads the text strictly left to right, one character at a time, never backing up, so it works on streams that cannot be rewound. Its worst case is linear. It does not skip characters, so on ordinary text it is usually slower than Boyer-Moore-style algorithms, which do.

The prefix function on its own solves several problems without any search:

• Smallest period of a string: m − π[m − 1]. The string is a repetition of a block (Repeated Substring Pattern) exactly when that period divides m and is less than m. For "abcabcabc" the period is 3.
• Shortest Palindrome (add the fewest characters to the front to make a palindrome): the longest palindromic prefix of s is π at the end of s + sep + reverse(s), where sep occurs in neither. Prepend the reverse of the rest. "aacecaaa" becomes "aaacecaaa".
• Counting occurrences of each prefix of a string inside itself.

Rabin-Karp and rolling hashes

Rabin-Karp (Richard Karp and Michael Rabin, 1987) compares hashes instead of characters. If the hash of each length-m window of the text could be computed in O(1), then comparing it with the pattern’s hash would rule out almost every alignment in O(1), and only hash matches would need a character-by-character check.

Polynomial rolling hash

Treat a string as the digits of a number in base B, reduced modulo a prime M:

$h(s_0 s_1 \ldots s_{m-1}) = \left(s_0 B^{m-1} + s_1 B^{m-2} + \cdots + s_{m-1}\right) \bmod M$

Sliding the window one place to the right removes the leading term and appends a new last digit:

$h_{i+1} = \left((h_i - s_i B^{m-1}) \cdot B + s_{i+m}\right) \bmod M$

which is O(1) given $B^{m-1} \bmod M$ precomputed.

import random

MOD = (1 << 61) - 1          # a Mersenne prime

def rabin_karp_find(text, pat, base=None):
    n, m = len(text), len(pat)
    if m == 0 or m > n:
        return [] if m else list(range(n + 1))
    if base is None:
        base = random.randrange(256, MOD - 1)
    high = pow(base, m - 1, MOD)
    hp = ht = 0
    for i in range(m):
        hp = (hp * base + ord(pat[i])) % MOD
        ht = (ht * base + ord(text[i])) % MOD
    out = []
    for i in range(n - m + 1):
        if ht == hp and text[i:i + m] == pat:     # verify: hashes can collide
            out.append(i)
        if i + m < n:
            ht = ((ht - ord(text[i]) * high) * base + ord(text[i + m])) % MOD
    return out

Collision probability

Two different strings of length m collide when the difference of their hash polynomials, a nonzero polynomial in B of degree at most m − 1, evaluates to 0 mod M. Over a prime field such a polynomial has at most m − 1 roots, so if B is chosen uniformly at random,

$\Pr[\text{collision}] \le \frac{m-1}{M}$

for any fixed pair of strings. With $M = 2^{61} - 1$ and m = 1,000,000 that is below $5 \times 10^{-13}$ per comparison, and a union bound over n windows keeps the total tiny. Three details matter:

• The base must be random (chosen at run time). A fixed, published base lets an adversary construct colliding inputs.
• Arithmetic modulo $2^{64}$ (letting machine integers overflow) is not a prime modulus, and there is a known family of strings (built from the Thue-Morse sequence) that collides for every odd base. Use a prime.
• Many-against-many comparisons hit the birthday bound: with k hashes stored in a set, about $k^2/2$ pairs can collide, so with $M \approx 10^9$ collisions appear after tens of thousands of strings. A 61-bit modulus, or double hashing (two independent (base, modulus) pairs, compared as a tuple), pushes the probability down to roughly the product of the two.

Verifying every hash hit with a real comparison makes the output always correct; collisions then cost time, not correctness. The expected running time is O(n + m); the worst case, when every window matches (text aaaa, pattern aa), is O(nm) because each verification is O(m). This is fine when the occurrences are what is wanted, since producing them already costs that.

Prefix hashes for O(1) substring comparison

Storing the hash of every prefix lets the hash of any substring be computed in O(1), which turns “are these two substrings equal?” into an O(1) probabilistic test:

class PrefixHash:
    def __init__(self, s, base=None, mod=MOD):
        self.mod = mod
        self.base = base or random.randrange(256, mod - 1)
        n = len(s)
        self.h = [0] * (n + 1)
        self.pw = [1] * (n + 1)
        for i, ch in enumerate(s):
            self.h[i + 1] = (self.h[i] * self.base + ord(ch)) % mod
            self.pw[i + 1] = self.pw[i] * self.base % mod

    def get(self, lo, hi):
        """Hash of s[lo:hi]."""
        return (self.h[hi] - self.h[lo] * self.pw[hi - lo]) % self.mod

This is a prefix sum in a polynomial ring (compare prefix sums). Combined with binary search it gives the longest common prefix of two suffixes in O(log n), Longest Duplicate Substring in O(n log n) (binary search on the length, hash every window of that length into a set), and palindrome checks of arbitrary substrings (compare the forward hash with the hash of the reversed string). Rabin-Karp’s real strength is multiple patterns of the same length: put all their hashes in a set and test each window against the set in O(1), which is how plagiarism detectors fingerprint documents.

Boyer-Moore

Boyer-Moore (Robert Boyer and J Strother Moore, 1977) compares the pattern against the text from right to left, and when a mismatch occurs it uses what it learned to shift the pattern forward, often by more than one position. On large alphabets the shifts are frequently close to m, so most text characters are never examined: the best case is O(n / m).

Two rules each propose a shift; the algorithm takes the larger.

The bad-character rule

Suppose the pattern is aligned at text position s, and comparing from the right, pat[j] mismatches text character c = text[s + j]. The pattern can be shifted so that the rightmost occurrence of c in the pattern lines up with that text position. If c does not occur in the pattern at all, the whole pattern can move past it.

Pattern EXAMPLE, text HERE IS A SIMPLE EXAMPLE, showing what both rules propose at each mismatch (the good-suffix rule is explained next):

HERE IS A SIMPLE EXAMPLE
EXAMPLE                    s=0:  'E' vs 'S' at j=6. 'S' is not in the pattern.
                                 bad-char 7, good-suffix 1 -> shift 7
       EXAMPLE             s=7:  'E' vs 'P' at j=6. Last 'P' in pattern is index 4.
                                 bad-char 6-4 = 2, good-suffix 1 -> shift 2
         EXAMPLE           s=9:  'E','L','P','M' match; 'A' vs 'I' at j=2.
                                 bad-char 3, good-suffix 6 -> shift 6
               EXAMPLE     s=15: 'E' vs 'P' at j=6. bad-char 2 -> shift 2
                 EXAMPLE   s=17: full match

Five alignments and 15 character comparisons find the match in a 24-character text; brute force would try 18 alignments.

The table is a map from character to its last index in the pattern: last = {ch: i for i, ch in enumerate(pat)}. The proposed shift for a mismatch at j is j − last.get(c, −1), which can be zero or negative when the last occurrence is to the right of j; that is why the bad-character rule alone is not enough and why Horspool’s variant, below, changes what it looks at.

The good-suffix rule

If the last m − 1 − j characters matched before the mismatch at j, the text is known to contain that suffix t = pat[j+1:]. Shift the pattern to the next position where:

1. another occurrence of t in the pattern lines up with it, preferably one not preceded by pat[j] (the strong rule, since that same character just failed), or, if there is none,
2. the longest prefix of the pattern that is also a suffix of t lines up with the end of it.

If nothing matches at all, the shift is m minus the longest border of the whole pattern. The table depends only on the pattern and is computed in O(m) with a border-array construction similar to KMP’s:

def good_suffix_table(p):
    m = len(p)
    shift = [0] * (m + 1)
    border = [0] * (m + 1)
    i, j = m, m + 1
    border[i] = j
    while i > 0:                           # case 1: suffix occurs elsewhere
        while j <= m and p[i - 1] != p[j - 1]:
            if shift[j] == 0:
                shift[j] = j - i
            j = border[j]
        i -= 1
        j -= 1
        border[i] = j
    j = border[0]
    for i in range(m + 1):                 # case 2: only a prefix matches
        if shift[i] == 0:
            shift[i] = j
        if i == j:
            j = border[j]
    return shift

shift[j + 1] is the good-suffix shift for a mismatch at j; shift[0] is the shift after a full match. Together:

def boyer_moore_find(text, pat):
    n, m = len(text), len(pat)
    last = {ch: i for i, ch in enumerate(pat)}
    good = good_suffix_table(pat)
    out = []
    s = 0
    while s <= n - m:
        j = m - 1
        while j >= 0 and pat[j] == text[s + j]:
            j -= 1
        if j < 0:
            out.append(s)
            s += good[0]
        else:
            s += max(good[j + 1], j - last.get(text[s + j], -1))
    return out

Complexity. Preprocessing is O(m + σ) for alphabet size σ. With the strong good-suffix rule, the number of comparisons when the pattern does not occur is O(n + m); Richard Cole proved a bound of about 3n in 1991. When reporting all occurrences, the worst case is O(nm) (pattern aaa, text aaaa...), because after each match the algorithm re-verifies characters it has already seen; the Galil rule, which remembers how much of the pattern is known to match after a shift, restores O(n + m). The best case is O(n / m). This is the reason Boyer-Moore wins in practice on text with a reasonably large alphabet: the longer the pattern, the faster it runs.

Horspool’s simplification

Nigel Horspool’s 1980 variant drops the good-suffix rule and changes the bad-character rule to always look at the text character aligned with the last position of the pattern, whatever position mismatched. The shift for character c is the distance from the last occurrence of c in pat[:-1] to the end of the pattern, or m if it does not occur there. That shift is always at least 1, so no second rule is needed.

def horspool_find(text, pat):
    n, m = len(text), len(pat)
    shift = {ch: m - 1 - i for i, ch in enumerate(pat[:-1])}
    out = []
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and text[i + j] == pat[j]:
            j -= 1
        if j < 0:
            out.append(i)
        i += shift.get(text[i + m - 1], m)
    return out

Horspool is a few lines, has a tiny table, and performs nearly as well as full Boyer-Moore on natural text. Its worst case is O(nm), and the benchmark below finds it: pattern baaa...a in text aaaa...a compares m − 1 characters at each alignment and then shifts by 1. Full Boyer-Moore’s good-suffix rule shifts by m there.

The Z-algorithm

The Z-array of a string s stores, at each position i > 0, the length of the longest substring starting at i that matches a prefix of s:

$z[i] = \max\{k : s[0..k-1] = s[i..i+k-1]\}$

s:  a  a  b  x  a  a  b
z:  7  1  0  0  3  1  0      (z[0] is set to n by convention)

Computing it naively is O(n²). The linear algorithm keeps the Z-box [lo, hi): the matched segment, among those found so far, that reaches furthest right. Inside the box, s[lo..hi) equals s[0..hi−lo), so the Z-value at i inside the box is at least the Z-value at the mirrored position i − lo, capped at the box edge. Only characters beyond hi need to be compared explicitly, and each such comparison extends hi, which only moves right. Total work O(n).

def z_function(s):
    n = len(s)
    z = [0] * n
    if n:
        z[0] = n
    lo = hi = 0
    for i in range(1, n):
        if i < hi:
            z[i] = min(hi - i, z[i - lo])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > hi:
            lo, hi = i, i + z[i]
    return z

Pattern matching computes the Z-array of pat + sep + text, where sep is a character occurring in neither, and reports positions where the Z-value is at least m. The separator stops any match from running past the pattern.

def z_find(text, pat, sep="\x00"):
    m = len(pat)
    z = z_function(pat + sep + text)
    return [i - m - 1 for i in range(m + 1, len(z)) if z[i] >= m]

O(n + m) time and space. The Z-array and the prefix function carry the same information (each can be converted to the other in linear time); the Z-array is often easier to reason about for problems phrased in terms of prefixes, such as counting how often each prefix occurs or computing the string’s periods. Dan Gusfield’s 1997 textbook made it the standard teaching algorithm for exact matching.

Manacher’s algorithm

Longest Palindromic Substring. Expanding around each of the 2n − 1 possible centers (each character, and each gap between characters) is O(n²) worst case and O(1) space, and is the usual practical answer:

def longest_palindrome_expand(s):
    best_lo, best_len = 0, 0
    for center in range(2 * len(s) - 1):
        lo = center // 2
        hi = lo + center % 2
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo -= 1
            hi += 1
        if hi - lo - 1 > best_len:
            best_lo, best_len = lo + 1, hi - lo - 1
    return s[best_lo:best_lo + best_len]

Manacher’s algorithm (Glenn Manacher, 1975) does it in O(n) using the same box idea as the Z-algorithm. First, insert a separator between characters so that every palindrome has odd length and a single center: abaab becomes #a#b#a#a#b# (with sentinels ^ and $ at the ends so the expansion loop never needs a bounds check). Let p[i] be the radius of the longest palindrome centered at i in the transformed string. That radius equals the length of the corresponding palindrome in the original string.

The invariant: center and right describe the palindrome found so far that extends furthest right. For a new position i < right, its mirror 2·center − i lies inside the same palindrome, and a palindrome around the mirror is reflected around i, at least up to the boundary right. So p[i] starts at min(right − i, p[mirror]) and only expands beyond right by explicit comparison. Each successful expansion pushes right further, so the total work is O(n).

def manacher(s):
    t = "^#" + "#".join(s) + "#$"
    p = [0] * len(t)
    center = right = 0
    for i in range(1, len(t) - 1):
        if i < right:
            p[i] = min(right - i, p[2 * center - i])
        while t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1
        if i + p[i] > right:
            center, right = i, i + p[i]
    return p

def longest_palindrome_manacher(s):
    if not s:
        return ""
    p = manacher(s)
    length, i = max((v, i) for i, v in enumerate(p))
    start = (i - length) // 2
    return s[start:start + length]

t:  ^  #  a  #  b  #  a  #  a  #  b  #  $
p:  0  0  1  0  3  0  1  4  1  0  1  0  0
                ^ "aba"   ^ "baab" (center between the two a's)

longest_palindrome_manacher("forgeeksskeegfor") is "geeksskeeg". Summing (p[i] + 1) // 2 over all i counts every palindromic substring (Palindromic Substrings) in O(n). For Palindrome Partitioning (list every way to split into palindromes), the palindrome table feeds a backtracking search; see Backtracking. The minimum-cuts version is dynamic programming.

Measured: the matchers against str.find

Each pure-Python implementation above was timed searching for an absent pattern (so every algorithm scans the whole text) in 200,000 characters of text, against str.find. Times are milliseconds, best of three.

What the table shows:

• Skipping works. On random letters, Horspool and Boyer-Moore get faster as the pattern gets longer (2.44 ms to 0.67 ms) because shifts approach m. KMP, Z and brute force read every character regardless.
• Small alphabets reduce the skips. On DNA, shifts are short and Boyer-Moore’s advantage shrinks.
• Each worst case shows up where theory says. Brute force is O(nm) on aaa...ab (37 times slower than on random text). Horspool is O(nm) on baaa...a, where it matches 49 characters from the right before failing and then shifts by 1; full Boyer-Moore’s good-suffix rule shifts by 50 on the same input and takes 4.55 ms. KMP and Z are flat across all inputs.
• Rabin-Karp is the slowest in Python because each step does arithmetic on 61-bit values whose products exceed a machine word, so Python allocates big integers. In C with 64-bit arithmetic it is competitive, and its natural home is multi-pattern or substring-equality work, not single-pattern search.
• str.find is 30 to 3,000 times faster than all of them. The pure-Python loops pay interpreter overhead of tens of nanoseconds per character; str.find runs in C at a fraction of a nanosecond per character. In Python, implement these algorithms for what they compute (prefix functions, Z-arrays, palindrome radii, many patterns at once), not to beat in.

What str.find actually does

CPython’s substring search lives in Objects/stringlib/fastsearch.h. It is not one algorithm:

• A one-character needle is a plain scan (using memchr where possible).
• Short searches (haystack under 2,500 characters, or needle under 100 characters and haystack under 30,000, or needle under 6 characters) use the loop Fredrik Lundh wrote in 2006, described in the source as “a mix between boyer-moore and horspool”. It tests the character under the last position of the needle first and compares the rest of the window only when that matches. After a failed candidate it shifts by the distance to the previous occurrence of the needle’s last character inside the needle (a Horspool-style shift). It also keeps a tiny Bloom filter (one bit per character value modulo 64 on 64-bit builds) of the characters in the needle; when the character just past the window is not in the filter, no alignment covering it can match, so the window jumps by m + 1.
• Longer searches use the Two-Way algorithm of Maxime Crochemore and Dominique Perrin (1991), added in Python 3.10 by Dennis Sweeney (bpo-41972). Two-Way splits the needle at a “critical factorization”, matches the right part left to right and then the left part, and achieves O(n + m) worst-case time with O(1) extra space. CPython augments it with a Boyer-Moore-style skip table, so on typical text it still skips. If the needle is a large fraction of the haystack, CPython starts with the fast default loop and switches to Two-Way adaptively once it has done more than about m / 4 character comparisons without finding a match.

Before 3.10 only the default loop existed, and its worst case was O(nm): a needle such as a×k + b + a×k against a long run of as matches the last character at every alignment, compares k characters before failing, and shifts by one. Since 3.10, long searches are linear in the worst case. In the benchmark above the haystack is 200,000 characters, so every row went straight to Two-Way. str.count, in, str.replace, str.split and str.partition use the same machinery. The re module is a backtracking regular-expression engine, separate from all of this, and can be exponential on pathological patterns.

Suffix arrays

The matchers above preprocess the pattern. When one text is searched many times with different patterns, it is better to preprocess the text. A suffix array lists the starting positions of all suffixes of the text in sorted order.

s = "banana"
i  suffix         sorted:   sa   suffix     lcp with next
0  banana                   5    a          1
1  anana                    3    ana        3
2  nana                     1    anana      0
3  ana                      0    banana     0
4  na                       4    na         2
5  a                        2    nana

Every substring of s is a prefix of some suffix, and the suffixes sharing a given prefix are contiguous in sorted order. So finding a pattern is binary search over the suffix array comparing the pattern with suffixes: O(m log n) per query (see Searching), and all occurrences form one contiguous range.

Construction by prefix doubling

Sorting the suffixes directly with string comparisons costs O(n² log n) in the worst case, because a single comparison can be O(n). Prefix doubling (Udi Manber and Gene Myers, 1990) sorts by the first 1, 2, 4, 8, … characters. After the round for length k, each suffix has a rank among the distinct length-k prefixes. The rank of the first 2k characters of suffix i is determined by the pair (rank[i], rank[i + k]), because the first k characters and the next k characters are both already ranked. Sorting by that pair gives the ranks for 2k. After at most $\lceil \log_2 n \rceil$ rounds all ranks are distinct.

def suffix_array(s):
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    k = 1
    while True:
        key = lambda i: (rank[i], rank[i + k] if i + k < n else -1)
        sa.sort(key=key)
        new = [0] * n
        for a, b in zip(sa, sa[1:]):
            new[b] = new[a] + (key(a) != key(b))
        rank = new
        if n == 0 or rank[sa[-1]] == n - 1:     # all ranks distinct
            return sa
        k *= 2

>>> suffix_array("banana")
[5, 3, 1, 0, 4, 2]

With a comparison sort each round is O(n log n), giving O(n log² n) total. Replacing the sort with two passes of counting sort (radix sort on the pair, since ranks are below n) makes each round O(n) and the total O(n log n). Linear-time constructions exist (the DC3/skew algorithm of Kärkkäinen and Sanders, 2003, and SA-IS by Nong, Zhang and Chan, 2009); SA-IS is what serious libraries use.

The LCP array with Kasai’s algorithm

The LCP array stores, for each adjacent pair in suffix-array order, the length of their longest common prefix. Most suffix-array applications need it. Computing each entry by direct comparison is O(n²) worst case. Kasai, Lee, Arimura, Arikawa and Park (2001) observed that if suffix i shares h characters with the next suffix in sorted order, then suffix i + 1 shares at least h − 1 with its next suffix (drop the first character from both). Processing suffixes in text order, h decreases by at most 1 per step and increases at most n times in total, so the whole array is O(n).

def lcp_kasai(s, sa):
    n = len(s)
    rank = [0] * n
    for i, p in enumerate(sa):
        rank[p] = i
    lcp = [0] * max(n - 1, 0)        # lcp[i] = LCP(suffix sa[i], suffix sa[i+1])
    h = 0
    for i in range(n):
        if rank[i] == n - 1:
            h = 0
            continue
        j = sa[rank[i] + 1]
        while i + h < n and j + h < n and s[i + h] == s[j + h]:
            h += 1
        lcp[rank[i]] = h
        if h:
            h -= 1
    return lcp

lcp_kasai("banana", [5, 3, 1, 0, 4, 2]) is [1, 3, 0, 0, 2].

What the pair enables

Suffix arrays are used in genome alignment tools and full-text indexes (often in compressed form such as the FM-index, built on the Burrows-Wheeler transform, which is itself read directly off the suffix array). They use 4 or 8 bytes per text character, far less than a suffix tree.

Suffix trees and suffix automata

Suffix trees

A suffix tree is a trie of all suffixes of s$ (with a unique terminator $), with every chain of single-child nodes compressed into one edge labeled by a substring. It has exactly n + 1 leaves and at most n internal nodes, and edge labels are stored as index pairs into s, so it is O(n) in size. Peter Weiner gave the first linear-time construction in 1973; Esko Ukkonen’s 1995 online algorithm, which adds one character at a time using suffix links, is the one usually implemented.

It answers substring queries in O(m) (walk down from the root), longest repeated substring (deepest internal node), longest common substring of several strings (deepest node with leaves from all of them), and many more problems in linear time. Its drawback is memory: each node carries child pointers, edge bounds and a suffix link, which in practice costs many times the size of the text. A suffix array with an LCP array simulates almost all suffix-tree algorithms with a fraction of the space, which is why suffix arrays largely replaced suffix trees in practice.

Suffix automata

A suffix automaton is the smallest deterministic finite automaton that accepts exactly the suffixes of s. Because every substring is a prefix of a suffix, every substring of s corresponds to a path from the start state, and every path from the start state spells a substring. Blumer and colleagues showed in 1985 that it has at most 2n − 1 states and 3n − 4 transitions (for n ≥ 3), and it can be built online in O(n) time for a fixed alphabet.

The states are equivalence classes of substrings with the same set of ending positions (endpos). For s = "abcbc", the substrings bc and c both end at positions 2 and 4, so they share a state. Each state v stores:

• len[v]: the length of the longest substring in its class. The class contains exactly the suffixes of that string with lengths in $(\text{len}[\text{link}[v]], \text{len}[v]]$.
• link[v]: the suffix link, the state of the longest suffix that has a strictly larger endpos set.
• next[v]: outgoing transitions, one per character.

Adding a character c creates a state for the whole new string, then walks the suffix-link chain from the previous last state adding c-transitions until it finds a state that already has one. If that existing transition goes to a state whose longest string is exactly one longer, it becomes the new state’s link. Otherwise that state is split by cloning: the clone takes the shorter strings of the class, and transitions that pointed at the original along the suffix-link chain are redirected to the clone.

class SuffixAutomaton:
    def __init__(self, s):
        self.next = [{}]
        self.link = [-1]
        self.length = [0]
        last = 0
        for ch in s:
            cur = len(self.length)
            self.next.append({})
            self.length.append(self.length[last] + 1)
            self.link.append(0)
            p = last
            while p != -1 and ch not in self.next[p]:
                self.next[p][ch] = cur
                p = self.link[p]
            if p != -1:
                q = self.next[p][ch]
                if self.length[p] + 1 == self.length[q]:
                    self.link[cur] = q
                else:
                    clone = len(self.length)
                    self.next.append(dict(self.next[q]))
                    self.length.append(self.length[p] + 1)
                    self.link.append(self.link[q])
                    while p != -1 and self.next[p].get(ch) == q:
                        self.next[p][ch] = clone
                        p = self.link[p]
                    self.link[q] = self.link[cur] = clone
            last = cur

    def count_distinct_substrings(self):
        return sum(self.length[v] - self.length[self.link[v]]
                   for v in range(1, len(self.length)))

Counting distinct substrings follows directly from the length intervals: state v represents len[v] − len[link[v]] distinct strings, and every distinct substring belongs to exactly one state.

>>> SuffixAutomaton("banana").count_distinct_substrings()
15

The suffix-array formula gives the same 15 (21 substrings by position, minus LCP sum 6). Other uses:

• Substring test in O(m): follow transitions from the start state.
• Longest common substring of s and t in O(|s| + |t|): build the automaton of s, then walk t through it, following suffix links on a mismatch, and track the longest current match. This is the linear-time answer to the problem that dynamic programming solves in O(|s| · |t|).
• Number of occurrences of each substring (the size of its endpos class, computed by propagating counts along suffix links), the k-th lexicographically smallest substring, and the shortest string that is not a substring.

    def longest_common_substring(self, t):
        v = length = best = 0
        for ch in t:
            while v and ch not in self.next[v]:
                v = self.link[v]
                length = self.length[v]
            if ch in self.next[v]:
                v = self.next[v][ch]
                length += 1
            best = max(best, length)
        return best

SuffixAutomaton("xabcdey").longest_common_substring("zbcdq") is 3 (bcd).

Aho-Corasick: many patterns at once

Searching for k patterns of total length M by running a single-pattern matcher k times costs O(k·n + M). The Aho-Corasick automaton (Alfred Aho and Margaret Corasick, 1975) finds every occurrence of every pattern in one pass: O(n + M + z), where z is the number of matches reported. It generalizes KMP from one pattern to a trie of patterns.

Construction has three parts:

1. Trie. Insert every pattern into a trie (see Tries and range structures). Mark the node where each pattern ends.
2. Failure links. For each node, the failure link points to the node for the longest proper suffix of its string that is also a path in the trie. This is KMP’s prefix function, defined over the trie instead of one string, and it is computed in breadth-first order so that shorter strings are finished first.
3. Output links. Each node’s output list includes the patterns ending there plus those of its failure node, so that she also reports he.

from collections import deque

class AhoCorasick:
    def __init__(self, patterns):
        self.goto = [{}]
        self.fail = [0]
        self.out = [[]]
        for idx, p in enumerate(patterns):
            node = 0
            for ch in p:
                if ch not in self.goto[node]:
                    self.goto.append({})
                    self.fail.append(0)
                    self.out.append([])
                    self.goto[node][ch] = len(self.goto) - 1
                node = self.goto[node][ch]
            self.out[node].append(idx)
        self.lengths = [len(p) for p in patterns]
        queue = deque(self.goto[0].values())
        while queue:
            node = queue.popleft()
            for ch, child in self.goto[node].items():
                queue.append(child)
                if node:                       # children of the root fail to the root
                    f = self.fail[node]
                    while f and ch not in self.goto[f]:
                        f = self.fail[f]
                    self.fail[child] = self.goto[f].get(ch, 0)
                self.out[child] += self.out[self.fail[child]]

    def search(self, text):
        node = 0
        hits = []
        for i, ch in enumerate(text):
            while node and ch not in self.goto[node]:
                node = self.fail[node]
            node = self.goto[node].get(ch, 0)
            for idx in self.out[node]:
                hits.append((i - self.lengths[idx] + 1, idx))
        return hits

The textbook example from the original paper:

patterns: he(0) she(1) his(2) hers(3)

trie:  root -h-> 1 -e-> 2 (he) -r-> 8 -s-> 9 (hers)
            |        \-i-> 6 -s-> 7 (his)
            \-s-> 3 -h-> 4 -e-> 5 (she)

failure links: 5 ("she") -> 2 ("he"), so node 5 outputs she and he
               4 ("sh")  -> 1 ("h"),  9 ("hers") -> 3 ("s"), 7 ("his") -> 3 ("s")

>>> AhoCorasick(["he", "she", "his", "hers"]).search("ushers")
[(1, 1), (2, 0), (2, 3)]

That is she at 1, he at 2 and hers at 2. Copying output lists makes each node’s list explicit; with many nested patterns that copying can be quadratic in the worst case, and production implementations store a “dictionary suffix link” to the nearest node with output instead. Precomputing the full transition function (resolving the failure walk for every character at build time) turns the automaton into a DFA with one lookup per text character, at the cost of O(M·σ) memory. Aho-Corasick underlies multi-keyword scanners such as antivirus and intrusion-detection signature matching, and the -F fixed-strings mode of grep-family tools.

Classic string problems

Longest palindromic substring

Three approaches, in order of what is usually written:

Do not confuse it with Longest Palindromic Subsequence, which allows gaps and is the LCS of s and reverse(s), an O(n²) DP.

Longest common substring versus subsequence

A substring is contiguous; a subsequence keeps order but may skip characters. For a = "abcde" and b = "ace", the longest common subsequence is ace (length 3) but the longest common substring has length 1.

The substring DP: L[i][j] is the length of the longest common suffix of a[:i] and b[:j], which is L[i−1][j−1] + 1 when the characters match and 0 otherwise; the answer is the maximum entry. O(|a|·|b|) time, O(|b|) space with a rolling row:

def longest_common_substring_dp(a, b):
    best = 0
    prev = [0] * (len(b) + 1)
    for i in range(1, len(a) + 1):
        cur = [0] * (len(b) + 1)
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                cur[j] = prev[j - 1] + 1
                best = max(best, cur[j])
        prev = cur
    return best

The subsequence DP differs in one line: on a mismatch, L[i][j] = max(L[i−1][j], L[i][j−1]) instead of 0, and the answer is the last entry rather than the maximum. That difference, “reset” versus “carry”, is the whole distinction. LCS is developed fully, with reconstruction and the edit-distance family, in Dynamic programming. For long strings the substring problem has the linear-time suffix-automaton solution above; the subsequence problem has no known strongly subquadratic algorithm.

Regular expression matching

Regular Expression Matching with . (any character) and x* (zero or more x), matching the whole string. Let dp[i][j] be whether s[i:] matches p[j:]. If p[j+1] is *, either skip the starred pair (dp[i][j+2]) or, if s[i] matches p[j], consume one character and stay on the same pattern position (dp[i+1][j]). Otherwise s[i] must match p[j] and both advance.

def regex_match(s, p):
    n, m = len(s), len(p)
    dp = [[False] * (m + 1) for _ in range(n + 1)]
    dp[n][m] = True
    for i in range(n, -1, -1):
        for j in range(m - 1, -1, -1):
            first = i < n and p[j] in (s[i], ".")
            if j + 1 < m and p[j + 1] == "*":
                dp[i][j] = dp[i][j + 2] or (first and dp[i + 1][j])
            else:
                dp[i][j] = first and dp[i + 1][j + 1]
    return dp[0][0]

O(nm) time and space. regex_match("aab", "c*a*b") is True; regex_match("mississippi", "mis*is*p*.") is False. The naive recursive version without memoization is exponential, which is the same failure mode as backtracking regex engines on patterns like (a*)*b. Engines built on Thompson’s NFA simulation guarantee time linear in the text for a fixed pattern, but cannot support backreferences. Wildcard Matching (? and * matching any sequence) is the same DP with a different transition.

Word break

Word Break: can s be segmented into words from a dictionary? ok[i] is true when some word ends at i and ok is true where it starts. Iterating over the distinct word lengths rather than over all split points keeps it O(n · L) set lookups, where L is the number of distinct lengths (each lookup hashes a slice, so add a factor of the word length).

def word_break(s, words):
    words = set(words)
    lengths = {len(w) for w in words}
    ok = [True] + [False] * len(s)
    for i in range(1, len(s) + 1):
        ok[i] = any(L <= i and ok[i - L] and s[i - L:i] in words for L in lengths)
    return ok[-1]

word_break("applepenapple", ["apple", "pen"]) is True and word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]) is False. With a large dictionary a trie lets one scan from each i stop as soon as no word continues. Listing every segmentation (Word Break II) is backtracking with memoization and can produce exponentially many answers. Both are in Dynamic programming.

Choosing a matching algorithm

Summary