The Z-Algorithm: A Linear-Time Masterclass in Pattern Searching

The Z-algorithm is a highly efficient linear-time algorithm for pattern searching, providing a significant improvement over the naive O(m × n) approach. Its primary innovation is the Z-array, a data structure that is pre-computed for a given string. For a string S, the Z-array's value at index i, Z[i], represents the length of the longest substring starting at i that also matches a prefix of S. The true power of the algorithm lies in its ability to construct this Z-array in linear time. It achieves this by maintaining a 'Z-box'—an interval [L, R] that tracks the rightmost prefix-match found so far. By using information within this box, the algorithm can often determine Z-values for new indices with few or no character comparisons, thus avoiding redundant work. This clever reuse of information is what guarantees the linear-time performance. For practical pattern searching, the pattern P and text T are concatenated into a new string `P + '$' + T`. After computing the Z-array for this new string, any entry in the array that equals the length of the pattern P corresponds to an occurrence of P in T. This makes the Z-algorithm a foundational tool in areas requiring fast string matching, such as bioinformatics, text editing, and data compression.

1. Introduction: The Quest for Efficient Pattern Searching

The problem of pattern searching is fundamental in computer science: given a text string T and a pattern string P, find all occurrences of P within T. A straightforward, or 'naive', approach would be to slide the pattern P across the text T one character at a time, and for each position, check if the pattern matches the corresponding substring of the text. While simple to understand, this method has a worst-case time complexity of O(m × n), where n is the length of the text and m is the length of the pattern. For large texts, such as a genome sequence or a large document, this is prohibitively slow.

Enter the Z-algorithm, a brilliant and elegant algorithm that solves this problem in linear time, O(n + m). It achieves this remarkable efficiency by pre-processing the string in a way that avoids redundant comparisons, a common theme in advanced string algorithms like KMP (Knuth-Morris-Pratt).

2. The Core Concept: The Z-Array

The heart of the Z-algorithm is the Z-array. For a given string S of length N, its Z-array is an array Z of the same length, where each entry Z[i] stores a specific value.

Definition: Z-value

The Z-value Z[i] is the length of the longest substring of S that starts at index i and is also a prefix of S.

By convention, Z[0] is set to 0, as comparing the entire string with itself is a trivial case that doesn't provide useful information for the algorithm's mechanics.

Example: Computing a Z-Array Let's consider the string S = "aabcaabxaaaz" of length 12.

Let's compute its Z-array:

So, for S = "aabcaabxaaaz", the Z-array is Z = [0, 1, 0, 0, 3, 1, 0, 0, 2, 2, 1, 0].

3. The Linear-Time Construction Algorithm

A naive computation of the Z-array would itself be quadratic. The genius of the Z-algorithm lies in its ability to construct this array in linear time. It does so by maintaining a "Z-box", which is an interval [L, R] representing the substring that matches a prefix of S and has the rightmost endpoint R found so far.

S[L...R] matches S[0...R-L]

The algorithm iterates through the string from i = 1 to N-1 to compute Z[i]. For each i, there are two main cases:

Case 1: i is outside the current Z-box (i > R) In this case, we have no information from previous computations to help us. We must perform an explicit character-by-character comparison between the substring starting at i (S[i...]) and the prefix of S (S[0...]). We find the length of the match, which is Z[i]. If Z[i] > 0, we update the Z-box to [L=i, R=i+Z[i]-1] because we have found a new, rightmost-reaching prefix match.

Case 2: i is inside the current Z-box (i <= R) This is the crucial optimization. Since i is inside [L, R], we know that the substring S[i...R] is identical to the substring S[k...R-L], where k = i - L. This means we can use the already computed value Z[k] to initialize Z[i]!

Because the R pointer only ever moves forward through the string, and the explicit comparison part of the algorithm is what advances R, the total number of comparisons is bounded by 2N, leading to a linear O(N) time complexity for building the Z-array.

4. Pattern Searching with the Z-Algorithm

Now, how do we use this to find a pattern P in a text T?

  1. Concatenate: Create a new string S' = P + '$' + T, where $ is a special character that does not appear in P or T. This character acts as a separator, ensuring that no prefix-match can cross the boundary from P into T or vice-versa.
  2. Compute Z-Array: Compute the Z-array for this new concatenated string S'.
  3. Find Matches: Iterate through the Z-array. The length of our pattern P is m. If we find any index i in the Z-array such that Z[i] == m, it signifies that the substring of S' starting at i is identical to the prefix of S' (which is P). Since the $ prevents matches from starting in P and ending in T, any such match must be an occurrence of P within the T part of S'. The starting index of this match in the original text T is i - (m + 1).

Example: Pattern Matching

Let's compute the Z-array for S':

Now, we scan Z for the value m=3:

The total time complexity is O(m+n) for building the Z-array of the concatenated string, plus O(m+n) for scanning it, resulting in an overall linear time complexity.

5. Real-World Applications and Complexity

Applications:

Key points

  • The Z-algorithm finds all occurrences of a pattern P in a text T in linear time, O(|P| + |T|).
  • The core of the algorithm is the Z-array, where Z[i] is the length of the longest substring starting at index i that is also a prefix of the string.
  • The Z-array is constructed in linear time by efficiently reusing previously computed information using a 'Z-box' [L, R].
  • The Z-box represents the interval corresponding to the rightmost-reaching prefix-substring found so far, enabling optimizations.
  • When calculating Z[i] for an index i inside the Z-box, the algorithm uses the pre-computed value Z[i-L] to avoid redundant character comparisons.
  • To perform pattern searching, a new string `P + '$' + T` is created, where '$' is a unique separator character.
  • An occurrence of the pattern P is found at index `k` in the text T if Z[|P|+1+k] in the concatenated string's Z-array is equal to |P|.
  • The Z-algorithm is a powerful example of an algorithm that achieves linear time by avoiding re-computation, similar in principle to dynamic programming.

Browse public study notes