Visualize

Pattern visualizer

Z-Algorithm

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. 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..

Reuse an earlier match instead of comparing from scratch

time O(n)space O(n)step 1 / 10
a
[0]
a
[1]
b
[2]
c
[3]
a
[4]
a
[5]
b
[6]
x
[7]
a
[8]
line 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.

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

Where to practice Strings

Practice Strings problemsAll Strings problemsBack to roadmap