Z Algorithm

Z algorithm is a linear-time string matching and sequence analysis method within computation and algorithms that constructs the Z-array (or prefix-length array) of a string S[0 .. n − 1] in O(n) time and O(n) space. Popularized by Dan Gusfield in his 1997 monograph Algorithms on Strings, Trees, and Sequences as the foundational preprocessing step for the Apostolico–Giancarlo, Galil, and Boyer–Moore string-searching frameworks, the Z algorithm computes for every index k ∈ {1, …, n − 1} the length Z[k] of the longest common prefix (LCP) between the full string S and the suffix of S beginning at position k.

Whereas naive evaluation of Z[k] for all k requires Θ(n²) character comparisons on repetitive strings such as "aaaa...a", the Z algorithm achieves strict O(n) worst-case complexity by tracking the rightmost Z-box—the interval [L, R] with maximum right endpoint R such that the substring S[L .. R] matches a prefix of S. Whenever the current index k falls inside [L, R], the algorithm reuses the previously computed prefix value Z[k − L] at the aligned mirror offset k' = k − L, avoiding redundant character comparisons inside the known match window. Concatenating a search pattern P of length m and a text T of length n via a sentinel character P#T allows the Z algorithm to locate all occurrences of P in T in O(n + m) time, matching the asymptotic efficiency of the Knuth–Morris–Pratt algorithm.

Longest Common Prefix With Suffixes

Let S = S[0]S[1] … S[n − 1] be a zero-indexed string of length n over an alphabet Σ. For each position k ∈ {1, 2, …, n − 1}, the Z-value Z[k] is defined as the maximum integer ℓ ≥ 0 such that the prefix S[0 .. ℓ − 1] equals the substring S[k .. k + ℓ − 1]:

By convention, Z[0] is either left undefined (set to 0) or defined as n. Whenever Z[k] > 0, the closed index interval [k, k + Z[k] − 1] is called the Z-box starting at position k, representing a contiguous substring of length Z[k] that is a verbatim copy of the prefix S[0 .. Z[k] − 1].

The Rightmost Z-Box Invariant [L, R]

As the algorithm scans left to right from k = 1 to n − 1, it maintains two integer pointers L and R (initialized to L = 0, R = 0) representing the start and inclusive end of the Z-box with the largest right endpoint R discovered among all positions 1 ≤ i < k. Because S[L .. R] is a prefix match of S, every character inside the active Z-box satisfies the index-shift identity:

Consequently, when evaluating a new position k ≤ R, the suffix of the active Z-box beginning at k—namely S[k .. R] of length β = R − k + 1—is guaranteed to equal the substring S[k' .. R − L] beginning at the mirror index k' = k − L < k, where Z[k'] has already been computed.

Three-Case Evaluation at Position k

At each index k ∈ {1, …, n − 1}, the Z algorithm branches into one of three mutually exclusive cases based on the relation between k, the right boundary R, and the precomputed mirror value Z[k − L]:

1. Case 1 (Outside the Active Z-Box: k > R): No previously discovered Z-box covers index k. The algorithm resets L ← k and R ← k, then compares characters S[R − L] and S[R] sequentially while they match, setting Z[k] ← R − L and adjusting R ← R − 1 to denote the inclusive right boundary.
2. Case 2a (Inside the Z-Box with Strictly Contained Mirror Match: k ≤ R and Z[k − L] < R − k + 1): Let k' = k − L and let β = R − k + 1 be the remaining length of the active Z-box. Because Z[k'] < β, the prefix match at k' terminates at a mismatch character S[Z[k']] ≠ S[k' + Z[k']] that lies strictly inside S[0 .. R − L]. By the Z-box identity S[k .. R] = S[k' .. R − L], the match starting at k must copy the same characters and hit the identical mismatch after Z[k'] steps. Thus the algorithm sets Z[k] ← Z[k − L] in O(1) time with zero character comparisons, leaving [L, R] unchanged.
3. Case 2b (Inside the Z-Box Touching or Exceeding the Boundary: k ≤ R and Z[k − L] ≥ R − k + 1): The Z-box identity guarantees that at least the first β = R − k + 1 characters starting at k match S[0 .. β − 1], so Z[k] ≥ β. However, because characters beyond index R have never been inspected, the match at k may continue past R. The algorithm sets L ← k and begins explicit character comparisons directly at index R + 1 against S[R + 1 − k], advancing R for each match and updating Z[k].

Amortized Counting of Character Comparisons

Why does the entire loop over k = 1, …, n − 1 perform at most 2n character comparisons in the worst case? Observe that Case 2a performs zero character comparisons, while in both Case 1 and Case 2b every explicit character comparison is performed at a text position ≥ R:

• Successful character comparison (S[R − L] = S[R]): Increments the right boundary pointer R by 1. Because R starts at 0, never decreases, and cannot exceed n − 1, at most n successful character comparisons can occur across the entire execution.
• Unsuccessful character comparison (S[R − L] ≠ S[R]): Immediately terminates the while loop for the current index k. Because the outer loop runs n − 1 times, at most n − 1 mismatch comparisons can occur in total.

Summing both outcomes proves that the Z algorithm performs at most 2n − 1 character comparisons, running in O(n) time.

Linear-Time Pattern Search Without Full-Text Space Allocation

To find all occurrences of a pattern P[0 .. m − 1] inside a text T[0 .. n − 1] where # ∉ Σ, one forms the concatenated string S = P · # · T of length m + 1 + n. Because the sentinel character # appears nowhere in P or T, no Z-value can ever exceed m, and any index k > m with Z[k] = m identifies an occurrence of P in T starting at text offset k − (m + 1). Moreover, in streaming applications where n ≫ m, only the pattern's Z-array Z_P[0 .. m − 1] needs to be stored in memory: the scan over T updates scalar variables L and R on the fly without storing Z[k] for k > m, reducing auxiliary memory from O(n + m) to O(m).

String Compression, Tandem Repeats, and Comparative Genomics

The Z-array directly resolves string periodicity and tandem-repeat problems: a string S of length n has a shortest period of length p if and only if p is the smallest divisor of n satisfying p + Z[p] = n. In bioinformatics and computational genomics, Main and Lorentz's O(n log n) divide-and-conquer algorithm invokes forward and reverse Z-array computations at each recursion level to enumerate all maximal tandem repeats (microsatellites and minisatellites) in chromosomal DNA sequences, while read-alignment pipelines use Z-boxes alongside suffix arrays and Burrows–Wheeler transform indexes for rapid seed extension.

How are the Z-array and the KMP prefix-function (π-array) mathematically related?

For a string S, the Z-value Z[i] measures the longest prefix of S starting at index i, whereas the Knuth–Morris–Pratt algorithm failure function π[j] measures the longest proper prefix of S[0 .. j] that is a suffix ending at index j. Either array can be converted into the other in O(n) time: specifically, π[i + Z[i] − 1] ≥ Z[i] for every Z-box [i, i + Z[i] − 1], so taking the maximum over all Z-boxes covering each right endpoint reconstructs the entire π-array in linear time.

What happens if we omit the sentinel character "#" when concatenating P and T?

If S = P · T is formed without a unique separator #, a prefix match starting in T can extend across the boundary between P and T, yielding Z[k] > m. The algorithm remains correct and still runs in O(n + m) time: an occurrence of P at index k ≥ m is simply indicated by the inequality Z[k] ≥ m rather than the equality Z[k] = m, which avoids expanding the alphabet Σ when processing packed binary or 2-bit DNA strings.

How does the Z algorithm assist the Boyer–Moore good-suffix preprocessing rule?

Computing the Boyer–Moore good-suffix shift table requires knowing, for every position i in pattern P, the length N[i] of the longest suffix of P that also ends at position i. Reversing the pattern to form P^R, running the Z algorithm on P^R in O(m) time, and reversing the resulting Z-array yields the suffix-length array N[i] = Z_P^R[m − 1 − i] directly.

1. Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology (Chapter 1: Exact Matching: Fundamental Preprocessing and First Algorithms). Cambridge University Press. https://doi.org/10.1017/CBO9780511574931
2. Main, M. G., & Lorentz, R. J. (1984). "An O(n log n) algorithm for finding all repetitions in a string." Journal of Algorithms, 5(3), 422–432. https://doi.org/10.1016/0196-6774(84)90021-X90021-X)
3. Apostolico, A., & Giancarlo, R. (1986). "The Boyer–Moore–Galil string searching strategies revisited." SIAM Journal on Computing, 15(1), 98–105. https://doi.org/10.1137/0215007
4. Crochemore, M., Hancart, C., & Lecroq, T. (2007). Algorithms on Strings. Cambridge University Press. https://doi.org/10.1017/CBO9780511546853