On this page

The Z-Algorithm

Why this exists

Here is a question you can ask about any string: at each position, how much of the string's beginning is repeated there?

Take aabcaabxaaz. At position 4 the text reads aabx..., and the string starts with aabc.... The first three characters agree (aab), then x differs from c. So the answer at position 4 is 3. Write that number down for every position and you get the Z-array (also called the Z-function). It is one of the most useful arrays in string processing, because a lot of questions turn into "read the Z-array":

  • Does the pattern P occur in the text T? Glue them together as P + "$" + T and look for positions where the answer is len(P).
  • What is the shortest repeating unit of a string (its period)? The first position whose match runs all the way to the end.
  • Which prefixes are also suffixes (borders)? The positions whose match touches the end.
  • How many times does each prefix occur? Count how many Z values are at least its length.

Computing each answer separately, by comparing characters from scratch, can cost on a string like aaaa…a. The Z-algorithm computes the whole array in time. It does this with one idea: keep a window, the Z-box , which is a stretch of the string we already know is a copy of the beginning. Inside the window, we do not need to compare characters again: we can look up the answer we already computed at the matching spot near the start.

The algorithm is old and simple. The underlying "Z values" were presented as the fundamental preprocessing step in Dan Gusfield's textbook Algorithms on Strings, Trees, and Sequences (1997), which builds Boyer–Moore and KMP on top of it; the same linear-time computation is known in competitive programming as the Z-function and, in the Chinese-speaking community, as "extended KMP". If you have read KMP & the Prefix Function, you will see that the two arrays carry the same information arranged differently. This lesson shows exactly how, so you can choose the one that makes your problem easiest.

Pattern triggers

If the problem says or has…Think of…
"find all occurrences of a pattern", one pattern, exact matchZ on P + sep + T, positions with
"for every position, the longest common prefix with the whole string"That is the Z-array
"sum of scores of built strings", "score of each suffix against the string"Sum of the Z-array (plus for position 0)
"smallest period", "string is a repetition of a block", "compress as "First with (and for exact repetition)
"prefixes that are also suffixes", "borders", "happy prefix"Positions with ; border length
"how many times does each prefix occur"Count Z values with a suffix sum
"prefix that is also a suffix and also appears in the middle"Z-array plus a running maximum (Codeforces "Password")
"remove from the front, append anything, when does it come back"Check for
"longest palindromic prefix", "add characters in front to make a palindrome"Z on s + sep + reverse(s)
Matching where you can compare only equal / not equal, alphabet unknownZ or KMP (both use only equality tests)
Many patterns at onceNot Z: use Aho–Corasick
Streaming text you cannot store, one character at a timePrefer KMP: Z needs random access to the string

The meta-trigger: a question about how each position lines up with the start of the string. If the question is about lining up with the start of a different string, concatenate the two so that string becomes the start.

Intuition & first principles

The question, one position at a time

For a string of length , define

In words: put a second copy of under the original, shifted right by , and count how many characters match before the first mismatch (or before the shifted copy runs off the end).

By convention we set . (The "true" value would be , since the whole string matches itself, but that number is never useful during the algorithm and it would break the reuse step below. Some problems want ; set it after the computation if so.)

Here is the Z-array for our running example, with each value checked by hand:

012345678910
aabcaabxaaz
01003100210
  • : abcaab… versus aabcaa…. First characters a = a, then b ≠ a.
  • : position 2 starts with b, the string starts with a.
  • : aabx… versus aabc…. Three match, then x ≠ c.
  • : aaz versus aab. Two match, then z ≠ b.
  • Every position that does not start with a has .

The slow way and where it wastes work

The obvious method is two nested loops: for each , compare with , with , and so on until a mismatch. On aabcaabxaaz that costs 18 character comparisons. Not bad. But on aaaaaaaa (8 letters) it costs , and on a string of a thousand as it costs . The work is quadratic, because each position re-reads characters that a previous position already read.

Look at what the slow method learns at position 4 of our example: it finds , so it now knows that $s[4..6] = $ aab is an exact copy of . Then at position 5 it starts comparing from scratch. But position 5 is inside that copy. Whatever is true at position 1 of the original (the spot that corresponds to 5 inside the copy) is true at position 5, at least as long as we stay inside the copied stretch.

An everyday analogy: the photocopied pages

Imagine proofreading a long report. You discover that pages 40–46 are a photocopy of pages 1–7. Someone now asks, "how far does the text starting on page 42 agree with the start of the report?" You do not need to read page 42 at all. Page 42 is a copy of page 3, and you already answered that question for page 3 yesterday. If yesterday's answer stays within the copied pages, it is today's answer too. Only if yesterday's answer reaches the end of the copied pages do you have to keep reading, from page 47 onwards, because beyond the copy you know nothing.

That is the whole algorithm:

  • the copied pages are the Z-box : a stretch that we know equals ;
  • the matching page near the start is the mirror position ;
  • yesterday's answer is , already computed because ;
  • the end of the copy is , and we only ever read new characters beyond it.

Mechanics

The Z-box, drawn

A Z-box is the window found by some earlier position whose match reached furthest to the right; so . The algorithm keeps the Z-box with the largest seen so far. Here it is after position 4 in our example:

index:   0  1  2  3  4  5  6  7  8  9  10
s:       a  a  b  c  a  a  b  x  a  a  z
         [=======]  [=======]
         s[0..2]    s[4..6]       Z-box [l, r] = [4, 6], because z[4] = 3
            ^          ^
            k = 1      i = 5      mirror: k = i - l = 5 - 4 = 1

Because is a character-for-character copy of , the suffix starting at and the suffix starting at look identical until position . So the match at is at least : the mirror's answer, cut off at the edge of the box. Past the edge we have no information.

flowchart LR
    subgraph PRE["prefix s[0..r-l]"]
        K["mirror k = i - l"]
    end
    subgraph BOX["Z-box s[l..r]"]
        I["current i"]
    end
    PRE -- "identical characters" --- BOX
    K -. "z[k] is already known" .-> I
    BOX --> BEYOND["s[r+1..] is unknown: compare here only"]

The three cases

Position falls into one of three cases. The first two are Gusfield's case 1 and case 2a; the third is his case 2b.

flowchart TD
    S["next position i"] --> Q1{"i > r?"}
    Q1 -- "yes: outside every box" --> C1["Case 1: start at 0 and compare character by character"]
    Q1 -- "no: inside the box" --> Q2{"z[k] < r - i + 1?"}
    Q2 -- "yes: mirror's match ends inside the box" --> C2["Case 2a: z[i] = z[k], no new comparisons can succeed"]
    Q2 -- "no: mirror's match reaches the edge" --> C3["Case 2b: z[i] is at least r - i + 1, keep comparing past r"]
    C1 --> U["if the match ends beyond r, move the box to [i, i + z[i] - 1]"]
    C3 --> U
  1. Outside the box (). We know nothing about position . Compare from scratch, exactly like the slow method.
  2. Inside, and the mirror's match stops early (). Then exactly. The mirror's match stopped at a mismatch inside the copy; since the copy is identical, the same mismatch happens at . There is nothing to compare.
  3. Inside, and the mirror's match reaches the edge (). We know at least the part up to matches, so start at and compare characters beyond , which we have never seen.

The neat trick in the code is that one line, z[i] = min(r - i + 1, z[k]), handles both inside cases. In case 2a the minimum is and the following comparison loop fails at once; in case 2b it is and the loop continues past .

The algorithm

Z(s):
    n = length(s);  z[0..n-1] = 0;  l = r = 0      # box [l, r]; r = 0 means "no useful box yet"
    for i = 1 .. n-1:
        if i <= r:                                  # inside the box
            z[i] = min(r - i + 1, z[i - l])         # copy from the mirror, cut at the edge
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1                               # extend with fresh characters
        if z[i] > 0 and i + z[i] - 1 > r:           # reaches further right than the old box
            l, r = i, i + z[i] - 1
    return z

Three details matter:

  1. The box is inclusive. includes both ends, so the room left at is , not . Many published versions use a half-open box with min(r - i, z[i - l]) instead. Both are correct; mixing the two conventions is the most common bug.
  2. z[0] must be 0 during the loop (or simply never read). The mirror index is at least 1 because whenever is inside a box, so is never used as a mirror. It is still cleanest to leave it at 0 and fix it afterwards if needed.
  3. Only move the box to the right. The box changes only when the new match ends beyond . That rule is what makes the running time linear.

Worked example by hand

Let us run it on aabcaabxaaz the way you would at a whiteboard. I will write "box" for .

  • . No box yet, so start at 0. Compare = a with = a: match, . Compare = a with = b: mismatch. So . The match covers , which ends at 1, beyond the old , so the box becomes .
  • . Is ? No: outside. Compare = a with = b: mismatch at once. . The box does not move.
  • . Outside again. a versus c: mismatch. .
  • . Outside. Compare a/a, a/a, b/b: three matches. Then = c versus = x: mismatch. . The match covers , ending at 6 > 1, so the box becomes . We now know is a copy of .
  • . Inside the box (). The mirror is , with . The room left in the box is . Since , this is case 2a: with no work. (The loop does one comparison, = a versus = b, which fails, as the case analysis promised.)
  • . Inside. Mirror , , room 1. Case 2a again: . The loop's single comparison a versus b fails.
  • . : outside. a versus x: mismatch. .
  • . Outside. a/a, a/a match; = b versus = z mismatch. , and the box becomes .
  • . Inside. Mirror , , room . Now is not less than the room, so this is case 2b: start at 1 and compare beyond the box. = a versus = z: mismatch. .
  • . Outside. a versus z: mismatch. .

Result: , using 16 character comparisons instead of the slow method's 18. The saving here is small because the string has few repeats. On aaaaaaaa the saving is dramatic: the first position matches to the end and creates the box ; every later position is inside it with the room exactly equal to the answer, so the Z-algorithm uses 7 comparisons where the slow method uses 28. On 1,000 as it is 999 against 499,500.

Trace table

One row per position . "Start" is the value of before the comparison loop; "comparisons" counts successes / failures in the loop. The table was produced by a script running the code above, so every value is checked.

Box beforeInside? mirrorStartComparisons (ok / fail)Box after
1anoneout01 / 11[1, 1]
2b[1, 1]out00 / 10[1, 1]
3c[1, 1]out00 / 10[1, 1]
4a[1, 1]out03 / 13[4, 6]
5a[4, 6]in, , , room 210 / 11[4, 6]
6b[4, 6]in, , , room 100 / 10[4, 6]
7x[4, 6]out00 / 10[4, 6]
8a[4, 6]out02 / 12[8, 9]
9a[8, 9]in, , , room 110 / 11[8, 9]
10z[8, 9]out00 / 10[8, 9]

Read the "ok" column against the "Box after" column. There are 6 successful comparisons in total (1 + 3 + 2), and every one of them read a character to the right of the box as it was at that moment: positions 1, then 4, 5, 6, then 8, 9. After each run of successes the box moved right to cover the characters just read. The right end never moves left, so successes can never outnumber the positions sweeps over. That is the linear-time argument in miniature, and the visualizer below lets you watch it happen.

Inside the Z-box a position starts from its mirror's answer, so successful comparisons only ever read characters beyond r, which is why the algorithm is linear.

In the player, the shaded window is the Z-box, k marks the mirror whose answer is being reused, green cells are a successful comparison pair, and grey cells a mismatch. Watch steps 16 and 18: positions 5 and 6 get their values from the mirror with no successful comparison at all.

Pattern matching via P + "$" + T

The Z-array answers questions about the string's own beginning. To find a pattern (length ) in a text (length ), make the beginning: form

where $ is a separator, a character that occurs in neither nor . Compute the Z-array of . A position in the part with means the characters starting there equal : an occurrence of at text index .

Why the separator? It caps every Z value at . No match can run through it, because nothing in equals it. So "" is exactly "occurrence", and the Z values in the part never exceed , which also means the box never needs to stretch across the join.

Trace: P = aba, T = cabababa

= aba$cabababa, length 12. The text part starts at index .

Box beforeInside? mirrorStartComparisons (ok / fail)Box afterOccurrence?
1bnoneout00 / 10none(pattern part)
2anoneout01 / 11[2, 2](pattern part)
3$[2, 2]out00 / 10[2, 2]separator
4c[2, 2]out00 / 10[2, 2]no
5a[2, 2]out03 / 13[5, 7]yes, at index 1
6b[5, 7]in, , , room 200 / 10[5, 7]no
7a[5, 7]in, , , room 112 / 13[7, 9]yes, at index 3
8b[7, 9]in, , , room 200 / 10[7, 9]no
9a[7, 9]in, , , room 112 / 03[9, 11]yes, at index 5
10b[9, 11]in, , , room 200 / 10[9, 11]no
11a[9, 11]in, , , room 110 / 01[9, 11]no (only 1 char left)

. The matches at map to text indices , and , and indeed cabababa contains aba at 1, 3 and 5. They overlap (the a at text index 3 belongs to two matches); Z finds overlapping occurrences with no special handling.

Look at rows 7 and 9: these are case 2b. The mirror says "1 character matches", the room is exactly 1, so we continue past the box and find two more matching characters. At the third comparison hits the separator and fails, which is the separator doing its job.

Doing without the separator

Picking a separator is a nuisance when the input may contain any byte. There is a cleaner way: compute the Z-array of with no separator, and report every in the text part () with . Without the separator Z values in the text part can exceed (the match can run on into more text), but "at least " still means the characters starting at equal , and since , those characters all lie in . The implementation below uses this version; it is correct for every input, including inputs containing $.

A second alternative, used for integer sequences, is to map characters to non-negative integers and use as the separator.

The ladder: brute force → better → optimal

Problem: compute the full Z-array of a string of length (and, through it, find a pattern of length in a text of length ).

Rung 1: compare every pair of suffixes from scratch

For each , compare with character by character until a mismatch. worst case (all as), and on random text over a large alphabet, because most comparisons fail on the first character. Excellent as a test oracle; the implementation section checks the fast version against it on thousands of random strings.

Rung 2: binary search with hashing

With polynomial string hashing, you can test "is " in after preprocessing, and the property is monotone in , so binary search finds in . Total , with a tiny probability of error from hash collisions. Worth knowing because the same trick computes the longest common prefix of any two positions, which the Z-algorithm cannot.

Rung 3: the Z-algorithm

Reuse mirror values inside the Z-box and compare only beyond its right edge. worst case, deterministic, only equality comparisons, extra memory for the array itself.

Rung 4 (for matching only): KMP or Z, then constant factors

For finding in , both KMP and Z are and optimal: in the worst case any correct algorithm must read every text character. Beyond that, the improvements are practical, not asymptotic: KMP uses memory instead of and streams the text; Boyer–Moore-style algorithms skip characters on typical text (sublinear on average).

RungMethodTimeExtra spaceWhy it improves
1Compare every suffix with the start worst beyond outputBaseline and test oracle
2Binary search + rolling hashEach found by hash checks; Monte Carlo
3Z-algorithmInside the box, reuse the mirror; only ever advances
4KMP for matchingSame time, pattern-sized memory, works on a stream

Correctness

We need two facts: the value the algorithm starts from is never too large (so extending it can only reach the truth), and the comparison loop then finds the exact answer.

Invariant (the box is a true copy). Whenever the box is with , we have . This holds when the box is set: we set it to right after the comparison loop verified exactly those characters, and . Nothing changes the string, so it stays true until the box moves again.

Claim 1 (the start value is a lower bound). If and , then .

Let . Two facts:

  • Because : (that is what means).
  • Because : the stretch lies inside the box, so by the invariant it is a copy of (shift both by ).

Chain them: . So at least characters match at .

Claim 2 (case 2a is exact). If , then exactly.

The mirror's match stops at , where (it cannot stop by running off the end, because ). Position is still inside the box (), so . The match at stops at the same length. In the code this shows up as one comparison that fails immediately.

Claim 3 (the loop finishes the job). Starting from a correct lower bound, the while loop compares with and stops at the first mismatch or at the end of the string. That is the definition of . So every is exact.

Matching. For , at a text position means , which is an occurrence; conversely an occurrence gives matching characters, and the separator stops the match at exactly (the character after in is the separator, which matches nothing in , or the text has ended). For the separator-free version, with is the same statement without the cap.

Complexity

Time: , by watching . The only expensive part is the while loop. Split its comparisons into successes and failures.

  • Failures. Each position ends its loop with at most one failing comparison. That is at most failures in total.
  • Successes. Here is the amortised argument in plain words. When a comparison at position succeeds, it compares for some . Why beyond ? In case 1, already. In case 2b, we start at , so the first character compared is . In case 2a, no comparison succeeds. So every success reads a character to the right of the current box, and at the end of the loop the box is moved so that its right end covers that character. The right end only ever moves right, and it can never pass . So the total number of successes over the whole run is at most .

Together: at most character comparisons, plus bookkeeping per position. Linear. On aaaaaaaa the count was 7, and on aabcaabxaaz it was 16, both within .

This "something only moves forward, and every expensive step pushes it" argument is the same shape as the one for KMP (there the potential is the current match length) and for the two-pointer and sliding-window patterns in Module 1.

Space. for the Z-array; besides. For matching, because the array covers the concatenation. If memory matters, there is an -memory version that computes the Z-array of only and then scans with the same box logic (see Variations), but KMP is the more common way to get pattern-sized memory.

Best, average and worst. All three are : the loop visits every position. On random text over a large alphabet almost every position is case 1 with an immediate mismatch, so the constant is small. On highly repetitive text, almost every position is inside the box. The worst case for the comparison count is about , reached by strings that force one failure at nearly every position and many successes too.

Alphabet. Z uses only equality tests between characters. It never indexes a table by character, so the alphabet can be bytes, Unicode code points, integers or any objects with ==. Compare tries and Aho–Corasick, which need a child table per node.

Implementation

The Z-function, plus pattern search using the separator-free concatenation. Every language asserts the arrays from the traces above: aabcaabxaaz, aaaaa, aba$cabababa, the empty string, overlapping matches (aa in aaaa) and a pattern longer than the text. The Python version was also checked against the brute-force definition on 3,000 random strings.

def z_function(s):
    """z[i] = length of the longest common prefix of s and s[i:]; z[0] = 0 by convention."""
    n = len(s)
    z = [0] * n
    l = r = 0                      # Z-box [l, r]: s[l..r] == s[0..r-l]
    for i in range(1, n):
        if i <= r:                 # inside the box: copy from the mirror, capped by the box
            z[i] = min(r - i + 1, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1              # every success here moves the box's right end
        if z[i] > 0 and i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1
    return z


def find_all(text, pattern):
    """Start indices of pattern in text, via the Z-array of pattern + text."""
    m = len(pattern)
    if m == 0:
        return list(range(len(text) + 1))
    z = z_function(pattern + text)   # no separator: we only look at i >= m
    return [i - m for i in range(m, m + len(text)) if z[i] >= m]


if __name__ == "__main__":
    assert z_function("aabcaabxaaz") == [0, 1, 0, 0, 3, 1, 0, 0, 2, 1, 0]
    assert z_function("aaaaa") == [0, 4, 3, 2, 1]
    assert z_function("abacaba") == [0, 0, 1, 0, 3, 0, 1]
    assert z_function("aba$cabababa") == [0, 0, 1, 0, 0, 3, 0, 3, 0, 3, 0, 1]
    assert z_function("") == [] and z_function("x") == [0]
    assert find_all("cabababa", "aba") == [1, 3, 5]
    assert find_all("aaaa", "aa") == [0, 1, 2]
    assert find_all("abc", "abcd") == [] and find_all("abc", "") == [0, 1, 2, 3]
    print("ok")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ZAlgorithm {
    /** z[i] = length of the longest common prefix of s and s.substring(i); z[0] = 0 by convention. */
    static int[] zFunction(String s) {
        int n = s.length();
        int[] z = new int[n];
        int l = 0, r = 0;                       // Z-box [l, r]
        for (int i = 1; i < n; i++) {
            if (i <= r) z[i] = Math.min(r - i + 1, z[i - l]);
            while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) z[i]++;
            if (z[i] > 0 && i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; }
        }
        return z;
    }

    /** Start indices of pattern in text, via the Z-array of pattern + text. */
    static List<Integer> findAll(String text, String pattern) {
        int m = pattern.length(), n = text.length();
        List<Integer> out = new ArrayList<>();
        if (m == 0) { for (int i = 0; i <= n; i++) out.add(i); return out; }
        int[] z = zFunction(pattern + text);    // only positions i >= m are used
        for (int i = m; i < m + n; i++) if (z[i] >= m) out.add(i - m);
        return out;
    }

    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }

    public static void main(String[] args) {
        check(Arrays.equals(zFunction("aabcaabxaaz"), new int[]{0, 1, 0, 0, 3, 1, 0, 0, 2, 1, 0}), "aabcaabxaaz");
        check(Arrays.equals(zFunction("aaaaa"), new int[]{0, 4, 3, 2, 1}), "aaaaa");
        check(Arrays.equals(zFunction("aba$cabababa"), new int[]{0, 0, 1, 0, 0, 3, 0, 3, 0, 3, 0, 1}), "P$T");
        check(zFunction("").length == 0, "empty");
        check(findAll("cabababa", "aba").equals(Arrays.asList(1, 3, 5)), "find aba");
        check(findAll("aaaa", "aa").equals(Arrays.asList(0, 1, 2)), "find aa");
        check(findAll("abc", "abcd").isEmpty(), "too long");
        System.out.println("ok");
    }
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

// z[i] = length of the longest common prefix of s and s.substr(i); z[0] = 0 by convention.
std::vector<int> zFunction(const std::string& s) {
    int n = static_cast<int>(s.size());
    std::vector<int> z(n, 0);
    int l = 0, r = 0;                           // Z-box [l, r]
    for (int i = 1; i < n; ++i) {
        if (i <= r) z[i] = std::min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
        if (z[i] > 0 && i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; }
    }
    return z;
}

// Start indices of pattern in text, via the Z-array of pattern + text.
std::vector<int> findAll(const std::string& text, const std::string& pattern) {
    int m = static_cast<int>(pattern.size()), n = static_cast<int>(text.size());
    std::vector<int> out;
    if (m == 0) { for (int i = 0; i <= n; ++i) out.push_back(i); return out; }
    std::vector<int> z = zFunction(pattern + text);   // only positions i >= m are used
    for (int i = m; i < m + n; ++i) if (z[i] >= m) out.push_back(i - m);
    return out;
}

int main() {
    assert((zFunction("aabcaabxaaz") == std::vector<int>{0, 1, 0, 0, 3, 1, 0, 0, 2, 1, 0}));
    assert((zFunction("aaaaa") == std::vector<int>{0, 4, 3, 2, 1}));
    assert((zFunction("aba$cabababa") == std::vector<int>{0, 0, 1, 0, 0, 3, 0, 3, 0, 3, 0, 1}));
    assert(zFunction("").empty());
    assert((findAll("cabababa", "aba") == std::vector<int>{1, 3, 5}));
    assert((findAll("aaaa", "aa") == std::vector<int>{0, 1, 2}));
    assert(findAll("abc", "abcd").empty());
    std::cout << "ok\n";
    return 0;
}
/** z[i] = length of the longest common prefix of s and s.slice(i); z[0] = 0 by convention. */
export function zFunction(s: string): number[] {
  const n = s.length;
  const z: number[] = new Array(n).fill(0);
  let l = 0;
  let r = 0; // Z-box [l, r]
  for (let i = 1; i < n; i++) {
    if (i <= r) z[i] = Math.min(r - i + 1, z[i - l]);
    while (i + z[i] < n && s[z[i]] === s[i + z[i]]) z[i]++;
    if (z[i] > 0 && i + z[i] - 1 > r) {
      l = i;
      r = i + z[i] - 1;
    }
  }
  return z;
}

/** Start indices of pattern in text, via the Z-array of pattern + text. */
export function findAll(text: string, pattern: string): number[] {
  const m = pattern.length;
  const n = text.length;
  if (m === 0) return Array.from({ length: n + 1 }, (_, i) => i);
  const z = zFunction(pattern + text); // only positions i >= m are used
  const out: number[] = [];
  for (let i = m; i < m + n; i++) if (z[i] >= m) out.push(i - m);
  return out;
}

const same = (a: number[], b: number[]): boolean => a.length === b.length && a.every((x, i) => x === b[i]);
if (!same(zFunction("aabcaabxaaz"), [0, 1, 0, 0, 3, 1, 0, 0, 2, 1, 0])) throw new Error("aabcaabxaaz");
if (!same(zFunction("aaaaa"), [0, 4, 3, 2, 1])) throw new Error("aaaaa");
if (!same(zFunction("aba$cabababa"), [0, 0, 1, 0, 0, 3, 0, 3, 0, 3, 0, 1])) throw new Error("P$T");
if (zFunction("").length !== 0) throw new Error("empty");
if (!same(findAll("cabababa", "aba"), [1, 3, 5])) throw new Error("find aba");
if (!same(findAll("aaaa", "aa"), [0, 1, 2])) throw new Error("find aa");
if (findAll("abc", "abcd").length !== 0) throw new Error("too long");
console.log("ok");

Language notes. In Java, s.charAt on a String is fast, but for very long inputs converting once with toCharArray() avoids repeated bounds checks. In C++, std::string concatenation copies both strings; for huge texts compute the Z-array of the pattern and use the two-string variant below. JavaScript strings index by UTF-16 code unit, so a character outside the Basic Multilingual Plane (most emoji) counts as two positions; convert with Array.from(s) first if you need code points. Python's s[i] creates a one-character string each time, so the pure-Python version runs at a few million characters per second; that is fine for interviews and most contest limits up to about .

Z versus the prefix function

KMP's prefix function is the length of the longest proper prefix of that is also a suffix of (a border of that prefix). The Z-array is the length of the longest prefix of that starts at . One array is indexed by where a copy of the beginning ends, the other by where it starts.

Both describe the same set of facts: all the places where a prefix of reappears. A copy of starting at position is the same thing as a border of length of the prefix ending at :

The Z-array records, for each start , the longest such . The prefix function records, for each end , the longest such ; and the chain lists every shorter one. Since each array lets you list all the (start, length) pairs, each determines the other. Two strings have the same Z-array if and only if they have the same prefix function.

flowchart LR
    F["facts: prefix s[0..L-1] reappears at start i, ending at e = i + L - 1"]
    F -- "group by start i, keep the longest L" --> Z["Z-array z[i]"]
    F -- "group by end e, keep the longest L" --> P["prefix function pi[e]"]
    Z -- "z_to_pi: O(n)" --> P
    P -- "pi_to_z: rebuild a string, run Z: O(n)" --> Z

Worked conversion on ababcabab

012345678
ababcabab
002004020
001201234

Z → π. Each says "a copy of the beginning of length starts at ". Its prefixes are copies too, so position ends a border of length for every . Walk left to right; for each fill for down to , and stop as soon as you meet a cell that is already filled. An earlier start that reached the same end position gave a longer border there, and also filled all the cells to its left that you would fill.

  • , : fill , .
  • , : fill , , , .
  • , : is already 4: stop at once.
  • Cells never filled stay 0: .

Each cell is filled at most once and each has at most one "already filled" check, so this is .

π → Z. The direct conversion is fiddly. A clean route uses the fact that only the equality pattern matters: rebuild a string with the given prefix function, then run the Z-algorithm on it. Rebuilding is easy. Go left to right; if , the character at must equal the character at (the border extends by that character), so copy it; if , use a brand-new symbol. For ababcabab this produces ABABCABAB (new symbols at positions 0, 1 and 4), the same string up to renaming. For abcb, whose prefix function is all zeros, it produces ABCD: a different string, but with the same prefix function and therefore the same Z-array (all zeros).

Deeper: why the rebuilt string has the right prefix function

Call the original string and the rebuilt one . By construction, implies : every copy step in follows an equality that holds in (a border extends by equal characters), and new symbols are equal to nothing. Now run the prefix-function computation on both strings in parallel. By induction the candidate chains are identical (they only depend on earlier values). At position , every candidate longer than failed in (characters differ), so it fails in too, because equality in implies equality in . The candidate succeeds in by construction, and when the new symbol fails every candidate. So has exactly the prefix function . The same idea underlies the literature on checking and reconstructing strings from border arrays (for example Duval, Lecroq and Lefebvre, 2005). The randomised cross-check in the code below tests it on 5,000 strings.

Both conversions, in four languages, with the ababcabab example asserted and a randomised cross-check of 5,000 strings over alphabets of size 1–3 (both directions must reproduce the directly computed array):

import random


def prefix_function(s):
    pi = [0] * len(s)
    for i in range(1, len(s)):
        k = pi[i - 1]
        while k > 0 and s[i] != s[k]:
            k = pi[k - 1]
        if s[i] == s[k]:
            k += 1
        pi[i] = k
    return pi


def z_function(s):
    n = len(s)
    z = [0] * n
    l = r = 0
    for i in range(1, n):
        if i <= r:
            z[i] = min(r - i + 1, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if z[i] > 0 and i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1
    return z


def z_to_pi(z):
    """Each z[i] > 0 says position i+j ends a border of length j+1; the first writer is the longest."""
    n = len(z)
    pi = [0] * n
    for i in range(1, n):
        for j in range(z[i] - 1, -1, -1):
            if pi[i + j] > 0:
                break
            pi[i + j] = j + 1
    return pi


def pi_to_z(pi):
    """Rebuild a string with this prefix function (fresh symbol when pi[i] == 0), then run Z."""
    s, fresh = [], 0
    for p in pi:
        if p == 0:
            s.append(fresh)
            fresh += 1
        else:
            s.append(s[p - 1])
    return z_function(s)


if __name__ == "__main__":
    s = "ababcabab"
    assert prefix_function(s) == [0, 0, 1, 2, 0, 1, 2, 3, 4]
    assert z_function(s) == [0, 0, 2, 0, 0, 4, 0, 2, 0]
    for _ in range(5000):
        t = [random.randrange(random.randint(1, 3)) for _ in range(random.randint(0, 15))]
        assert z_to_pi(z_function(t)) == prefix_function(t), t
        assert pi_to_z(prefix_function(t)) == z_function(t), t
    print("ok")
import java.util.Arrays;
import java.util.Random;

public class Convert {
    static int[] prefixFunction(int[] s) {
        int[] pi = new int[s.length];
        for (int i = 1; i < s.length; i++) {
            int k = pi[i - 1];
            while (k > 0 && s[i] != s[k]) k = pi[k - 1];
            if (s[i] == s[k]) k++;
            pi[i] = k;
        }
        return pi;
    }

    static int[] zFunction(int[] s) {
        int n = s.length, l = 0, r = 0;
        int[] z = new int[n];
        for (int i = 1; i < n; i++) {
            if (i <= r) z[i] = Math.min(r - i + 1, z[i - l]);
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
            if (z[i] > 0 && i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; }
        }
        return z;
    }

    /** Each z[i] > 0 says position i + j ends a border of length j + 1; the first writer is the longest. */
    static int[] zToPi(int[] z) {
        int[] pi = new int[z.length];
        for (int i = 1; i < z.length; i++)
            for (int j = z[i] - 1; j >= 0 && pi[i + j] == 0; j--) pi[i + j] = j + 1;
        return pi;
    }

    /** Rebuild a string with this prefix function (fresh symbol when pi[i] == 0), then run Z on it. */
    static int[] piToZ(int[] pi) {
        int[] s = new int[pi.length];
        int fresh = 0;
        for (int i = 0; i < pi.length; i++) s[i] = pi[i] == 0 ? fresh++ : s[pi[i] - 1];
        return zFunction(s);
    }

    public static void main(String[] args) {
        int[] s = "ababcabab".chars().toArray();
        if (!Arrays.equals(prefixFunction(s), new int[]{0, 0, 1, 2, 0, 1, 2, 3, 4})) throw new AssertionError("pi");
        if (!Arrays.equals(zFunction(s), new int[]{0, 0, 2, 0, 0, 4, 0, 2, 0})) throw new AssertionError("z");
        Random rnd = new Random(7);
        for (int it = 0; it < 5000; it++) {
            int[] t = new int[rnd.nextInt(16)];
            int sigma = 1 + rnd.nextInt(3);
            for (int i = 0; i < t.length; i++) t[i] = rnd.nextInt(sigma);
            if (!Arrays.equals(zToPi(zFunction(t)), prefixFunction(t))) throw new AssertionError("z->pi");
            if (!Arrays.equals(piToZ(prefixFunction(t)), zFunction(t))) throw new AssertionError("pi->z");
        }
        System.out.println("ok");
    }
}
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <vector>

std::vector<int> prefixFunction(const std::vector<int>& s) {
    std::vector<int> pi(s.size(), 0);
    for (std::size_t i = 1; i < s.size(); ++i) {
        int k = pi[i - 1];
        while (k > 0 && s[i] != s[k]) k = pi[k - 1];
        if (s[i] == s[k]) ++k;
        pi[i] = k;
    }
    return pi;
}

std::vector<int> zFunction(const std::vector<int>& s) {
    int n = static_cast<int>(s.size()), l = 0, r = 0;
    std::vector<int> z(n, 0);
    for (int i = 1; i < n; ++i) {
        if (i <= r) z[i] = std::min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
        if (z[i] > 0 && i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; }
    }
    return z;
}

// Each z[i] > 0 says position i + j ends a border of length j + 1; the first writer is the longest.
std::vector<int> zToPi(const std::vector<int>& z) {
    std::vector<int> pi(z.size(), 0);
    for (std::size_t i = 1; i < z.size(); ++i)
        for (int j = z[i] - 1; j >= 0 && pi[i + j] == 0; --j) pi[i + j] = j + 1;
    return pi;
}

// Rebuild a string with this prefix function (fresh symbol when pi[i] == 0), then run Z on it.
std::vector<int> piToZ(const std::vector<int>& pi) {
    std::vector<int> s(pi.size());
    int fresh = 0;
    for (std::size_t i = 0; i < pi.size(); ++i) s[i] = pi[i] == 0 ? fresh++ : s[pi[i] - 1];
    return zFunction(s);
}

int main() {
    std::vector<int> s = {'a', 'b', 'a', 'b', 'c', 'a', 'b', 'a', 'b'};
    assert((prefixFunction(s) == std::vector<int>{0, 0, 1, 2, 0, 1, 2, 3, 4}));
    assert((zFunction(s) == std::vector<int>{0, 0, 2, 0, 0, 4, 0, 2, 0}));
    std::srand(7);
    for (int it = 0; it < 5000; ++it) {
        std::vector<int> t(std::rand() % 16);
        int sigma = 1 + std::rand() % 3;
        for (std::size_t i = 0; i < t.size(); ++i) t[i] = std::rand() % sigma;
        assert(zToPi(zFunction(t)) == prefixFunction(t));
        assert(piToZ(prefixFunction(t)) == zFunction(t));
    }
    std::cout << "ok\n";
    return 0;
}
export function prefixFunction(s: ArrayLike<number>): number[] {
  const pi: number[] = new Array(s.length).fill(0);
  for (let i = 1; i < s.length; i++) {
    let k = pi[i - 1];
    while (k > 0 && s[i] !== s[k]) k = pi[k - 1];
    if (s[i] === s[k]) k++;
    pi[i] = k;
  }
  return pi;
}

export function zFunction(s: ArrayLike<number>): number[] {
  const n = s.length;
  const z: number[] = new Array(n).fill(0);
  let l = 0;
  let r = 0;
  for (let i = 1; i < n; i++) {
    if (i <= r) z[i] = Math.min(r - i + 1, z[i - l]);
    while (i + z[i] < n && s[z[i]] === s[i + z[i]]) z[i]++;
    if (z[i] > 0 && i + z[i] - 1 > r) {
      l = i;
      r = i + z[i] - 1;
    }
  }
  return z;
}

/** Each z[i] > 0 says position i + j ends a border of length j + 1; the first writer is the longest. */
export function zToPi(z: number[]): number[] {
  const pi: number[] = new Array(z.length).fill(0);
  for (let i = 1; i < z.length; i++) {
    for (let j = z[i] - 1; j >= 0 && pi[i + j] === 0; j--) pi[i + j] = j + 1;
  }
  return pi;
}

/** Rebuild a string with this prefix function (fresh symbol when pi[i] === 0), then run Z on it. */
export function piToZ(pi: number[]): number[] {
  const s: number[] = [];
  let fresh = 0;
  for (let i = 0; i < pi.length; i++) s.push(pi[i] === 0 ? fresh++ : s[pi[i] - 1]);
  return zFunction(s);
}

const same = (a: number[], b: number[]): boolean => a.length === b.length && a.every((x, i) => x === b[i]);
const codes = (t: string): number[] => Array.from(t, (c) => c.charCodeAt(0));
if (!same(prefixFunction(codes("ababcabab")), [0, 0, 1, 2, 0, 1, 2, 3, 4])) throw new Error("pi");
if (!same(zFunction(codes("ababcabab")), [0, 0, 2, 0, 0, 4, 0, 2, 0])) throw new Error("z");
for (let it = 0; it < 5000; it++) {
  const sigma = 1 + Math.floor(Math.random() * 3);
  const t = Array.from({ length: Math.floor(Math.random() * 16) }, () => Math.floor(Math.random() * sigma));
  if (!same(zToPi(zFunction(t)), prefixFunction(t))) throw new Error("z->pi " + t);
  if (!same(piToZ(prefixFunction(t)), zFunction(t))) throw new Error("pi->z " + t);
}
console.log("ok");

When to pick each

They are interchangeable in power, so pick by convenience:

SituationPickWhy
One pattern, one text, everything in memoryEitherBoth ; Z on P + T is the shortest code to get right
Text arrives as a stream, cannot be storedPrefix function (KMP)KMP reads each text character once, in order, with memory; Z needs random access to the whole concatenation
"For each position, how much of the start matches here?" (scores, LCP with the string)ZIt is literally the Z-array
Periods, borders, "is it a repetition"EitherZ: first with ; π:
Count occurrences of every prefixZ (or π with a chain count)Z: count values ; π needs the extra "propagate along the chain" pass
Build an automaton, add characters online, multi-patternPrefix functionThe prefix function extends to the KMP automaton and to Aho–Corasick; Z has no automaton form
Appending characters to the string one at a timePrefix functionπ of a new character depends only on earlier values; Z values of earlier positions can change when you append
Comparing with a reversed string (palindromic prefix)EitherZ on s + sep + rev(s) or π on the same string

A rule of thumb from competitive programmers: Z when the question is phrased by starting positions, π when it is phrased by ending positions or arrives online.

Applications

Each of these is a few lines on top of the Z-array. All were checked against brute force on thousands of random strings.

Smallest period. A string has period ( for all ) exactly when the shift by matches all the way to the end: . The smallest such (or if none) is the smallest period. If you need to be an exact repetition (), additionally require . Example: abcabca has periods 3, 6 and 7 (abc repeated, cut off).

Borders. A border of length is a prefix equal to the suffix of the same length; that suffix starts at , so is a border exactly when , i.e. with . Example: abcababcab has borders 2 (ab) and 5 (abcab).

Occurrences of every prefix. The prefix of length occurs at position exactly when (with treated as ). Count how many positions have each Z value, then take suffix sums: . For ABACABA the borders are 1, 3, 7, occurring 4, 2 and 1 times.

String compression in a tight loop. "Write as with largest" is the smallest with .

Longest palindromic prefix. is a palindrome exactly when the suffix of of length equals the prefix of of length . Run Z on s + "#" + rev(s) and take the largest with equal to the total length. That answers "shortest palindrome by adding characters in front" (LeetCode 214): put the reverse of the rest in front.

Number of distinct substrings, incrementally (). Add characters one at a time. When you append to , the new substrings are suffixes of ; reverse and compute its Z-array; the suffixes that already occurred are exactly the prefixes of the reversed string that occur again, whose number is . So the count increases by . This gives total, fine for and a nice exercise; suffix arrays do it in .

Real-world uses

The Z-algorithm is mostly a teaching and contest tool. Production string search usually relies on Boyer–Moore variants, SIMD byte scanning, Aho–Corasick or regular-expression engines. But the Z idea is inside several real systems:

  • Boyer–Moore preprocessing. Gusfield's textbook derives the Boyer–Moore good suffix table from Z values computed on the reversed pattern (his values), and the same "longest match ending here" information appears in standard implementations. If you ever implement Boyer–Moore from scratch, the Z-algorithm is the cleanest way to get its hardest table right.
  • Bioinformatics: tandem repeats. Finding all tandem repeats (squares like ACGACG) in DNA, which matter because short tandem repeats are used in genetic fingerprinting, is solved by the Main–Lorentz divide-and-conquer algorithm (1984). Its key step computes, across the split point, longest-common-prefix and longest-common-suffix values that are exactly Z-arrays of concatenated strings. Total .
  • Exact matching of short reads and motifs. For a single short motif against a long sequence, Z on motif + sep + sequence is a standard textbook method (Gusfield, chapter 1), and its use of only equality comparisons makes it work unchanged over any encoding of nucleotides or amino acids.
  • Compression and diffing heuristics. "How long does the data starting here match the data starting at the beginning of the window?" is the question behind LZ-family match finding for one fixed reference position. Real compressors use hash chains or suffix structures because they need matches against every earlier position, but the Z-array is the exact answer for one reference point and appears in teaching implementations of LZ77 factorisation.
  • Testing and competitive programming. Z is the standard way to answer "LCP of every suffix with the whole string" in contest problems, and the shortest correct code for single-pattern matching under time pressure.

Pitfalls & edge cases

  • Inclusive versus half-open box. With inclusive, the room is and the update is r = i + z[i] - 1. With half-open, the room is and the update is r = i + z[i]. Mixing them gives an off-by-one that passes small tests and fails on repetitive strings. Pick one and write it in a comment.
  • Empty box updates. With an inclusive box, a position with would set an "empty box" if you forget the z[i] > 0 guard. It happens to be harmless (no later position falls inside it), but it is confusing when you debug; the guard keeps the box meaningful.
  • z[0]. Leave it 0 during the computation. If the problem wants (sum of scores, prefix-occurrence counts), set it after the loop. Setting it to before the loop is also safe in the standard code because , but many variants are not.
  • Separator inside the input. P + "$" + T silently breaks when $ occurs in the text or the pattern: a match can run through the separator and can exceed . Use the separator-free check , or a sentinel outside the alphabet (an integer like on integer arrays).
  • Reading past the end. The loop condition must test i + z[i] < n before indexing s[i + z[i]]. In C++ and Java the order of && makes this safe; do not swap the operands.
  • Mapping positions back. With the separator, a match at in is at text index ; without it, at . Off by one here is the most common bug in contest submissions.
  • Pattern longer than the text, empty pattern. Return no matches when . For an empty pattern, decide a convention (every index , as str.find would suggest) and test it.
  • Unicode. In JavaScript and Java, length and indexing count UTF-16 code units. A pattern containing an emoji is two "characters". Normalise (NFC) and convert to code points if the input is user text; see Strings in Depth.
  • Concatenation cost. P + T copies both strings. For a 1 GB text this doubles memory. Use the two-string variant (Z of , then scan ) or KMP.
  • Python speed. The pure-Python loop handles about characters in roughly a second; for larger inputs use built-in str.find in a loop (implemented in C) or vectorised approaches.

Variations

  • Two-string Z ("extended KMP"). Compute = the longest common prefix of and without concatenating. First compute the Z-array of , then sweep with the same box logic, using 's Z-array for the mirror lookups. Memory besides the output. This is what "扩展KMP" (extended KMP) refers to in Chinese textbooks.
  • Suffix version. Reverse the string, compute Z, reverse the result: you get, for each position, the longest common suffix of and . Combining prefix and suffix versions gives matching with one mismatch: an occurrence of with at most one wrong character at is where .
  • Integer sequences and shapes. Z works on any array with equality. To find a melody regardless of key, or a price pattern regardless of level, run Z on the sequence of differences between consecutive values.
  • Main–Lorentz repetitions. Divide and conquer plus Z-arrays across the split point find all tandem repeats in .
  • Z on a cyclic string. Run Z on (positions give comparisons of every rotation with , capped at ). Rotation equality ("is a rotation of ?") is found in .
  • Hash-based LCP. For LCP between two arbitrary positions, not just "with the start", use hashing with binary search or a suffix array with LCP and RMQ.
  • Prefix function. The dual array, covered in KMP & the Prefix Function. The conversions above show they are two views of the same information.

Practice ladder

Each problem is described in my own words; follow the link for the full statement.

1. Find the Index of the First Occurrence in a String (LeetCode 28) — Return where a needle first appears in a haystack, or . Teaches the concatenation trick end to end.

Hint

Z of needle + haystack; the first with gives index .

2. String Matching (CSES 1753) — Count the occurrences of a pattern in a string of up to characters. Teaches overlapping matches and linear time under a real limit.

Hint

Same as problem 1, but count instead of returning the first. In Python, read input with sys.stdin and keep the loop tight.

3. Sum of Scores of Built Strings (LeetCode 2223) — A string is built by prepending characters; the score of each stage is its longest common prefix with the final string. Sum all scores. Teaches recognising the Z-array in disguise.

Hint

Each built stage is a suffix of the final string, and its score is , with the full string scoring .

Solution
def sum_scores(s):
    z = z_function(s)               # from the implementation above
    return len(s) + sum(z[1:]) if s else 0

assert sum_scores("babab") == 9     # 5 + 0 + 3 + 0 + 1

4. Longest Happy Prefix (LeetCode 1392) — Longest proper prefix that is also a suffix. Teaches borders from Z.

Hint

The smallest with gives the longest border, of length .

5. Finding Borders (CSES 1732) — List every border length in increasing order. Teaches enumerating all positions where a match touches the end.

Solution
def borders(s):
    n = len(s)
    z = z_function(s)
    return [n - i for i in range(n - 1, 0, -1) if i + z[i] == n]   # increasing lengths

assert borders("abcababcab") == [2, 5]

6. Finding Periods (CSES 1733) — List every period length (the string is a prefix of an infinite repetition of its first characters). Teaches the period/Z link.

Solution
def periods(s):
    n = len(s)
    z = z_function(s)
    return [p for p in range(1, n) if p + z[p] == n] + [n]

assert periods("abcabca") == [3, 6, 7]

7. Repeated Substring Pattern (LeetCode 459) — Is the string a block repeated two or more times? Teaches the extra divisibility condition.

Hint

Some with and . (The famous one-liner checks whether occurs in (s + s)[1:-1], which is the same fact seen through rotations.)

8. Shortest Palindrome (LeetCode 214) — Add the fewest characters in front to make a palindrome. Teaches the longest palindromic prefix through a reversed concatenation.

Solution
def shortest_palindrome(s):
    n = len(s)
    if n == 0:
        return s
    rev = s[::-1]
    z = z_function(s + "#" + rev)       # '#' is not a lowercase letter
    best = 0
    for i in range(n + 1, 2 * n + 1):   # positions in the reversed part
        if i + z[i] == 2 * n + 1:       # match runs to the end: a suffix of rev equals a prefix of s
            best = max(best, z[i])
    return rev[:n - best] + s

assert shortest_palindrome("aacecaaa") == "aaacecaaa"
assert shortest_palindrome("abcd") == "dcbabcd"

The longest palindromic prefix has length best; everything after it, reversed, goes in front.

9. Password (Codeforces 126B) — Find the longest substring that is a prefix, a suffix, and also occurs somewhere strictly inside. Teaches combining borders with a running maximum.

Solution
def password(s):
    n = len(s)
    z = z_function(s)
    best_before = 0                         # max z[j] over 1 <= j < i
    for i in range(1, n):
        if i + z[i] == n and best_before >= z[i]:
            return s[:z[i]]                 # the first such i gives the longest border
        best_before = max(best_before, z[i])
    return "Just a legend"

assert password("fixprefixsuffix") == "fix"
assert password("abcdabc") == "Just a legend"

Why only : a middle occurrence of a border of length must start before , otherwise it would run past the end. And a with that starts before ends before , so it is neither the prefix nor the suffix occurrence.

10. Prefixes and Suffixes (Codeforces 432D) — For every prefix that is also a suffix, print how many times it occurs as a substring. Teaches counting with Z values and suffix sums.

Solution
def prefixes_suffixes(s):
    n = len(s)
    z = z_function(s)
    z[0] = n                                 # the whole string matches itself
    cnt = [0] * (n + 2)
    for v in z:
        cnt[v] += 1
    for L in range(n - 1, 0, -1):            # cnt[L] = number of positions with z >= L
        cnt[L] += cnt[L + 1]
    return [(L, cnt[L]) for L in range(1, n + 1) if L == n or z[n - L] == L]

assert prefixes_suffixes("ABACABA") == [(1, 4), (3, 2), (7, 1)]

11. Minimum Time to Revert Word to Initial State II (LeetCode 3031) — Each second, delete the first characters and append any characters. Find the first second at which the word can be back to its original form. Teaches turning a simulation into a Z query.

Hint

After seconds, the untouched part is the suffix starting at , and you can write anything after it. So the word can revert when or .

Solution
def revert_time(word, k):
    n = len(word)
    z = z_function(word)
    t = 1
    while t * k < n and z[t * k] < n - t * k:
        t += 1
    return t

assert revert_time("abacaba", 3) == 2
assert revert_time("abacaba", 4) == 1
assert revert_time("abcbabcd", 2) == 4

12. Find Beautiful Indices in the Given Array II (LeetCode 3008) — Report the occurrences of one pattern that have some occurrence of a second pattern within distance . Teaches combining two matching runs with a sorted merge.

Hint

Two Z runs give two sorted lists of occurrences. Sweep them with two pointers (or binary search each in the second list) to test . Total .

Common mistakes & interview follow-ups

"Explain the Z-box." It is the interval of the match that reaches furthest right so far, so is a copy of . Inside it, the answer at is at least the mirror's answer , cut at the edge.

"Why is it linear?" Every successful comparison reads a character beyond and then moves to cover it; never moves left and stops at . Each position has at most one failed comparison. So fewer than comparisons.

"Z or KMP?" Same asymptotics, same information. Z is easier to explain for "by start position" questions and gives the scores array directly. KMP streams the text with memory and generalises to automata and Aho–Corasick. Mention that each array can be converted to the other in .

"What if the separator character appears in the input?" Use the separator-free test , or an out-of-alphabet sentinel on integer arrays.

"Can you find the LCP of two arbitrary suffixes?" Not with one Z-array; that needs a suffix array with LCP and range-minimum queries, or hashing with binary search.

"How would you match with up to one mismatch?" Z from the front (on P + T) and Z from the back (on reversed strings) at each alignment; an alignment is good if the prefix match plus the suffix match covers at least characters.

"What changes for Unicode text?" Indexing must be by code point (or grapheme cluster), and strings should be normalised first. The algorithm itself is unchanged; it needs only equality.

Mistakes interviewers watch for: mixing inclusive and half-open boxes; r - i where r - i + 1 is needed; reading s[i + z[i]] before checking the bound; using $ as a separator on arbitrary input; reporting instead of ; setting in a variant that uses as a mirror; forgetting that matches can overlap.

Quick quiz

1. Compute the Z-array of abacaba.

Answer

. Positions 2 and 6 start with a and match one character before a mismatch (or the end). At position 4 the rest of the string is aba, which matches the first three characters aba of abacaba; then the shifted copy runs out, so . Positions 1, 3 and 5 start with b or c, so they score 0.

2. During the run on aabcaabxaaz, at the box is . Which earlier value is reused, and why are no new successful comparisons possible?

Answer

The mirror , with . The room is , so the mirror's match ended inside the copy, at a mismatch that is copied too: exactly (case 2a).

3. What is the Z-array of aaaaaa, and how many character comparisons does the Z-algorithm make?

Answer

. Position 1 makes 5 successful comparisons and runs off the end, creating the box . Each later position is inside the box with mirror ; the room is smaller than , so it starts at , which already reaches the end of the string, and the loop makes no comparison at all. Total: 5 comparisons, against 15 for the slow method.

4. You search for a in the text a$a by building P + "$" + T and reporting the positions where . What goes wrong?

Answer

The concatenation is a$a$a and its Z-array is . At (text index 0) the match runs straight through the second $, because the "separator" also occurs in the text, so and the occurrence at text index 0 is missed. Only the occurrence at index 2 is reported. Fix it with a separator that cannot occur in the input, or test (which is correct with or without a separator).

5. Convert the Z-array to a prefix function without looking at the string.

Answer

From : , . From : , , , . From : already set, stop. Result , the prefix function of ababcabab.

Further reading / sources

  • Dan Gusfield, Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997, chapter 1 ("Exact matching: fundamental preprocessing and first algorithms", the Z values and Z-box) and chapter 2 (Boyer–Moore and KMP from Z values).
  • cp-algorithms: Z-function and its calculation (half-open convention, applications including distinct substrings and compression) and Prefix function.
  • Michael G. Main and Richard J. Lorentz, "An algorithm for finding all repetitions in a string", Journal of Algorithms 5(3), 1984.
  • Jean-Pierre Duval, Thierry Lecroq, Arnaud Lefebvre, "Border array on bounded alphabet", Journal of Automata, Languages and Combinatorics 10(1), 2005 (reconstructing strings from border arrays).
  • Maxime Crochemore, Christophe Hancart, Thierry Lecroq, Algorithms on Strings, Cambridge University Press, 2007, chapter 1 (borders, periods and prefix tables).

Previous lesson: KMP & the Prefix Function · Next lesson: Aho–Corasick (Multi-Pattern Matching)

Related: String Algorithms overview · String Hashing in Depth · Suffix Arrays & LCP · Strings in Depth · Sliding Window · Course home