Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 225 ยท Strings

The Z-Algorithm

Learn the Z-algorithm step by step in Python. Build the Z array in O(n), search patterns in linear time, and solve prefix, border and period problems.

The Z-algorithm is one of the most elegant tools in string processing. Given a string s, it computes an array z where z[i] is the length of the longest substring starting at position i that is also a prefix of s. That sounds like an odd thing to want, yet this single array solves pattern matching, finds repeated blocks, detects periods and computes borders, all in O(n) time.

Compared with KMP, the Z-algorithm is easier to remember and to explain: there is no failure table to interpret, just a window of text you have already compared that you reuse. Many programmers find it the simplest linear-time way to search for a pattern. In this lesson you build the naive version first, discover why it is slow, then add the one idea that makes it linear.

What the Z array means

Take s = "aabxaab". For each position i, ask: how many characters starting at i match the characters at the start of s?

TEXT
index:   0 1 2 3 4 5 6
s:       a a b x a a b
z:       - 1 0 0 3 1 0

z[1] = 1   "abxaab" vs "aabxaab": a = a, then b != a
z[4] = 3   "aab"    vs "aab"    : all 3 match
z[5] = 1   "ab"     vs "aa"     : a = a, then b != a

By convention z[0] is undefined or set to n (the whole string trivially matches itself). We store n here, and most problems ignore it.

Python Z array by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The brute-force version compares from scratch at every i, so it costs O(nยฒ) for a string like "aaaa...a", where every z[i] is long. Look at that input: z[1] was computed by comparing n - 1 characters, then z[2] re-compares nearly the same characters. Surely we already learned what we need.

The Z-box: reuse what you have already compared

Keep a window [l, r) called the Z-box: the rightmost segment found so far that matches a prefix of s. That is, s[l:r] == s[0:r-l].

TEXT
          0         l            r
s:        [ prefix ]...[ matches prefix ]
                        |<-- r - l -->|
          s[l:r] == s[0:r-l]

Now compute z[i] for a new position i.

  1. If i is outside the box (i >= r), we know nothing: compare from scratch, and extend as far as possible. This may create a new, further-right box.
  2. If i is inside the box (i < r), the substring starting at i is a copy of the substring starting at k = i - l near the start of s. So z[i] is at least min(z[k], r - i). Start the comparison from that value instead of 0:
    • If z[k] < r - i, the copy ends inside the box, so z[i] = z[k] exactly. No extension is possible.
    • If z[k] >= r - i, we only know the first r - i characters match; try to extend beyond r.

Every successful character comparison moves r to the right, and r never moves left. Failed comparisons happen at most once per position. Hence the whole algorithm does O(n) comparisons.

Python The linear-time Z-algorithm

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last two lines test the fast version against the slow one on every string over {a, b} up to length 7. This kind of cross-checking against a simple solution is a habit worth keeping for every clever algorithm.

Trace on a small example

Run it on s = "aabxaab" (n = 7).

TEXT
i=1: i >= r (r=0)      compare s[0]=a, s[1]=a -> match; s[1]=a vs s[2]=b -> stop
                       z[1] = 1; box becomes [1, 2)
i=2: i >= r (r=2)      s[0]=a vs s[2]=b -> z[2] = 0
i=3: i >= r            s[0]=a vs s[3]=x -> z[3] = 0
i=4: i >= r            a=a, a=a, b=b, then a vs end -> z[4] = 3; box [4, 7)
i=5: i < r (r=7)       k = i - l = 1, z[1] = 1, r - i = 2 -> start at min(2,1) = 1
                       compare s[1]=a vs s[6]=b -> stop
                       z[5] = 1
i=6: i < r             k = 2, z[2] = 0 -> start at 0; s[0]=a vs s[6]=b -> z[6] = 0

Result: [7, 1, 0, 0, 3, 1, 0], the same as the earlier diagram (with z[0] = n).

Pattern matching with the Z-array

To find pattern in text, build the string

TEXT
combined = pattern + "$" + text

where $ is a separator that occurs in neither string. Compute its Z array. Any position i in the text part with z[i] == len(pattern) is a match. The separator guarantees no Z value can exceed len(pattern), because the prefix match stops at the separator.

TEXT
pattern "aba", text "abacaba"
combined:  a b a $ a b a c a b a
z:         - 0 1 0 3 0 1 0 3 0 1
                     ^           ^
                     z = 3 = len(pattern)  -> matches at text index 0 and 4

The match position in text is i - len(pattern) - 1.

Python Pattern search with the Z array

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The whole search is O(n + m) time and O(n + m) extra space for the combined string and the array. You can cut the space to O(m) by computing the Z array of the pattern only and then streaming over the text, but the combined-string trick is the one to memorize.

Prefix and border problems

Once you have z, many questions become one-liners.

Borders. A border of s is a non-empty proper prefix that is also a suffix (the same idea as the LPS values in KMP). Position i gives a border exactly when i + z[i] == n, and its length is n - i.

Periods. The smallest period p of s is the smallest p such that s[i] == s[i + p] for all valid i. This is equivalent to p + z[p] == n (the suffix from p is a prefix). If p also divides n, then s is a block of length p repeated n / p times.

Counting prefix occurrences. The number of positions where the whole prefix of length L appears equals the number of i with z[i] >= L.

Python Borders, periods and repeated blocks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For "aabaab" the only border is aab (length 3: a is not a border because the string ends in b); the smallest period is 3 and the string is aab repeated twice. For "abaab" the border ab has length 2 but the period 3 does not divide 5, so there is no whole repeated block.

A classic problem: shortest string with a given prefix and suffix

Problem. Given a string s, find the length of the longest border that is not the whole string (the longest proper prefix that is also a suffix).

Brute force: for each length L from n - 1 down to 1, compare s[:L] with s[n-L:]. Each comparison costs O(L), so the total is O(nยฒ).

Z solution: the longest border starts at the smallest i >= 1 with i + z[i] == n, so its length is n - i. That is one pass over z: O(n).

Python Longest border: brute force versus Z

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Z-algorithm versus KMP versus Rabin-Karp

Preprocessing Search Guarantee
Naive none O(n*m) worst case slow on repetitive text
KMP O(m) LPS table O(n) deterministic linear
Z-algorithm O(n + m) Z array included deterministic linear
Rabin-Karp O(m) hash O(n) expected randomized, can degrade

KMP and Z are essentially equivalent in power: the prefix function and the Z array can be converted into each other in linear time. Choose whichever you can write without a bug. Many people prefer Z because "the longest match with the prefix" is an easier mental model than "the longest proper border of each prefix".

Common mistakes

  • No separator. Without $, a Z value can run from the pattern into the text and exceed m, giving false or missed matches. The separator must not appear in either string.
  • Forgetting z[0]. It is either n or 0 by convention. Be consistent, and skip index 0 in loops that start from 1.
  • Not clamping with r - i. Using z[i - l] alone can claim a match longer than the box guarantees. Always take min(r - i, z[i - l]).
  • Resetting the box when i moves. The box only ever moves right, and that is exactly why the algorithm is linear.
  • Quadratic extension. Starting the while loop from 0 inside the box brings back O(nยฒ).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does z[i] represent?

    z[i] counts how many characters from position i onward match the beginning of the string.
  2. 2. Why is the Z-algorithm O(n) even though it has a while loop inside a for loop?

    Inside the box we start from a reused value, and each character that is compared successfully pushes r forward. Since r never exceeds n and never moves left, the total work is linear.
  3. 3. Why do we put a separator between the pattern and the text before computing Z?

    The separator is not in the text, so a prefix match always stops there. A value z[i] equal to len(pattern) then means a genuine full match.
  4. 4. In 'abcabcabc', which condition shows that 3 is a period?

    A period p satisfies p + z[p] == n, because the suffix starting at p must equal a prefix. Here z[3] = 6 and 3 + 6 = 9.
  5. 5. What is the time complexity of searching a pattern of length m in a text of length n with the Z-algorithm?

    The combined string has length n + m + 1 and its Z array is built in linear time, followed by one scan.

Summary

  • z[i] is the length of the longest match between the suffix starting at i and the prefix of s.
  • A naive Z array costs O(nยฒ); the Z-box [l, r) lets you reuse z[i - l] for positions inside the box, making it O(n).
  • To search, compute Z for pattern + separator + text and report positions where z[i] == len(pattern).
  • i + z[i] == n marks a border of length n - i; the smallest such i gives the smallest period.
  • Always clamp with min(r - i, z[i - l]), and always use a separator that is not in either string.
  • KMP and Z solve the same problems in the same time; use whichever feels natural.

Next: Palindromic Substrings and Manacher, where a similar "reuse the mirror" idea finds palindromes in linear time.