Z Algorithm
The Z algorithm computes, for each position i in a string S of length n, the length of the longest substring starting at S[i] that is also a prefix of S. T...
Linear Pattern Matching Using the Z-Array
The Z algorithm computes, for each position i in a string S of length n, the length of the longest substring starting at S[i] that is also a prefix of S. The resulting array Z has Z[0] defined as the length of S itself (or left undefined by convention), and for i greater than zero, Z[i] is the length of the longest common prefix of S and S[i..n-1]. The entire Z array can be computed in O(n) time.
The algorithm maintains a window [L, R] representing the rightmost Z-box seen so far, where a Z-box is a substring S[L..R] that is also a prefix of S. For each new position i, if i is inside the current Z-box (i less than or equal to R), we can use previously computed values to start from a known lower bound without re-examining characters. If i is outside the box, we start a naive match from scratch. The key property is that the right boundary R only ever moves forward, so the total number of character comparisons across all positions is at most 2n, giving O(n) overall.
To use the Z algorithm for pattern matching, concatenate the pattern P, a separator character that does not appear in either string (often a dollar sign), and the text T, forming the combined string C of length m plus 1 plus n. Compute the Z array of C. Any position i in C greater than m where Z[i] equals m corresponds to an occurrence of P starting at position i minus m minus 1 in the text T.
This approach avoids the failure function construction required by KMP while achieving the same O(n plus m) time. Some practitioners find the Z algorithm slightly more intuitive to reason about because the Z array has a direct geometric meaning: it represents the reach of prefix matches from each position.
The Z algorithm also has applications beyond pattern matching. It can determine the number of distinct substrings of a string, find the lexicographically smallest rotation of a string, and help in computing string periodicity.
Comparison with KMP: both achieve O(n plus m) time. KMP's failure function is closely related to the Z array; in fact, the Z array can be converted to the KMP failure function and vice versa in O(m) time. Choice between them is largely a matter of preference and coding style.
Worked example: S equals "aabxaa". Z array: Z[0] undefined, Z[1] equals 1 (both start with 'a', then mismatch at second character), Z[2] equals 0, Z[3] equals 0, Z[4] equals 2 (S[4..5] equals "aa", which matches the prefix "aa" of length 2). For pattern matching with P equals "aa", construct "aa$aabxaa" and compute Z; positions with Z value 2 (at index 6 and 7 mapping back to text position 4) reveal the match.
Interview tip: if you know the Z algorithm, mention it as an alternative to KMP. Knowing two linear-time pattern matching algorithms shows depth. Many interviewers are not familiar with the Z algorithm and will be impressed.