Suppose we want to know how much of a string's prefix reappears at each later position. Comparing each suffix with the prefix independently is correct, but a repetitive string makes us verify the same relationships many times. For a string of identical characters, those independent scans take quadratic time.
The Z-array records all of these prefix-match lengths. Its linear-time computation reuses a previously verified matching interval, called a Z-box. The important question is how much that interval actually proves. Sometimes it determines the new answer completely; sometimes it proves only a lower bound, and comparisons must resume at its right boundary.
This representation differs from KMP's prefix-function state. We will derive its own invariant, then use the resulting array for exact pattern occurrences, suffix borders and periods. The code does not rely on hashing or probabilistic equality.
Define a match length with an explicit boundary
Let be a sequence of length , indexed from 0. A half-open segment contains positions . Tokens are compared by a consistent equality relation; for strings below they are Python string code points. No case conversion, Unicode normalization or grapheme grouping is implicit.
Definition 9.2.1
(Z-values and the zero-position convention)
For , define as the largest length for which
We set by convention; we do not use it to describe the full string's match with itself. The empty sequence has empty Z-array. A positive-position value zero means that the first tokens differ.
The upper bound matters: a match cannot run beyond the end of the suffix. If , the next comparison fails, so . If , the suffix is exhausted and there is no next token on that side to compare.
For example, aaaaa has Z-array . The decreasing values arise from suffix lengths, despite every available token being equal. Computing these lengths from scratch would repeat successful comparisons.
A known matching box gives two different kinds of information
Definition 9.2.2
(Z-box)
While processing indices , maintain a previously verified box with
Its right endpoint is the furthest reached by a previously computed match; initially . All earlier Z-values are already exact. An empty box is allowed. If , the box gives no positive-length information at , so begin with length zero and compare directly.
If , the position lies inside the box. Let . Position corresponds to prefix position , whose Z-value has already been computed. Within the box, we may safely copy
The cap is the amount of the old box still available. It is a boundary of established knowledge, rather than a claim that the real match must stop there.
Theorem 9.2.3
(Box reuse)
Let with , let , suppose is already exact, and put . Then , so . If moreover , then .
Proof
(Carrying equalities through the box)
For every , box equality gives , and the old value gives . Thus the first tokens really match the prefix.
If , the mismatch after the copied prefix also lies inside the box. The exact old Z-value gives , and box equality transports the latter token to . Hence the new match stops at exactly ; it cannot be longer.
If , the known equality reaches the box boundary. Nothing in the box certifies the next token, so the real match may stop there or extend beyond . Start direct comparisons after the copied tokens. Once a mismatch or the sequence end is reached, the new value is exact. If its endpoint exceeds , replace the box by .
Proof X-ray
The cap splits the proof into two cases
The cap separates two cases that use different kinds of facts. When , the proof uses two equalities (the box and the old Z-value) and one inequality, the old mismatch, transported through the box; an inequality is what fixes the answer. When , only equalities are available. They certify at most tokens and certify no inequality, which is exactly why direct comparison must restart at . The condition is what guarantees that is already exact when it is used. The counterexample below shows what goes wrong when the cap is dropped.
The referenced is an earlier value: any box used inside the loop began at an earlier positive position , so . The implementation can use one common comparison loop after copying; in the interior-mismatch case its first comparison simply confirms the known failure.
Counterexample mode
Copying beyond the old box can invent matching tokens
For aaab, position 1 has match length 2, so the box becomes . At position 2, and , but the available box suffix has length . The safe copied length is one.
The next comparison is prefix token a against the final b, so . Blindly copying the old value 2 would claim that suffix ab matches prefix aa. The old value describes a match at another position, whose extra token lies outside the equality supplied by this box.
A trace with both reuse cases
Worked example 9.2.4
(An interior answer stays fixed; a boundary answer may grow)
Take aabcaabxaaaz, with positions 0 through 11. Its full Z-array is . These selected steps expose the different cases:
| Position | Information before comparison | Exact value | Box afterward |
|---|---|---|---|
| 4 | Outside the old box; compare aab with the prefix | 3 | |
| 5 | , ; copy an interior mismatch | 1 | |
| 6 | , | 0 | |
| 8 | Outside; two a tokens match before a differs from prefix b | 2 | |
| 9 | Copy , then compare at position 10 | 2 | |
| 10 | Copy one to the boundary, then meet final z | 1 |
At position 9 the copied token is not the whole answer. The next a also matches prefix position 1, so the match grows to two; the final z then differs from prefix position 2, which is b. At position 5 the mismatch is already implied inside the box, so no successful extension is possible.
Worked example 9.2.5
(An exhausted suffix and the box that follows it)
For abcabc the Z-array is . Positions 1 and 2 fail at once, since b and c differ from a. At position 3 the suffix abc matches the prefix and is exhausted: , which also exhibits the border abc and the period 3. The box is now . At position 4, and , so the value is copied: . At position 5, and , so . The last two values need no new comparison beyond the known failure.
Why all comparison work is linear
Theorem 9.2.6
(Linear-time Z-array)
With constant-time indexing and token equality, the loop computes the Z-array of a sequence of length in time and cells.
Proof
(Charging successful comparisons to positions)
An outer iteration does constant work to choose its initial length. If a copied match ends strictly inside the old box, the known mismatch prevents any successful comparison. Otherwise, direct comparisons start at or beyond the old right endpoint .
Charge each successful comparison to its position on the suffix side. During an iteration these positions increase by one. By its end, the new box reaches beyond every such position. Since never decreases, a later iteration cannot successfully compare at a position that has already received this charge. There are at most chargeable positions, namely 1 through .
Each iteration also has at most one failed token comparison: the loop stops at its first mismatch. Reaching the sequence end may stop it without a failed comparison. There are iterations for , so total token comparisons and all remaining loop work are . A nested comparison loop therefore does not imply quadratic time here.
Proof X-ray
Why the right end of the box acts as a ratchet
Every successful direct comparison happens at a suffix position . In the interior-mismatch case no comparison succeeds. In the boundary case comparison starts at , and when it starts at . After the iteration , and never decreases, so can never be compared successfully again. The charge is thus on positions, not on iterations, which is why the loop nested inside the outer loop does not multiply the cost. Failed comparisons add at most one per iteration.
The Z-array uses cells; the box itself uses constant extra state. These bounds assume constant-time indexing and token equality. They do not apply unchanged if comparing one token itself requires a long computation.
Exact matching with a separator that cannot collide
Let the nonempty pattern be of length and the text be of length . Form a token sequence consisting of the pattern, one fresh separator token, then the text. The text begins at offset .
Theorem 9.2.7
(Occurrences from Z-values)
Let be nonempty of length , let have length , and let be the sequence , where the token equals no token of or . For we have , and occurs in at index if and only if .
Proof
(The fresh separator caps every value at m)
At a text index , the first tokens match the combined sequence's prefix exactly when the pattern occurs at . A fresh separator also ensures that the Z-value there cannot exceed : after matching tokens, the prefix presents the separator while the suffix presents a text token, or the text has already ended. Thus z[m + 1 + j] == m is an exact occurrence test.
Python strings contain character tokens, so a newly created object() placed in a list is unequal to every character token. We do not have to guess that a particular character such as # is absent from both inputs. The wrapper below uses this object as the separator and returns occurrence indices in increasing order, including overlapping occurrences.
def z_array(sequence):
n = len(sequence)
z = [0] * n
left = right = 0
for i in range(1, n):
if i < right:
z[i] = min(right - i, z[i - left])
while i + z[i] < n and sequence[z[i]] == sequence[i + z[i]]:
z[i] += 1
if i + z[i] > right:
left, right = i, i + z[i]
return z
def all_occurrences(pattern, text):
if pattern == "":
return list(range(len(text) + 1))
combined = list(pattern) + [object()] + list(text)
z = z_array(combined)
length = len(pattern)
offset = length + 1
return [i for i in range(len(text)) if z[offset + i] == length]
The wrapper accepts strings. The lower-level routine accepts a finite indexable sequence with the equality assumptions already stated. Neither mutates its input. Building the combined list, computing its Z-array and scanning text positions take time and cells, including the output bound of at most positions. For an empty pattern, the specified result is every boundary , handled before building the combined sequence.
Worked example 9.2.8
(Find both overlapping occurrences without consuming the first one)
For pattern aba and text ababa, write the unique separator as for display. This symbol denotes the object token, not a chosen input character. The combined tokens are a b a then then a b a b a, with Z-array .
The text offset is . The values at combined positions 4 and 6 both equal the pattern length 3, so the result is . The occurrences share the text token at position 2. Testing each starting position from the Z-array preserves that overlap instead of advancing past the whole first occurrence.
Counterexample mode
An ordinary separator character does not certify a length cap
Suppose pattern # and text ## are combined with another literal #. The result is ####, whose Z-array is . At the first text position, the Z-value is 2 rather than pattern length 1, because equality continues through the supposed separator.
Using an equality-to-length filter with that construction would miss the occurrence at text index 0. A greater-than-or-equal filter would still detect it, but the assertion that these Z-values are capped by the pattern length would be false. The fresh object establishes the precise invariant used by this implementation; a displayed punctuation mark does not establish freshness.
Borders and periods use the same exact values
Theorem 9.2.9
(Borders and periods from Z-values)
Let have length and let . The suffix is a proper border of exactly when , and its length is then . For , the number is a period of exactly when .
Proof
(Matching the whole suffix against the prefix)
A nonempty proper border is a prefix that is also a suffix, with length satisfying . Its suffix starts at , and the criterion is : the whole suffix matches the prefix. The cap in the definition rules out a longer value there. Scanning these suffix starts lists all proper border lengths in linear time.
For , call a period when for every . These are exactly the prefix-versus-suffix comparisons at position , so the criterion is . The full length is a trivial period when , but it has no in-range position z[n] and must not be tested by indexing the array there.
Common mistake
(A period does not mean whole copies)
A period need not divide the length. For ababa, , so 2 is a period, even though the string is not a concatenation of whole copies of ab. To obtain whole copies of a length- block, also require that divide . This distinction separates a repeated pattern that ends partway through its next copy from an exact concatenation.
Common mistake
(A Z-value is not a KMP border length)
The useful common feature is a proved equality of two segments. A Z-value is not the length of a previous occurrence of any substring, and it is not KMP's border length of the prefix ending at that position. Keep its prefix-versus-current-suffix meaning attached to each use.
Concept lensCombinatorial
The prefix function read from Z-values
For a position , a proper border of of length starts at some with , that is, . The longest border comes from the smallest such , so , and if no exists. Each Z-box lists the end positions where a border starting at is still alive.
Exercises with complete solutions
Quick check
(1. Give the Z-array of aaaaa using z[0]=0. At position 2 after the box [1,5) was found, why can z[1]=4 not be copied without a cap?)
Solution · 1. The available suffix limits the copied knowledge
The array is . At position 2 the box offers only tokens, and the whole suffix also has length three. Copying 4 would run beyond the sequence. The capped initial value is , and reaching the sequence end makes it the exact answer.
Quick check
(2. In aabcaabxaaaz, why is the value at position 5 exactly 1, while the copied value 1 at position 9 can grow to 2?)
Solution · 2. Locate the first unproved comparison
At position 5, box leaves two tokens, but ends strictly inside it. The mismatch is transported through the box, fixing the value at 1. At position 9, box leaves only one token, so the copied 1 reaches its boundary. Position 10 is new information and contains a, matching prefix position 1; the length grows to 2 before the final z mismatches prefix b.
Quick check
(3. For pattern aba in text ababa, what is the combined text offset and which combined Z-values certify the occurrences? Why is index 2 not skipped?)
Solution · 3. Translate combined indices back to text indices
The offset is . Combined positions 4 and 6 have Z-value 3, producing text starts and . The method checks every text starting position, rather than consuming a match and jumping ahead by its length, so the overlapping occurrence is retained.
Quick check
(4. Why does pattern # in text ## break the equality-to-length filter when a literal # is used as separator? What property of object() restores the implementation's proof?)
Solution · 4. Prove freshness rather than assume a missing character
The combined string is ####; its first text Z-value is 2, so equality to pattern length 1 fails even though a match exists there. A fresh object token differs from every string character. After matching the pattern, the next prefix token is that object and the suffix is either exhausted or contains a character, so the match cannot pass length one. Both text starts then have Z-value 1.
Quick check
(5. What should all_occurrences return for an empty pattern in text ab? What about a nonempty pattern in an empty text, or a pattern longer than the text?)
Solution · 5. Empty matches belong to boundaries
For the empty pattern in ab, the result is , one for every boundary. A nonempty pattern in empty text has no occurrence, so returns . A pattern longer than the text also returns , since no remaining text suffix can supply the required number of tokens. These outcomes follow from the wrapper's explicit convention and suffix-length bound, not from assigning a different meaning to .
Quick check
(6. The Z-array of ababa is [0,0,3,0,1]. Find its nonempty proper border lengths. Is 2 a period, and is the string made of whole copies of a length-two block?)
Solution · 6. A period can end with an incomplete copy
Positions 2 and 4 exhaust their suffixes with lengths 3 and 1, so the proper borders have lengths and . Since , 2 is a period. But 2 does not divide 5, so the string cannot be a concatenation of whole length-two blocks. It follows the repeating pattern ab only through the first token of the next copy.