AlgoViz
HomeStrings

Z function

Hard

Longest match with the prefix at every index

Problem

Compute the Z-array: for each index, the length of the longest substring starting there that is also a prefix of the string.

In simple words

Z[i] is how far the substring starting at i matches the string's own prefix.

The idea

z[i] is how many characters starting at i match the string's own prefix. Maintaining the rightmost match window [l, r] lets each new index reuse the work already done inside it, making the whole array O(n).

The trick

  • Inside the current window, seed z[i] from the already-computed z[i - l].
  • Extend only past what is already known, which is why the total is linear.
  • Pattern matching: run it on pattern + separator + text.
a
b
x
a
b
c
a
b
c
a
b
y
0
1
2
3
4
5
6
7
8
9
10
11

Step 1 of 9. Brute force: slide "abcaby" across the text, comparing letter by letter. Values: a, b, x, a, b, c, a, b, c, a, b, y.

1/9
Brute force
timeO(n·m)spaceO(1)

Slide and compare.

1for (let i = 0; i + m <= n; i++) {2  let j = 0;3  while (j < m && text[i + j] === pat[j]) j++;4  if (j === m) return i;5}

Input

array
[a, b, x, a, b, c, a, b, c, a, b, y]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
s = "aabxaab"
Output:
[0, 1, 0, 0, 3, 1, 0]
Explanation:
Each value = match length with the prefix.

Example 2

Input:
s = "aaaa"
Output:
[0, 3, 2, 1]
Explanation:
0,3,2,1.

Example 3

Input:
s = "abc"
Output:
[0, 0, 0]
Explanation:
No prefix matches → 0,0,0.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.