Concepts

String algorithms are techniques for working with sequences of characters quickly and correctly. Find-in-file, log search, search-box autocomplete and DNA sequence comparison all ask the same question: where does this run of characters occur? This chapter fixes the vocabulary used throughout the guide and starts from the simplest approach, naive matching, to show why better algorithms exist.

Vocabulary

A proper prefix is any prefix except the whole string. Borders are the heart of KMP, so it pays to get comfortable with them now.

Families of problems

Most string problems fall into four groups.

• Single-pattern search: find every occurrence of one pattern. Naive matching, KMP, the Z-algorithm, Rabin-Karp and Boyer-Moore live here.
• Multi-pattern search: find many patterns at once, such as a list of banned words. Aho-Corasick and Rabin-Karp with a hash set are the usual tools.
• Dictionary lookup: find all words in a word list that start with a given prefix. The trie is the classic structure.
• Text indexing: preprocess one text so that many queries run fast. Suffix arrays and FM-indexes cover this.

Naive matching

The obvious approach tries every starting position and compares character by character.

def naive_search(text: str, pattern: str) -> list[int]:
    n, m = len(text), len(pattern)
    hits = []
    for start in range(n - m + 1):
        j = 0
        while j < m and text[start + j] == pattern[j]:
            j += 1
        if j == m:
            hits.append(start)
    return hits


print(naive_search("abracadabra", "abra"))  # [0, 7]

For short inputs this is fine. But with text aaaa...a and pattern aaa...ab, almost all m characters match at every position before failing, so the worst case is O(n·m). The real problem is that each failure throws away what the comparisons just revealed and restarts from scratch at the next position. KMP stores that knowledge in a border table and reuses it; Rabin-Karp replaces most character comparisons with a hash comparison.

Computing borders by brute force

To build intuition, compute the longest border the slow way. The next chapter computes the same values for every prefix in O(m) with the prefix function.

def longest_border(s: str) -> int:
    for length in range(len(s) - 1, 0, -1):
        if s[:length] == s[-length:]:
            return length
    return 0


for word in ["abcab", "aaaa", "abcd", "ababa"]:
    print(word, longest_border(word))
# abcab 2 / aaaa 3 / abcd 0 / ababa 3

The longest border of ababa is aba, of length 3. Note that the prefix and the suffix may overlap.

When to write your own

Python's in, str.find, str.count and the re module are already highly optimized, so you will rarely rewrite KMP just to find a substring. Knowing the algorithms still matters when:

• you need information the built-ins do not expose: prefix-function values, the smallest period of a string, all borders
• the text arrives as a stream and cannot be passed in one piece
• the task goes beyond a single search: many patterns, prefix lookup, substring hashing
• you have to explain time complexity in a coding interview

A first Unicode caveat

What counts as one character is less obvious than it looks. A Python str is a sequence of code points, and one visible character may be several code points.

import unicodedata

a = "café"                       # single é (U+00E9)
b = "café"                 # e + combining acute accent (U+0301)
print(a == b, len(a), len(b))    # False 4 5
print(unicodedata.normalize("NFC", a) == unicodedata.normalize("NFC", b))  # True
print(len(a.encode("utf-8")))    # 5 (bytes)

Unless text and pattern are normalized to the same form (for example NFC) before searching, words that look identical to a person will not match. The last chapter returns to this.

Summary

• Text length is n, pattern length is m, and a border is a proper substring that is both a prefix and a suffix.
• Naive matching is O(n·m) in the worst case because it discards what each failed attempt learned.
• KMP and Z reuse earlier comparisons, Rabin-Karp compares hashes, and tries answer prefix queries over a dictionary.
• For Unicode text, decide on normalization and on what a "character" is before you search.