String Algorithms: KMP, Rolling Hash, Tries and Suffix Arrays

#The Matching Problem

#Naive Matching and Its Worst Case

The plain method tries every alignment. At each one it compares letters left to right and stops at the first disagreement. It needs no extra memory beyond the answer, so the space is O(1).

def naive_find_all(text, pattern):
    """Every start index where pattern occurs, plus the number of character comparisons.

    Time O(n·m) worst case, extra space O(1) beyond the answer.
    """
    n, m = len(text), len(pattern)
    hits, compares = [], 0
    for start in range(n - m + 1):
        j = 0
        while j < m:
            compares += 1
            if text[start + j] != pattern[j]:
                break
            j += 1
        if j == m:
            hits.append(start)
    return hits, compares


print(naive_find_all("aaaaab", "aab"))
print(naive_find_all("the cat sat on the mat", "at"))
print(naive_find_all("abcdefghijkl", "xyz"))
# Output:
# ([3], 12)
# ([5, 9, 20], 24)
# ([], 10)

On ordinary text most alignments fail on the first or second letter, so the cost is close to n. Look at the last line: a pattern whose first letter never appears costs one comparison per alignment. The bad case is a text full of near misses, where each alignment gets far into the pattern before it fails. That costs up to m per alignment.

A slow example from real life: a text of 1,000 letters a and a pattern of 499 letters a followed by one b. Each of the 501 alignments matches 499 letters, and then the b fails: 500 comparisons each. That is 250,500 comparisons for a text of 1,000 letters. Both n and m grow, and the cost is their product, O(n·m).

#KMP: Never Re-read the Text

Now the code. The search below is the same loop run against the text instead of the pattern. For each text letter, try to extend the current match length k. On a mismatch, fall back along the borders. When k reaches m, record a hit and fall back once, so overlapping hits are found.

def prefix_function(p):
    """pi[i] = length of the longest border of p[:i+1].

    Time O(m), space O(m).
    """
    pi = [0] * len(p)
    k = 0
    for i in range(1, len(p)):
        while True:
            if p[i] == p[k]:
                k += 1
                break
            if k == 0:
                break
            k = pi[k - 1]              # fall back to the next shorter border
        pi[i] = k
    return pi


def kmp_find_all(text, p):
    """All start indexes of p in text, plus the number of character comparisons.

    Time O(n + m), extra space O(m).
    """
    if not p:
        return [], 0
    pi = prefix_function(p)
    hits, compares, k = [], 0, 0
    for i, ch in enumerate(text):
        while True:
            compares += 1
            if ch == p[k]:
                k += 1
                break
            if k == 0:
                break
            k = pi[k - 1]
        if k == len(p):
            hits.append(i - k + 1)
            k = pi[k - 1]              # keep going: the next match may overlap
    return hits, compares


for word in ["ababc", "aabaaab", "abcabcabd", "aaaa"]:
    print(word, prefix_function(word))
print(kmp_find_all("abababc", "ababc"), naive_find_all("abababc", "ababc"))
print(kmp_find_all("aaaaaa", "aa"))
# Output:
# ababc [0, 0, 1, 2, 0]
# aabaaab [0, 1, 0, 1, 2, 2, 3]
# abcabcabd [0, 0, 0, 1, 2, 3, 4, 5, 0]
# aaaa [0, 1, 2, 3]
# ([2], 8) ([2], 11)
# ([0, 1, 2, 3, 4], 6)

So over the whole search there are at most n fall-backs. Each text letter also gets one comparison that either extends k or gives up at k = 0. That makes at most 2n comparisons. The table build is the same argument with m. The total is O(n + m) time, and the table needs O(m) space.

Now the adversarial case from before, a text of 1,000 letters a and the pattern of 499 letters a then b, where the naive method needed 250,500 comparisons.

text = "a" * 1000
pattern = "a" * 499 + "b"
hits, compares = kmp_find_all(text, pattern)
print(hits, compares)
print(naive_find_all(text, pattern)[1])
# Output:
# [] 1501
# 250500

Two limits of KMP are worth knowing. It does not shrink the answer: a text of all a's still has one occurrence per index. And its win is largest on repetitive input. On random text the naive method also fails early, so KMP's table mostly buys a guarantee. Its other real advantage is that it reads the text in one pass with no backing up, so it works on a stream you cannot rewind.

#Rabin-Karp: Compare Fingerprints First

KMP avoids work with careful bookkeeping. Rabin-Karp takes a different road: compare a cheap number first, and compare the letters only when the numbers agree.

def rabin_karp(text, pattern, base=256, mod=1_000_000_007):
    """All start indexes of pattern in text, plus (hash matches, character comparisons).

    Expected time O(n + m) if hashes behave like random numbers; worst case O(n·m). Space O(1).
    """
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return [], 0, 0
    high = pow(base, m - 1, mod)               # weight of the leading character
    want = window = 0
    for i in range(m):
        want = (want * base + ord(pattern[i])) % mod
        window = (window * base + ord(text[i])) % mod
    hits, hash_matches, compares = [], 0, 0
    for start in range(n - m + 1):
        if window == want:                     # equal hashes: maybe a match, maybe a collision
            hash_matches += 1
            ok = True
            for j in range(m):
                compares += 1
                if text[start + j] != pattern[j]:
                    ok = False
                    break
            if ok:
                hits.append(start)
        if start + m < n:                      # slide: drop text[start], add text[start + m]
            window = ((window - ord(text[start]) * high) * base + ord(text[start + m])) % mod
    return hits, hash_matches, compares


print(rabin_karp("the cat sat on the mat", "at"))
print(rabin_karp("abracadabra", "abra"))
# Output:
# ([5, 9, 20], 3, 6)
# ([0, 7], 2, 8)

print(rabin_karp("abracadabra", "abra", mod=7))
print(rabin_karp("abracadabra", "abra", mod=101))
# Output:
# ([0, 7], 5, 13)
# ([0, 7], 2, 8)

The answer is the same, but with modulus 7 there were 5 hash matches, 2 real and 3 spurious, and 13 comparisons instead of 8. The spurious ones cost extra work and never cost correctness.

Now the cost, with its assumptions stated. If the hash behaves like a random number modulo q, a window that is not a match collides with probability about 1/q. Over n windows that is about n/q spurious hits, each costing up to m comparisons. With q near a billion that is negligible, so the expected time is O(n + m): the setup, plus O(1) per slide. This is an expectation under an assumption about the hash, not a guarantee.

Rabin-Karp has one strength that KMP lacks. It extends to many patterns of the same length: put all their hashes in a set, and test each window against the set. It also extends to two-dimensional grids of letters.

#The Z-Algorithm in Brief

The Z-array is built in O(n) time and O(n) space by keeping the rightmost match window found so far. Inside that window, a position copies the answer from its mirror image near the start, then extends only as far as needed. It is the same amortized idea as KMP: the right edge of the window only moves forward.

KMP and Z solve the same problems, and the two arrays carry the same information in different forms. Use whichever you can write correctly under pressure. Z is often easier to explain and to debug; the prefix function is better when the text arrives as a stream.

#Boyer-Moore-Horspool: Skip Ahead

def horspool(text, p):
    """Boyer-Moore-Horspool: all start indexes plus the number of character comparisons.

    Typically skips most of the text, worst case O(n·m). Extra space O(alphabet size).
    """
    n, m = len(text), len(p)
    jump = {ch: m - 1 - i for i, ch in enumerate(p[:-1])}     # last position of each letter
    hits, compares, start = [], 0, 0
    while start <= n - m:
        j = m - 1
        while j >= 0:                          # compare from the END of the pattern
            compares += 1
            if text[start + j] != p[j]:
                break
            j -= 1
        if j < 0:
            hits.append(start)
        start += jump.get(text[start + m - 1], m)
    return hits, compares


sentence = "the quick brown fox jumps over the lazy dog"
print(horspool(sentence, "lazy"))
print(naive_find_all(sentence, "lazy"))
print(horspool("a" * 30, "b" + "a" * 5), naive_find_all("a" * 30, "b" + "a" * 5))
# Output:
# ([35], 14)
# ([35], 43)
# ([], 150) ([], 25)

On ordinary text Horspool made 14 comparisons where the naive method made 43, and 14 is far fewer than the 43 letters of the text. It can be sublinear, which none of the earlier methods can be.

The price is the worst case. In the last line the text is 30 letters a and the pattern is one b followed by five a's. Horspool compares from the end, so it matches five a's before the b fails, and the jump is only 1 because a occurs in the pattern. That costs 150 comparisons. The naive method, which looks at the front first, fails at once and spends only 25. The worst case of Horspool is O(n·m).

The full Boyer-Moore adds a second rule, the good-suffix rule, that gives linear time in the worst case with extra care. It is subtle, and Horspool is the version worth remembering. The lesson to take away: skipping beats comparing when mismatches are common and the alphabet is large.

#Many Patterns at Once: Tries and Aho-Corasick

The cost: building the machine takes time proportional to the total length of all the words, and the memory is the same order. Searching takes O(n + k) time, where k is the number of occurrences reported, and does not depend on the number of words. Notice the k: a text where every position matches many words can have a very large output, and reporting is not free.

We only describe it here and do not write the full code. If you can write KMP and a trie, you can write Aho-Corasick: build the trie, compute failure links with a breadth-first pass, then run the search loop.

#Suffix Arrays: Index the Text Once

Why sort? Every occurrence of a pattern is a prefix of some suffix. All suffixes that start with the same pattern sit side by side in sorted order, in one block. So we binary search for the start and the end of that block. Each probe compares only m letters, so one query costs O(m log n) plus the number of hits.

from bisect import bisect_left, bisect_right


def suffix_array(s):
    """Sorted suffix start indexes. This toy version is slow: O(n² log n) time, O(n²) memory.

    Real builders reach O(n log n), or O(n) with SA-IS, using O(n) memory.
    """
    return sorted(range(len(s)), key=lambda i: s[i:])


def sa_find(s, sa, p):
    """All start indexes of p in s, by binary search. O(m log n) plus the hits."""
    cut = lambda i: s[i:i + len(p)]            # compare only the first m letters
    lo = bisect_left(sa, p, key=cut)
    hi = bisect_right(sa, p, key=cut)
    return sorted(sa[lo:hi])


def longest_repeat(s, sa):
    """Longest substring that occurs twice: the biggest shared start of two neighbours."""
    best = ""
    for a, b in zip(sa, sa[1:]):
        k = 0
        while a + k < len(s) and b + k < len(s) and s[a + k] == s[b + k]:
            k += 1
        if k > len(best):
            best = s[a:a + k]
    return best


word = "banana"
sa = suffix_array(word)
print(sa, [word[i:] for i in sa])
print(sa_find(word, sa, "ana"), sa_find(word, sa, "a"), sa_find(word, sa, "x"))
print(longest_repeat(word, sa))
# Output:
# [5, 3, 1, 0, 4, 2] ['a', 'ana', 'anana', 'banana', 'na', 'nana']
# [1, 3] [1, 3, 5] []
# ana

The trade is clear. A suffix array costs O(n) memory (as integers) and a long build, and then answers each pattern in O(m log n). It is the right tool when the text is big and fixed, such as a genome or a document collection.

#Longest Palindromic Substring

Here is the idea. Every palindrome has a center: a letter for odd length, a gap between two letters for even length. A string of n letters has 2n - 1 centers. From each center, expand outward while the two outer letters agree. The first disagreement ends that center. Keep the longest result. A palindrome's own center always finds it, so nothing is missed.

def longest_palindrome(s):
    """Longest palindromic substring and the number of letter comparisons.

    Time O(n²) worst case, space O(1) beyond the answer.
    """
    best_lo, best_hi, compares = 0, 0, 0
    for center in range(2 * len(s) - 1):
        lo = center // 2
        hi = lo + center % 2                   # equal to lo for odd length, lo + 1 for even
        while lo >= 0 and hi < len(s):
            compares += 1
            if s[lo] != s[hi]:
                break
            lo -= 1
            hi += 1
        if hi - lo - 1 > best_hi - best_lo:
            best_lo, best_hi = lo + 1, hi
    return s[best_lo:best_hi], compares


for text in ["babad", "cbbd", "abcdefgh", "a" * 10]:
    print(text, longest_palindrome(text))
# Output:
# babad ('bab', 13)
# cbbd ('bb', 10)
# abcdefgh ('a', 21)
# aaaaaaaaaa ('aaaaaaaaaa', 55)

Keep the palindrome that reaches furthest right, with its center and right edge. A new center inside that palindrome has a mirror image on the left side, and by symmetry it starts with the mirror's radius, capped at the right edge. It then expands only if it reaches beyond that edge. The right edge only moves forward, so the expansion work is amortized over the whole string.

We only describe it. Expand-around-center is what interviews usually expect, with Manacher as the follow-up.

Do not confuse three neighbours. The longest palindromic substring (letters side by side) is this section. The longest palindromic subsequence (letters may skip) is a dynamic programming problem with an O(n²) table. Counting how many palindromic pieces exist uses the same expansion, adding one per successful step.

#Edit Distance: A Pointer to DP

There is no clever skipping trick here. The problem has the shape that dynamic programming solves: the answer for two prefixes comes from the answers for slightly shorter prefixes, one table cell at a time. The table has n times m cells, so time and space are both O(n·m), and keeping only two rows cuts the space to O(m).

#Which Tool? A Decision Table

Ask four questions in order. Is the text fixed while you ask many questions? Is there one pattern or many? Do you need the guarantee, or is an expected cost fine? Is the pattern exact?

#Where This Shows Up

• Python's own in, find and count run tuned C code. As a rule, use them first. CPython's search mixes ideas from this lesson, such as skipping ahead using the last letter of the window, and its newer versions add a guard against the bad worst case.

• Editors and command-line search tools look for one pattern in files, and tools that match many keywords at once use ideas close to Aho-Corasick.

• File-sync tools can use a rolling checksum, the cousin of the rolling hash here, to find blocks that match between two versions of a file even when bytes were inserted in the middle. Tools that look for copied text can also fingerprint windows with rolling hashes.

• Genome tools use suffix-array-style indexes so a read of a few hundred letters can be located inside a genome of billions. Some teams also use suffix arrays to find repeated passages in large text collections before training a language model.

• Spell checkers, fuzzy search and speech scoring use edit distance. Some tokenizers for language models use trie-like structures to find the longest known piece at a position.

#Common Mistakes

#Try It: Five Problems

The ladder goes from easy to adversarial. Every problem returns a counter, so you can watch the cost grow or stay flat. Problem 1 is the naive search. Problem 2 builds the prefix table and counts its work. Problem 3 uses it to search.

Problem 4 has a bug in the rolling hash. Problem 5 asks you to reuse the prefix function for a new job. Test each with an empty pattern, a pattern longer than the text, a text of one repeated letter, and a long input.

#Recap

Matching a pattern of m letters in a text of n letters has n - m + 1 alignments. The naive method costs O(n·m) in the worst case, which a near-miss text such as many a's makes real.

KMP stores the prefix function, the longest border of each prefix, so a mismatch falls back along borders and the text pointer never moves left. Search is O(n + m) by an amortized argument on k, and the table needs O(m) space.

Rabin-Karp compares rolling hashes and checks the letters only on an equal hash. It is expected O(n + m) if hashes behave randomly, and O(n·m) in the worst case. The Z-algorithm is KMP's twin, and Horspool skips ahead using the last letter of the window. Aho-Corasick adds failure links to a trie to search many words in one pass. A suffix array sorts all suffixes of a fixed text and answers each query in O(m log n).

The longest palindromic substring takes O(n²) by expanding around 2n - 1 centers, and Manacher's idea makes it O(n). Closeness instead of equality is edit distance, an O(n·m) dynamic programming table.