For every position in a string, the Z-Algorithm computes the length of the longest substring starting at that position that matches a prefix of the string. The result, called the Z-array, solves pattern matching, string-period detection, and several related problems in linear time.

Given a string S of length n, the Z-array is an array Z of the same length where Z[i] is the length of the longest substring starting at position i that matches a prefix of S. Equivalently, Z[i] is the length of the longest common prefix between S and the suffix of S starting at position i.

By convention Z[0] is undefined (or 0); the entire string trivially matches its own prefix. Some implementations set Z[0] = n, but most algorithms skip position 0.

Example: S = "aabxaab"

Each value:

Green-highlighted positions are where Z[i] > 0, meaning they match some prefix of the string. Z[4] = 3 says "the substring starting at index 4 matches the first 3 characters of the string", which is exactly what pattern matching needs.

The naive way: for each index i from 1 to n-1, compare S[i], S[i+1], ... against S[0], S[1], ... until there is a mismatch.

Worst case O(n^2). For a string like "aaaaaaa", the inner loop runs to the end of the string at every position.

The Z-box (sometimes called Z-window) drives the linear-time version. It is the same general idea Manacher's algorithm uses for palindromes: maintain a window of already-matched characters and reuse it.

The Z-Box [L, R)

Throughout the algorithm we track a half-open interval [L, R) where R is one past the rightmost position reached by any Z-box so far. Inside this interval, S[L..R-1] matches the prefix S[0..R-L-1]. This is the "rightmost Z-box." The matching convention used in this chapter and in the code below is exclusive R: R is the position immediately after the last matched character.

The mirror is what makes the optimization work. The diagram below uses S = "aabxaabxaab" with L = 4, R = 11. The substring S[4..10] = "aabxaab" equals the prefix S[0..6] = "aabxaab", character for character. Any position i inside the Z-box has a twin position k = i - L inside the prefix, with S[i] == S[k] guaranteed.

For example, at i = 8 the twin is k = 4. Z[4] = 7 says "the substring starting at position 4 matches a prefix of length 7." The same answer carries over to position 8, capped by how much of the box remains (R - i = 3). So Z[8] starts at min(Z[4], 3) = 3 without comparing a single character.

For each new position i, there are two cases:

Case 1: i >= R (outside the current Z-box)

No useful information about position i. Compute Z[i] from scratch by comparing S[i], S[i+1], ... against S[0], S[1], .... If Z[i] > 0, update L = i and R = i + Z[i].

Case 2: i < R (inside the current Z-box)

Since S[L..R-1] matches S[0..R-L-1], we know S[i..R-1] matches S[i-L..R-L-1]. Let k = i - L. Then S[i..R-1] equals S[k..R-L-1], and Z[k] is already computed.

The Z-box optimization is amortized: each character comparison either falls inside the current Z-box (resolved in O(1) by copying) or extends R to the right (which can happen at most n times total). That gives O(n) overall.

Trace on a longer string to see the Z-box in action, then the full implementation.

Trace: S = "aabxaabxaab"

At i = 5, 6, 7, 9, and 10, no characters were compared. The values came from previously computed positions via the Z-box.

Implementation

Here is the complete Z-array construction.

The key line is z[i] = Math.min(r - i, z[i - l]), which initializes Z[i] using the Z-box when i is inside it. When i is outside the Z-box (i >= r), this line is skipped and Z[i] stays at 0, so the while loop computes from scratch.

To find all occurrences of a pattern P in a text T, concatenate the pattern, a separator character, and the text into a single string, then compute its Z-array.

The separator "$" must be a character that does not appear in P or T. It prevents matches from crossing the boundary between P and T.

After computing the Z-array of S, any position i where Z[i] equals len(P) indicates a full pattern match. Positions 0 through len(P) - 1 belong to P, position len(P) is the separator, so text positions start at len(P) + 1. A match at position i in S corresponds to a match at position i - len(P) - 1 in T.

Example: P = "aab", T = "aabxaab"

Z[4] = 3 = len(P), so there is a match at position 4 - 3 - 1 = 0 in T. Z[8] = 3 = len(P), so there is a match at position 8 - 3 - 1 = 4 in T.

Those are the two positions where "aab" appears in "aabxaab".

The separator is necessary. Without it, Z[i] could exceed len(P) if the text happens to continue matching beyond the pattern boundary. The separator guarantees Z[i] <= len(P) for positions in the text portion, so the check Z[i] == m is exact.

Implementation

Linear time is not obvious from the code because of the nested while loop.

The argument: R only moves to the right. Every while-loop iteration that finds a matching character advances R by one position (whether computing from scratch outside the Z-box or extending beyond R).

R starts at 0 and can reach at most n, so the total number of character comparisons across all while-loop iterations combined is at most n. Each for-loop iteration that does not enter the while loop is O(1) (copy a previously computed Z entry).

Total work:

For pattern matching with the concatenated string of length n + m + 1, the time is O(n + m).

Same amortized argument as KMP. KMP tracks how far it has matched into the pattern (j, which never backtracks more than it advances); Z-Algorithm tracks the rightmost reached position R.

String Period

A string S has period p if S[i] == S[i + p] for every i where both are in bounds. For example, "abcabcab" has period 3: positions 0,3,6 hold 'a'; 1,4,7 hold 'b'; 2,5 hold 'c'.

To find the smallest period using the Z-array, find the smallest i >= 1 with i + Z[i] == n. If additionally n % i == 0, S is a perfect repetition of S[0..i-1]; otherwise i is still the smallest period but the last repetition is partial.

Sum of Scores of Built Strings

For a string S, sum over each i of the length of the longest common prefix between S and S[i..n-1]. The answer is Z[1] + Z[2] + ... + Z[n-1] + n (adding n for Z[0], the whole string matching itself).

Pattern Occurrence Counting

When only the count is needed, build the Z-array of P + "$" + T and count positions i > len(P) with Z[i] == len(P). O(n+m) time and space.

Both achieve O(n+m) but differ in important ways:

The biggest practical difference is streaming. KMP processes text one character at a time and can report matches as they happen, so it works for real-time inputs like network packet inspection. Z-Algorithm needs the full text up front because it operates on the concatenated string.

When the full text is available and the problem involves prefix-match information (period detection, longest happy prefix, sum-of-scores), Z-Algorithm produces shorter code.

Time Complexity

Z-array construction: O(n) — R only moves right, so total character comparisons across all while-loop iterations are bounded by n.

Pattern matching: O(n + m) — building the concatenated string, computing its Z-array, and scanning are each O(n + m).

Space Complexity

Z-array construction: O(n) — the Z-array plus a few variables for L and R.

Pattern matching: O(n + m) — the concatenated string and its Z-array. KMP uses only O(m) for the failure function while scanning text in O(1) extra space, so KMP is better when memory is tight.