Complexity

This chapter analyzes time and space in terms of text length n, pattern length m and alphabet size σ. String algorithms often behave very differently on average and in the worst case, so both are covered.

Naive matching

There are n - m + 1 starting positions and up to m comparisons at each, so the worst case is O(n·m). Text aaaa...a with pattern aa...ab is the textbook bad input. On the other hand, with a large alphabet and text that looks random, most attempts fail on the first or second character, so the average is close to O(n). Extra memory is O(1).

Why KMP is linear

KMP's inner while loop looks like a nested loop, yet the total cost is O(n + m). An amortized argument shows why.

1. k grows by at most 1 per text character, so its total increase is at most n.
2. Every iteration of the while loop decreases k by at least 1, and k never drops below 0.
3. Therefore the while loop cannot run more times in total than k ever increased, which is at most n.

The same argument gives O(m) for the prefix function. Space is O(m) for the pi array, and because the text is read strictly left to right, KMP works unchanged on streams.

Counting comparisons makes the difference concrete.

def naive_comparisons(text: str, pattern: str) -> int:
    count = 0
    for s in range(len(text) - len(pattern) + 1):
        for j in range(len(pattern)):
            count += 1
            if text[s + j] != pattern[j]:
                break
    return count


def kmp_comparisons(text: str, pattern: str) -> int:
    pi = [0] * len(pattern)
    k = 0
    for i in range(1, len(pattern)):
        while k > 0 and pattern[i] != pattern[k]:
            k = pi[k - 1]
        if pattern[i] == pattern[k]:
            k += 1
        pi[i] = k
    count, k = 0, 0
    for ch in text:
        while True:
            count += 1
            if ch == pattern[k]:
                k += 1
                break
            if k == 0:
                break
            k = pi[k - 1]
        if k == len(pattern):
            k = pi[k - 1]
    return count


text, pattern = "a" * 10_000, "a" * 99 + "b"
print(naive_comparisons(text, pattern))  # 990100
print(kmp_comparisons(text, pattern))    # 19901

On the same input the naive method makes about 990,000 comparisons and KMP about 20,000. KMP never exceeds 2n comparisons during the scan.

Rabin-Karp

Rolling the hash costs O(1) per window, so hashing is O(n + m) overall. Each hash hit costs an O(m) check, so with occ real occurrences and rare collisions the expected time is O(n + m + occ·m). If the modulus is small, or the input was crafted to collide, almost every window needs a check and the worst case becomes O(n·m). Space is O(1).

Rabin-Karp shines when you look for many patterns of the same length. Put the pattern hashes in a set and each window needs one set lookup, so k patterns cost O(n + k·m) expected time.

def multi_rabin_karp(text: str, patterns: set[str], base: int = 911382323, mod: int = (1 << 61) - 1) -> list[tuple[int, str]]:
    m = len(next(iter(patterns)))
    assert all(len(p) == m for p in patterns)
    def h(s: str) -> int:
        v = 0
        for ch in s:
            v = (v * base + ord(ch)) % mod
        return v
    wanted = {h(p) for p in patterns}
    high = pow(base, m - 1, mod)
    out, cur = [], h(text[:m])
    for i in range(len(text) - m + 1):
        if cur in wanted and text[i:i + m] in patterns:
            out.append((i, text[i:i + m]))
        if i + m < len(text):
            cur = ((cur - ord(text[i]) * high) * base + ord(text[i + m])) % mod
    return out


print(multi_rabin_karp("the cat sat on the mat", {"cat", "mat", "dog"}))
# [(4, 'cat'), (19, 'mat')]

Tries

Insert, lookup and walking to a prefix all cost O(L) for a key of length L, no matter how many words are stored. Autocomplete adds the number of nodes visited while collecting results. With N total characters there are at most N nodes, so space is O(N·σ) with fixed-size child arrays or O(N) with hash maps. When words share few prefixes the node count explodes, which is why compressed tries (radix trees) merge chains of single-child nodes.

A sorted list plus binary search also answers prefix queries, and uses far less memory when the word list rarely changes.

import bisect

words = sorted(["car", "cart", "cat", "dog", "dot"])
lo = bisect.bisect_left(words, "ca")
hi = bisect.bisect_left(words, "cb")   # the next prefix after "ca"
print(words[lo:hi])  # ['car', 'cart', 'cat']

Comparison

Summary

• KMP and Z are linear even in the worst case; the amortized argument bounds total decreases by total increases.
• Rabin-Karp is linear in expectation but can degrade to O(n·m) under heavy collisions.
• Trie operations depend only on key length, but memory is costly, so consider radix trees or a sorted list too.