Z-AlgorithmThe Z function

01Why it exists

Reach for it when you see:The longest common prefix between the string and each of its suffixes, hunting for Z values equal to m over pattern + separator + text, periods and repeating units, matching that tolerates a few errors (one pass forwards, one backwards), string rotation.

02The core idea

The Z array is defined like this: Z[i] is the length of the longest common prefix shared by the whole string s and the suffix s[i..] that starts at i. Z[0] is simply the length of the string and is normally left unused. Comparing from scratch at every position costs O(n²) on a string like aaaa…a. The Z algorithm instead maintains a window [l, r]: among the positions computed so far, the match interval [i, i + Z[i] − 1] that reaches furthest to the right. The defining property of that window is that s[l..r] is character for character the same as s[0..r−l] at the start of the string.

Computing Z[i] splits into three cases. If i > r, then i lies outside the window with nothing to borrow, so you compare from scratch one character at a time, and if the match reaches past r the window is replaced. If i lies inside the window, then, because the window matches the start of the string, s[i..r] is the same text as s[i−l..r−l]; the position i − l is called the mirror of i, and its Z value was computed long ago. When that mirror value is smaller than the r − i + 1 cells left in the window, the match on the mirror side broke off inside the window, so it breaks off at the same place here — copy Z[i] = Z[i−l] with zero comparisons. When the mirror value is at least as large as the number of cells left, only the first r − i + 1 characters are known to match, the characters beyond the window have never been looked at, so you carry on comparing from the cell after r and then update the window.

Cost: every successful comparison in the extend step pushes r one place to the right, and r only ever increases, up to n, so there can be at most n successful comparisons in total; failed comparisons cost at most one per i. That is O(n) time and O(n) space overall. For string matching, concatenate the pattern, a separator that appears nowhere else, and the text, then compute the Z array: the separator caps every value at m, so a position holding exactly m means the pattern occurs in the text starting there, all in O(n + m). Set against KMP: the pi table stores only the pattern, O(m), which lets the text arrive as a stream. The Z algorithm has to concatenate everything first, but its definition — how many characters each position shares with the start — is the more direct one, and it composes into other applications more readily.

The usual traps. Forgetting to take the minimum with r − i + 1 when copying the mirror value, which treats characters beyond the window as matching although nobody has looked at them. Being inconsistent about whether the right end of the window is a closed or a half-open interval, where being off by one is fatal. Leaving out the separator, which lets Z values run past the pattern and into the text, making the "equals m" test unreliable. And using Z[0] as though it were an ordinary value. Two useful properties: every i with i + Z[i] = n is a period of the string, and the smallest one is the shortest period — when it divides n, the string is that unit repeated exactly. Reversing the string and running Z again gives you how many characters each position matches from the end, which is what makes error-tolerant matching possible. How this sits beside the neighbouring lessons: the Z array and KMP's pi table convert into each other in O(n) and solve very nearly the same set of problems, while the next lesson, Manacher, runs on the same idea — borrow the answer from a mirror position inside the interval that reaches furthest — with the common prefix swapped for a palindrome radius.

03The algorithm

1. 1Set Z[0] = n and the window to l = r = 0, then sweep i from 1 up to n − 1.
2. 2If i ≤ r, start with Z[i] = min(Z[i − l], r − i + 1) — those characters are guaranteed to match, so there is nothing to compare. Otherwise start with Z[i] = 0.
3. 3Carry on from the current Z[i], comparing s[Z[i]] against s[i + Z[i]] one character at a time and adding 1 on every match. When the mirror value is smaller than the number of cells left, the very first comparison fails.
4. 4If Z[i] > 0 and i + Z[i] − 1 > r, replace the window with [i, i + Z[i] − 1].
5. 5To match, run Z over pattern, separator and text: subtract m + 1 from each position whose value is m and you have a starting point in the text. To find a period, the smallest i satisfying i + Z[i] = n is the shortest period.

04Interactive demo

s = aabcaabcaab. In the string row, blue is the current i; the row underneath shows the window [l, r] in amber. Positions i = 1 through 4 all sit outside the window and have to compare character by character: Z[1] = 1, Z[2] and Z[3] are both 0, and i = 4 matches 7 characters in one go, pushing the window out to [4, 10], right up to the end of the string. Then i = 5, 6 and 7 all fall inside the window, their green mirror positions are 1, 2 and 3, and every one of those Z values is smaller than the number of cells left, so they are copied straight across with zero comparisons. At i = 8 the mirror Z[4] = 7 is larger than the 3 cells remaining, so only 3 characters are guaranteed to match, and since the window already runs to the end, Z[8] = 3 and the window becomes [8, 10]; i = 9 and 10 copy once more. The finished array is Z = [·, 1, 0, 0, 7, 1, 0, 0, 3, 1, 0]. Both i = 4 and i = 8 satisfy i + Z[i] = n, so the shortest period is 4: s is aabc repeated, with the last block left incomplete.

05Code

Python has the Z function, string matching through a separator, and the forward-and-backward pair of Z arrays that locates every position matching with at most one wrong character. C++ has the Z function, the shortest period used to pull out the unit and the count of a tandem repeat, and a check for whether two circular sequences differ only in where they start. Both languages treat the window as the closed interval [l, r], matching the demo.

def z_function(s):
    """z[i]: the length of the longest common prefix of s and s[i:]. O(n)"""
    n = len(s)
    z = [0] * n
    if n:
        z[0] = n
    l = r = 0                                   # window [l, r]: s[l..r] matches s[0..r-l]
    for i in range(1, n):
        if i <= r:
            z[i] = min(z[i - l], r - i + 1)     # copy the mirror, but borrow no further than the window edge
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1                           # past the window there is nothing to reuse, so compare directly
        if z[i] and i + z[i] - 1 > r:           # only move the window when the right end reaches further
            l, r = i, i + z[i] - 1
    return z


def z_search(text, pat):
    """Run Z over pat + separator + text; every value equal to m is one occurrence"""
    m = len(pat)
    if m == 0:
        return []
    z = z_function(pat + "\0" + text)          # the separator is in neither string, so no Z value exceeds m
    return [i - m - 1 for i in range(m + 1, len(z)) if z[i] == m]


def almost_match(text, pat):
    """Occurrences with at most one wrong character: a match from the front, b from the back, a + b >= m - 1"""
    n, m = len(text), len(pat)
    if m == 0 or m > n:
        return []
    front = z_function(pat + "\0" + text)
    back = z_function(pat[::-1] + "\0" + text[::-1])   # a prefix of the reversal is a suffix of the original
    res = []
    for i in range(n - m + 1):
        a = front[m + 1 + i]                    # how many characters text[i:] shares with pat from the front
        b = back[m + 1 + (n - i - m)]           # how many characters text[i:i+m] shares with pat from the back
        if a + b >= m - 1:
            res.append(i)
    return res


if __name__ == "__main__":
    print(z_function("aabcaabcaab"))            # [11, 1, 0, 0, 7, 1, 0, 0, 3, 1, 0]
    print(z_search("abracadabra", "abra"))      # [0, 7]
    print(almost_match("ACGTTACGAACGT", "ACGT"))   # [0, 5, 9]: position 5 is ACGA, one mismatch

06Practice

• LeetCode 3029Minimum Time to Revert Word to Initial State I (find the smallest multiple with i + Z[i] = n)Medium
• LeetCode 2223Sum of Scores of Built Strings (the answer is the sum of the whole Z array)Hard
• LeetCode 3031Minimum Time to Revert Word to Initial State II (same as above; at length 10⁶ it has to be linear)Hard
• LeetCode 3036Number of Subarrays That Match a Pattern II (convert to a sequence of comparisons first, then match)Hard
• LeetCode 3303Find the Occurrence of First Almost Equal Substring (one Z array forwards, one backwards)Hard