Zfunction

Z-function

The Z-function of a string S of length n assigns to each position i the length of the longest substring starting at i that is also a prefix of S. In many algorithmic references, Z[0] is defined as 0, though some definitions take Z[0] = n. The value Z[i] thus measures how far the prefix of S matches the substring beginning at i.

Efficient computation: The Z-algorithm computes the entire Z-array in O(n) time. It maintains a window [l, r] that denotes the rightmost substring of S that matches a prefix of S. For i from 1 to n-1: if i ≤ r, set Z[i] = min(r − i + 1, Z[i − l]); then extend the match by comparing S[Z[i]] with S[i + Z[i]] while they are equal, increasing Z[i]. If the new match extends beyond r, update l = i and r = i + Z[i] − 1. This yields a linear-time, linear-space algorithm.

Applications: The Z-function is commonly used for pattern matching by forming the string P + a separator + T and computing its Z-array; positions where Z[i] equals |P| indicate occurrences of P in T. It also helps analyze string repetitions, compute periods, and assist in various prefix-suffix related problems. It is often compared with the prefix function (failure function) as an alternative tool for similar tasks.

Example: For S = "aaaaa" (with Z[0] defined as 0), the Z-array is [0, 4, 3, 2, 1]. If a convention uses Z[0] = n, the first entry would be 5, giving [5, 4, 3, 2, 1].