Introduction

Linear-time substring matching is possible when the algorithm avoids rechecking characters that it already knows how to reason about. The naive approach restarts too much work after mismatches, which can make it slow on repetitive input. Algorithms such as Knuth-Morris-Pratt and the Z algorithm achieve O(n + m) matching by preprocessing structure and reusing it during the scan.

Why the Naive Search Repeats Work

The naive method tries every alignment of the pattern against the text and compares characters until a mismatch appears. On repetitive inputs, many of those comparisons repeat work the algorithm effectively already learned.

For example, if a long prefix matched and then failed late, the naive method often restarts from the next text position and checks many of the same characters again.

To achieve linear time, the algorithm needs memory about partial matches so it can skip impossible alignments.

Use Knuth-Morris-Pratt

KMP preprocesses the pattern into an lps table. Each table entry stores the length of the longest proper prefix that is also a suffix for the pattern prefix ending at that position.

Build the lps table

1def build_lps(pattern: str) -> list[int]:
2    lps = [0] * len(pattern)
3    length = 0
4    i = 1
5
6    while i < len(pattern):
7        if pattern[i] == pattern[length]:
8            length += 1
9            lps[i] = length
10            i += 1
11        elif length > 0:
12            length = lps[length - 1]
13        else:
14            lps[i] = 0
15            i += 1
16
17    return lps

Search the text with KMP

1def kmp_search(text: str, pattern: str) -> list[int]:
2    if not pattern:
3        return list(range(len(text) + 1))
4
5    lps = build_lps(pattern)
6    matches = []
7    i = 0
8    j = 0
9
10    while i < len(text):
11        if text[i] == pattern[j]:
12            i += 1
13            j += 1
14            if j == len(pattern):
15                matches.append(i - j)
16                j = lps[j - 1]
17        elif j > 0:
18            j = lps[j - 1]
19        else:
20            i += 1
21
22    return matches
23
24print(kmp_search("ABABDABACDABABCABAB", "ABABCABAB"))

KMP is linear because the text index never moves backward. The pattern index is adjusted using the precomputed structure rather than restarting from zero every time.

The Z Algorithm Gives Another Linear Approach

The Z algorithm computes, for each position, the length of the longest prefix match starting there. For pattern searching, you combine the pattern, a separator, and the text, then compute Z values on the combined string.

1def z_values(s: str) -> list[int]:
2    z = [0] * len(s)
3    left = right = 0
4
5    for i in range(1, len(s)):
6        if i <= right:
7            z[i] = min(right - i + 1, z[i - left])
8
9        while i + z[i] < len(s) and s[z[i]] == s[i + z[i]]:
10            z[i] += 1
11
12        if i + z[i] - 1 > right:
13            left, right = i, i + z[i] - 1
14
15    return z
16
17def z_search(text: str, pattern: str) -> list[int]:
18    if not pattern:
19        return list(range(len(text) + 1))
20
21    joined = pattern + "$" + text
22    z = z_values(joined)
23    result = []
24    pat_len = len(pattern)
25
26    for i, value in enumerate(z):
27        if value == pat_len:
28            result.append(i - pat_len - 1)
29
30    return result
31
32print(z_search("abracadabra", "abra"))

Like KMP, the Z algorithm avoids repeated character comparisons by reusing information from earlier matches.

What Linear Time Really Means Here

For text length n and pattern length m, linear-time matching usually means O(n + m). The preprocessing of the pattern takes linear time in m, and the scan of the text takes linear time in n.

That is different from the naive worst case, which can degrade toward O(nm) on adversarial input.

This improvement matters most on large or repetitive text where repeated backtracking becomes expensive.

Edge Cases Still Matter

Even with a mathematically good algorithm, you still need to define behavior for:

• empty pattern
• pattern longer than the text
• overlapping matches
• byte-wise versus Unicode-normalized comparison

Those are not afterthoughts. They are part of the real contract of the search function.

Common Pitfalls

The biggest pitfall is claiming linear complexity while implementing a search that still restarts too much work after mismatches.

Another common issue is building the lps or Z table incorrectly. A small preprocessing bug can make the runtime look fast while silently missing matches.

People also forget to test repetitive or adversarial inputs, which are exactly the cases that separate linear algorithms from naive ones.

Summary

• Linear-time substring matching works by avoiding repeated comparisons after mismatches.
• KMP achieves this with the lps prefix-suffix table.
• The Z algorithm provides another exact matching approach with the same linear-time guarantee.
• The target complexity is O(n + m) for text length n and pattern length m.
• Correct preprocessing and edge-case handling matter as much as the high-level algorithm choice.