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 overall. Each hash hit costs an check, so with real occurrences and rare collisions the expected time is . If the modulus is small, or the input was crafted to collide, almost every window needs a check and the worst case becomes . Space is .