Gusfield's Z-Algorithm

The Gusfield’s Z-Algorithm is a linear-time algorithm for pre-processing a string. Its output, the Z-values ($Z_i$), enable efficient solutions to various string-related problems, including linear-time pattern matching.

Defining The $Z$-Values, $Z$-Box, $r_i$ & $l_i$

For a string str[1...n], the $Z_i$-value, at each position $i\ge 1$, represents the length of the longest substring starting at position $i$ that matches a prefix of the string.

Example of $Z$-values

Given the string str = aabcaabxaay, the corresponding Z-array, with the same length as str, has values:

• Z[1] = 11 → Since Z[1] represents the entire string, it is always equal to n.
• Z[2] = 1 → The substring starting at str[2] (a) matches the first character of the prefix.
• Z[3] = 0 → No match between str[3] (b) and the prefix.
• Z[4] = 0 → No match between str[4] (c) and the prefix.
• Z[5] = 3 → The substring str[5..7] = "aab" matches the prefix str[1..3] = "aab".
• Z[6] = 1 → The substring str[6] = "a" matches the first character of the prefix.
• Z[7] = 0 → No match between str[7] (b) and the prefix.
• Z[8] = 0 → No match between str[8] (x) and the prefix.
• Z[9] = 2 → The substring str[9..10] = "aa" matches the prefix str[1..2] = "aa".
• Z[10] = 1 → The substring str[10] = "a" matches the first character of the prefix.
• Z[11] = 0 → No match between str[11] (y) and the prefix.

The $Z$-box at each position $i\ge 1$ is the contiguous range of indices $[i\dots i+Z_i-1]$, representing the longest substring starting at position $i$ that matches the prefix of str.

Example of a $Z$-Box

Given the string str = aabcaabxaay, the corresponding $Z$-box has the following values:

• ZBox[1] = [1..11] → The $Z$-box is from index 1 to 11 (i.e., the entire string).
• ZBox[2] = [2..2] → The $Z$-box is from index 2 to 2 (a).
• ZBox[3] = undefined → No match, so the $Z$-box is empty.
• ZBox[4] = undefined → No match, so the $Z$-box is empty.
• ZBox[5] = [5..7] → The $Z$-box is from index 5 to 7 (aab).
• ZBox[6] = [6..6] → The $Z$-box is from index 6 to 6 (a).
• ZBox[7] = undefined → No match, so the $Z$-box is empty.
• ZBox[8] = undefined → No match, so the $Z$-box is empty.
• ZBox[9] = [9..10] → The $Z$-box is from index 9 to 10 (aa).
• ZBox[10] = [10..10] → The $Z$-box is from index 10 to 10 (a).
• ZBox[11] = undefined → No match, so the $Z$-box is empty.

The $r_i$, for $i>1$, is the right-most endpoint of all Z-boxes that begin at or before position $i$. The value of $r_i$ never decreases as $i$ increases.

Example of $r_i$

Given the string str = aabcaabxaay, the corresponding $r_i$ values are:

• r[2] = 2 → ZBox[2] = [2..2], so the right-most endpoint is 2.
• r[3] = 2 → ZBox[3] is undefined, so the right-most endpoint remains as 2.
• r[4] = 2 → Same as previous.
• r[5] = 7 → ZBox[5] = [5..7], so the right-most endpoint is 7, as $7>2$.
• r[6] = 7 → ZBox[6] = [6..6], the right-most endpoint remains 7, as $7>6$.
• r[7] = 7 → ZBox[7] is undefined, so the right-most endpoint remains as 7.
• r[8] = 7 → Same as previous.
• r[9] = 10 → ZBox[9] = [9..10], so the right-most endpoint is 10, as $10>7$.
• r[10] = 10 → ZBox[10] = [10..10], the right-most endpoint remains as 10.
• r[11] = 10 → ZBox[1] is undefined, so the right-most endpoint remains as 10.

The $l_i$, for $i>1$, is the left endpoint of any Z-box that ends at position $r_i$. If there are multiple Z-boxes that end at $r_i$, then $l_i$ can be chosen as the left endpoint of any of those Z-boxes.

Example of $l_i$

Given the string str = aabcaabxaay, the corresponding $l_i$ values are:

• l[2] = 2 → The Z-box that end at position r[2] = 2 is ZBox[2] = [2..2] which has the left-endpoint of 2
• l[3] = 2 → r[3] = r[2], so the left endpoint remains.
• l[4] = 2 → Same as previous.
• l[5] = 5 → The Z-box that end at position r[5] = 7 is ZBox[5] = [5..7] which has the left-endpoint of 5
• l[6] = 5 → r[6] = r[5], so the left endpoint remains
• l[7] = 5 → Same as previous.
• l[8] = 5 → Same as previous.
• l[9] = 9 || 10 → The Z-boxes that end at position r[9] = 10 areZBox[9] = [9..10] and ZBox[10] = [10..10]. The $l_i$ could either be 9 or 10.
• l[10] = 9 || 10 → r[10] = r[9], so the left endpoint remains
• l[11] = 9 || 10 → Same as previous.

Illustration of all Definitions

Overview Of Gusfield’s Z-Algorithm

The goal is to compute $\{Z_i,Z_i\text{-box},r_i,l_i\}$ values for each position $1<i\le n$. The computation starts at $i=2$, since $Z_1$ is always the length of the string and provides no useful information.

However, not all values need to be actively tracked and stored in an array:

• $Z_i$ — Each computed $Z_i$ value is stored, as it is essential for further calculations.
• $Z_i$-box — The interval $[i\dots i+Z_i-1]$ can be derived in $O(1)$ time from $Z_i$.
• $(r_i,l_i)$ — Only the most recent $(r,l)$ values (i.e., $(r_{i-1},l_{i-1})$) are stored as temporary variables, since updating $(r_i,l_i)$ only depends on the previous iteration.

Z-Algorithm: Base Case

To start the algorithm, compute $Z_{i=2}$ by performing an explicit left-to-right comparison of the characters str[(i=2)...q-1] with str[1...q-2] until a mismatch is found at some $q\ge 1$.

• This results in $Z_2=(q-1)-(i)+1=q-2$
• If $Z_2>0$, i.e. a Z-box of some length is found:
  • Set $r_2=(i)+(Z_i)-1=q-1$ and $l_2=i=2$
• Else, if $Z_2=0$, i.e. the Z-box is undefined:
  • Set $r_2=0$ and $l_2=0$

The length of a $Z$-box (the $Z$-value) is given by $Z=EP-SP+1$.

As $i$ and $q-1$ are the start & end points of the $Z$-box, we have the formula:

$Z=(q-1)-(i)+1$

This can be rearranged to make $r$ the subject:

$r=(i)+(Z_i)-1$

Example of Computing the Base Case ( $Z_2$)

Given the string str = aabcaacxaabcaabcay, the base case begins with calculating $Z_2$.

• Initialise the $Z$-array as a zero-filled array of the str’s length.
• Compare str[2] with str[1]:
  • str[2] = a = str[1], so $Z_2$ increments.
• Compare str[3] with str[2]
  • str[3] = b != str[2], so a mismatch is found.
• Since $Z_2=1>0$, set:
  • $l_2=2$
  • $r_2=2+Z_2-1=2$

Z-Algorithm: Inductive Step

Assume that for some position $k$:

• The values $Z_2$ through $Z_{k-1}$ have been computed correctly,
• $r$ currently holds $r_{k-1}$ and,
• $l$ currently holds $l_{k-1}$,

To compute $Z_k$ at position $k$, there are two cases to consider:

Case 1 — $k>r$

If $k>r$, then $k$ is outside the previously computed $Z_l$-box, meaning there’s no additional information available.

Therefore, to compute $Z_k$, explicitly compare characters str[k...q-1] with the prefix str[1...q-k] until a mismatch is found at some $q\ge k$.

• This results in $Z_k=(q-1)-(k)+1=q-k$
• If $Z_k>0$, then:
  • Set $r_k=k+Z_k-1=q-1$ and $l_k=k$
• Else, if $Z_k=0$, then:
  • $(r_k,l_k)$ retains its value, remaining the same as $(r_{k-1},l_{k-1})$.

Example of Computing Case 1

Given the string str = aabcaacxaabcaabcay,

• The base case begins with $Z_2=1$, $l_2=2$, and $r_2=2$
• For $k=3$:
  • Since the $Z_2$-box ends at $r_2=2<k$, it provides no additional information for computing $Z_3$.
  • Explicit matching is performed:
    • str[3] = b != str[1], so $Z_3=0$.
    • Thus, retain the previous values of $(r,l)$.

Case 2 — $k\le r$

If $k\le r$, then $k$ lies within the boundaries of the previously computer $Z_l$-box, allowing future information about substring matches to aid in computing $Z_k$.

• By definition, the $Z_l$-box ($[l\dots r]$), matches the prefix range $[1\dots Z_l]$, making them symmetrical.
• This then implies that str[k...r] = str[k-l+1...Z_l] which again by definition, is equal to str[1...r-k+1]
• By the inductive hypothesis, $Z_{k-l+1}$ is already computed, so it can be used to aid in the computation of $Z_k$

More specifically, we relate $Z_{k-l+1}$ to the length of the green box ($r-k+1$), leading to three possible cases:

Case 2a — $Z_{k-l+1}<r-k+1$

If $Z_{k-l+1}<r-k+1$, then the $Z_k$-box remains within the bounds of the remaining portion of the $Z_l$​-box, so its value can be directly copied.

• Recall that $Z_l$-box is equivalent to $[1\dots Z_l]$, and str[k...r] = str[k-l+1...Z[l]] = str[1...r-k+1]
• Since a mismatch occurs immediately after the $Z_{k-l+1}$-box, at position $p$ with the prefix at position $p-k+l$, the exact same mismatch must occur after the $Z_k$-box, at position $p+l-1$

Therefore, as $Z_k$ is identical to $Z_{k-l+1}$, we can simply:

• Set $Z_k=Z_{k-l+1}$.
• Keep $r$ and $l$ unchanged.

Since no explicit comparisons are performed, $Z_k$ is computed in $O(1)$ time.

Case 2b — $Z_{k-l+1}=r-k+1$

If $Z_{k-l+1}=r-k+1$, then the $Z_k$-box reaches the boundary of the $Z_l$ box, meaning it could extend further, requiring explicit matching.

• Recall that $Z_l$-box is equivalent to $[1\dots Z_l]$, and str[k...r] = str[k-l+1...Z_l] = str[1...r-k+1]
• This case implies that a mismatch occurred at $r-l+2$ with the corresponding prefix character at $r-k+2$
• Thus, the character at $r+1$ can’t be the same as $r-l+2$, because if it was, the $Z_l$ box would have extended further, contradicting its original boundary at $r$.
• However, the character at $r+1$ can be the same as $r-k+2$; we can’t be certain that $Z_k$ is strictly bounded by $Z_l$.

Therefore, we:

• Set $Z_k=Z_{k-l+1}=r-k+1$
• Increment $Z_k$ by continuing explicit matching from str[r+1...q-1] with the prefix from str[r-k+2...q-k] until a mismatch occurs at some position $q\ge r+1$.
• This results in $Z_k=Z_{k-l+1}+(q-1)-(r+1)+1=q-k$
• Additionally, set $r_k=k+Z_k-1=q-1$ and $l_k=k$

This takes $O(q-r)$ time, as the algorithm iterates over $(q-1)-(r)+1$ characters.

Case 2c — $Z_{k-l+1}>r-k+1$

If $Z_{k-l+1}>r-k+1$, then the $Z_k$-box extends beyond the boundary of the $Z_l$-box, meaning $Z_{k-l+1}$ provides enough information to compute $Z_k$ without further comparisons.

• Recall that $Z_l$-box is equivalent to $[1\dots Z_l]$, and str[k...r] = str[k-l+1...Z_l] = str[1...r-k+1]
• Since the $Z_{k-l+1}$-box extends past $r-l+1$, by definition, its corresponding match at the prefix, extends past $r-k+1$
• Therefore, $Z_k$ does not extend, as if it did, then the character at $r+1$ would be the same as $r-l+2$, but this would mean the $Z_l$ box would have extended further, contradicting its original boundary at $r$.
• This means that the character at $r+1$ cannot be the same as $r-k+2$, and is thus a mismatch.

Therefore, we can simply:

• Set $Z_k=(r-l+1)-(k-l+1)+1=r-k+1$
• Keep $r$ and $l$ unchanged ($r_k=k+Z_k-1=r$, and $l_k=l$ (or $l_k=k$ as both are the left endpoint of the z-box ending at $r_k$)

Since no new comparisons are required, this case takes $O(1)$ time.

Time Complexity Analysis

The Z-algorithm pre-processes a string in $O(n)$ time by computing all $Z$-values efficiently.

• The total run-time depends on two factors
  • The number of iterations
  • The total number of character comparisons (both matches and mismatches)
• Since the algorithm computes one $Z$-value per iteration, there are exactly $n-1$ iterations
  • Each iteration, aside from character comparisons, involves only constant-time operations.
• Character comparisons stop as soon as a mismatch occurs, meaning there can be at most $n-1$ mismatches in total.
  • To determine the total number of matches, note that the rightmost boundary $r_k$ is always non-decreasing across iterations. Denoted by $r_k=r_{k-1}+\delta$, where $\delta \ge 0$
  • A $Z$-box cannot extend beyond the string boundaries, $r_k\le n$, ensuring that the total number of matches $\le n$

Therefore the algorithm performs at most $O(n)$ character comparisons across all iterations, along with $O(n)$ additional work, leading to an overall time complexity of $O(n)$

Space Complexity Analysis

• A regular implementation computes and stores $Z$-values in an array of length $n$, requiring $O(n)$ space

Z-Algorithm For Linear Time Exact Pattern Matching

The Exact Pattern Matching Problem involves finds all occurrences of a given pattern[1...m] in a given text[1...n].

Gusfield’s Z-algorithm enables a linear-time solution to this, as follows:

1. Construct a new string: str[1...m+n+1] = pat[1...m] + "$" + txt[1...n]
2. For $1<i<m+n$, pre-process $Z_i$ values corresponding to the str.
3. For any $i\ge m+2$, positions where $Z_i=m$ indicate an occurrence of pat[1...m] at position $i$ in str, and hence $i-(m+1)$ in txt. That is: pat[1...m] = str[i...i+m-1] = txt[i-(m+1)...i-2]
4. As the computation of $Z_i$ values for any string takes $O(\text{|string|})$ time, this algorithm takes $O(m+n)$ time.

The terminal character ( $) can be omitted with minor modifications to the algorithm.

• The $ serves as a separator, ensuring no character in text matches it.
• This guarantees that the maximum possible $Z_i$ value is $m$.
• Without $, this restriction is lost, so occurrences must be identified by considering all $Z_i\ge m$ values.
• Additionally, indexing adjustments are needed since the string length is reduced by one.

Improvements to Space Complexity

• In a regular implementation, the space complexity would be $O(n+m)$ space
• This can be optimised by only storing necessary $Z$ values (those of length $m$), reducing it to $O(m)$ space