Construct the Z-array for linear time pattern matching.

Problem Statement

Given a string `s`, compute the Z-array for `s`. An element `Z[i]` of the Z-array is the length of the longest substring starting from `s[i]` which is also a prefix of `s`. By standard convention, `Z[0] = 0`.

Examples

Input: s = "aaaaa"

Output: [0, 4, 3, 2, 1]

Explanation: Combining the input according to Z function logic yields [0, 4, 3, 2, 1].

Input: s = "aaabaab"

Output: [0, 2, 1, 0, 2, 1, 0]

Explanation: Combining the input according to Z function logic yields [0, 2, 1, 0, 2, 1, 0].

Complexity

Time Complexity: O(N)

Space Complexity: O(N)

Hints

💡 Hint 1: Z[i] is the length of the longest substring starting from s[i] that is also a prefix of s. Z[0] is 0 by standard convention. 💡 Hint 2: Maintain a segment [l, r] which is the match box extending furthest to the right. 💡 Hint 3: If i <= r, initialize Z[i] using already computed values: min(r - i + 1, Z[i - l]), then expand linearly as needed.

Editorial & Approach

Problem Overview & Intuition

The Z-algorithm computes prefix-matching lengths in linear O(N) time by maintaining the rightmost matching window [l, r]. Reusing previously computed Z-values avoids re-evaluating characters already inside the window.

Step-by-Step Approach

Initialize z = new Array(n).fill(0) and l = 0, r = 0.
Iterate i from 1 to n - 1.
If i <= r, initialize z[i] = Math.min(r - i + 1, z[i - l]).
Extend z[i] while characters match.
If i + z[i] - 1 > r, update l = i, r = i + z[i] - 1.
Return z.

Optimal Implementation (JavaScript)

function zFunction(s) {
  const n = s.length;
  const z = new Array(n).fill(0);
  let l = 0, r = 0;
  for (let i = 1; i < n; i++) {
    if (i <= r) z[i] = Math.min(r - i + 1, z[i - l]);
    while (i + z[i] < n && s[z[i]] === s[i + z[i]]) z[i]++;
    if (i + z[i] - 1 > r) {
      l = i;
      r = i + z[i] - 1;
    }
  }
  return z;
}

Complexity Analysis

Time Complexity O(N) — each character inside [l, r] visited a constant number of times.

Space Complexity O(N) — for the output Z-array.

Edge Cases & Corner Traps Handled

All identical characters "aaaaa": Z = [0, 4, 3, 2, 1].
All distinct characters: Z array is all zeroes.

Z function

Hard

Example Scenarios

1Example 1

Input: s = "aaaaa"

Output: [0, 4, 3, 2, 1]

Explanation:

Combining the input according to Z function logic yields [0, 4, 3, 2, 1].

2Example 2

Input: s = "aaabaab"

Output: [0, 2, 1, 0, 2, 1, 0]

Explanation:

Combining the input according to Z function logic yields [0, 2, 1, 0, 2, 1, 0].

Editor

Loading Editor...

s =

"aaaaa"

Output:Click "Run" above to execute and verify your code here.

[0,4,3,2,1]