DSA Tracker

Visualize

Z-Algorithm

Reuse an earlier match instead of comparing from scratch

time O(n)space O(n)

Comparing every position against the prefix from scratch is quadratic, and most of that work is repeated. The Z-algorithm keeps one interval [l, r] — the rightmost stretch already proven to match the prefix, the z-box. Any position landing inside that box already has a known answer at its mirror position in the prefix, so it can be copied instead of compared, and comparing only ever resumes past r. Because r never moves left, the total number of comparisons across the whole string is linear.

Details

Animated on: s = "aabcaabxa" — build Z, where Z[i] is the length of the longest substring starting at i that is also a prefix of s. Z[0] is set to the whole length by convention.

Problem:Z-AlgorithmMedium

Reuse an earlier match instead of comparing from scratch

step 1 / 10

a
[0]
a
[1]
b
[2]
c
[3]
a
[4]
a
[5]
b
[6]
x
[7]
a
[8]

s = "aabcaabxa". Z[i] answers one question per position: how many characters starting at i also start the whole string? The whole trick is that a match already found is reusable, so most positions need no comparisons at all.

Pseudocode
1FUNCTION zAlgorithm(s):
2  l <- 0
3  r <- 0
4  FOR i <- 1 TO LENGTH(s) - 1
5    IF i <= r
6      Z[i] <- MIN(r - i + 1, Z[i - l])
7    WHILE i + Z[i] < LENGTH(s) AND s[Z[i]] = s[i + Z[i]]
8      Z[i] <- Z[i] + 1
9    IF i + Z[i] - 1 > r
10      l <- i
11      r <- i + Z[i] - 1
12  RETURN Z

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. s = "aabcaabxa". Z[i] answers one question per position: how many characters starting at i also start the whole string? The whole trick is that a match already found is reusable, so most positions need no comparisons at all.
  2. i=1 is past the z-box [0, 0], so it is compared against the prefix from scratch: "a" agrees for 1 character before s[2]='b' differs from s[1]='a'. Z[1]=1, and because this match reaches further right than before, the box becomes [1, 1] — that is the work later positions will reuse.
  3. i=2 is past the z-box [1, 1], so nothing is known in advance and comparing starts at the prefix: s[2]='b' differs from s[0]='a', so Z[2]=0 and the box does not move.
  4. i=3 is past the z-box [1, 1], so nothing is known in advance and comparing starts at the prefix: s[3]='c' differs from s[0]='a', so Z[3]=0 and the box does not move.
  5. i=4 is past the z-box [1, 1], so it is compared against the prefix from scratch: "aab" agrees for 3 characters before s[7]='x' differs from s[3]='c'. Z[4]=3, and because this match reaches further right than before, the box becomes [4, 6] — that is the work later positions will reuse.
  6. i=5 sits inside the z-box [4, 6], so position 1 of the prefix is its mirror. Z[1]=1 is shorter than the 2 characters the box still guarantees, so Z[5]=1 is copied outright — not a single comparison was made here.
  7. i=6 sits inside the z-box [4, 6], so position 2 of the prefix is its mirror. Z[2]=0 is shorter than the 1 character the box still guarantees, so Z[6]=0 is copied outright — not a single comparison was made here.
  8. i=7 is past the z-box [4, 6], so nothing is known in advance and comparing starts at the prefix: s[7]='x' differs from s[0]='a', so Z[7]=0 and the box does not move.
  9. i=8 is past the z-box [4, 6], so it is compared against the prefix from scratch: "a" agrees for 1 character and runs off the end of the string. Z[8]=1, and because this match reaches further right than before, the box becomes [8, 8] — that is the work later positions will reuse.
  10. Every position is answered: Z = [9, 1, 0, 0, 3, 1, 0, 0, 1]. The largest entry, Z[4]=3, says the longest place the string repeats its own opening is "aab" — which is exactly how this array is used to find a pattern inside a text in linear time.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Z-Algorithm in the editorAll Strings problemsBack to roadmap