Z-function

The Z-function computes, for every position of a string, how many letters from there repeat the start of the string, in $O(n)$ time. With it you can find every occurrence of a pattern in a text, or the periods of a string, even when the text has 10^6 letters and the plain letter-by-letter search is too slow.

Explanation

Where does the pattern ab occur in the text aabab? Glue the pattern, a # and the text into one string, ab#aabab, 8 letters at positions 0 to 7. Under every position, write how many letters starting there repeat the start of the string. Position 4 starts with ab, like the string itself, and then a meets #, so position 4 gets 2. Position 0 is the whole string; by convention it gets 0.

Fig. 1. The number under each position counts the letters from there that repeat the start of the string.

Look at the two 2s. They stand at positions 4 and 6, where ab starts in the text: at positions 1 and 3 of aabab. This row of numbers is the Z-array of the string. The # stops every count at the end of the pattern, so no number is larger than 2.

Counts on ab#aabab stop after a letter or two. On aabaabaaabb, 11 letters at positions 0 to 10, one of them runs much longer. The numbers at positions 0 to 3 are 0, 1, 0 and 5: from position 3, the 5 letters aabaa repeat the start of the string. Call positions 3 to 7 the window: the stretch found so far that repeats the start of the string and reaches furthest right.

Fig. 2. Positions 3–7 repeat positions 0–4.

Counting from scratch at positions 4 to 7 takes 10 comparisons, and 6 of them look again at letters 4 to 7, which the match from position 3 already compared. On a string of 10^6 letters a, position 1 matches 10^6 - 1 letters, position 2 one fewer, and so on: about 5 \cdot 10^{11} comparisons, far beyond the rule of thumb of about 10^8 simple steps per second.

Every position in the window corresponds to the position 3 places to its left, at the start of the string. That position is further left, so its number is already computed by the time we get there, and we can copy it. Take position 6, the one that corresponds to the long match at position 3: its number should be 5 as well.

The number 5 would say that positions 6 to 10 repeat positions 0 to 4. Positions 6 and 7 do, but position 8 holds a and position 2 holds b, so the true number at position 6 is 2. The match from position 3 ends at position 7, and positions 8 to 10 were never compared with anything.

Fig. 3. The claim of 5 runs past the window's end mark.

We can trust the copied number only up to the window's end. From position 6 that is 2 letters, positions 6 and 7, so we start from the smaller of 5 and 2. Past the end nothing is known, so we compare letter by letter; here the first comparison already fails, and the number at position 6 stays 2. When a match does run past the window's end, the stretch it covers becomes the new window, because it reaches further right.

This method is the Z-function. It keeps the window that reaches furthest right, starts each position inside it from the copied number cut at the window's end (a position outside the window starts from 0), and compares letters only past that end.

Let's run the whole method on aabaabaaabb, from position 1 to 10.

The number at position 0 is 0. The window is empty: l = r = 0.

Position 1 is outside the window, so it starts from 0. Positions 0 and 1 both hold a, so the number at position 1 grows to 1.

Position 1 holds a and position 2 holds b: they differ, so the number at position 1 stays 1.

The match reaches past the old window's end, so the window moves: l = 1, r = 2. It covers position 1, the same letters as position 0. The bracket under the numbers marks the window, the bracket under the string marks the start it repeats.

Position 2 is outside the window, so it starts from 0. Position 0 holds a and position 2 holds b: they differ, so the number at position 2 stays 0.

Position 3 is outside the window, so it starts from 0. Positions 0 and 3 both hold a, so the number at position 3 grows to 1.

Positions 1 and 4 both hold a, so the number at position 3 grows to 2.

Positions 2 and 5 both hold b, so the number at position 3 grows to 3.

Positions 3 and 6 both hold a, so the number at position 3 grows to 4.

Positions 4 and 7 both hold a, so the number at position 3 grows to 5.

Position 5 holds b and position 8 holds a: they differ, so the number at position 3 stays 5.

The match reaches past the old window's end, so the window moves: l = 3, r = 8. It covers positions 3 to 7, the same letters as positions 0 to 4.

Position 4 is inside the window and copies the number at position 4 − 3 = 1 (outlined): 1. That match ends inside the window, so the comparison of positions 1 and 5 (a and b) fails at once, as expected, which is why the pair is grey.

Position 5 is inside the window and copies the number at position 5 − 3 = 2: 0. That match ends inside the window, so the comparison of positions 0 and 5 (a and b) fails at once.

Position 6 is inside the window, so it copies the number at position 6 − 3 = 3, which is 5. Only 2 letters are left up to the window's end, so it starts from 2.

Position 2 holds b and position 8 holds a: they differ, so the number at position 6 stays 2.

Position 7 is inside the window, so it copies the number at position 7 − 3 = 4: 1. That reaches exactly the window's end.

Positions 1 and 8 both hold a, so the number at position 7 grows to 2.

Positions 2 and 9 both hold b, so the number at position 7 grows to 3.

Position 3 holds a and position 10 holds b: they differ, so the number at position 7 stays 3.

The match reaches past the old window's end, so the window moves: l = 7, r = 10. It covers positions 7 to 9, the same letters as positions 0 to 2.

Position 8 is inside the window and copies the number at position 8 − 7 = 1: 1. That match ends inside the window, so the comparison of positions 1 and 9 (a and b) fails at once.

Position 9 is inside the window and copies the number at position 9 − 7 = 2: 0. That match ends inside the window, so the comparison of positions 0 and 9 (a and b) fails at once.

Position 10 is outside the window, so it starts from 0. Position 0 holds a and position 10 holds b: they differ, so the number at position 10 stays 0.

The run is over: the Z-array is 0 1 0 5 1 0 2 3 1 0 0.

1/25

Fig. 4. Step through the Z-function with the buttons or the arrow keys. Green pairs are equal, red pairs differ.

The run fills in the whole Z-array: 0 1 0 5 1 0 2 3 1 0 0. It makes 18 comparisons: 8 that find equal letters and 10 unequal ones, one per position. On 10^6 letters a it makes fewer than 10^6 comparisons instead of about 5 \cdot 10^{11}.

Searching for a pattern

To find a pattern of length $m$ in a text of length $k$, glue the pattern, a separator and the text into one string of length m + 1 + k and compute its Z-array. Every position whose number equals $m$ is an occurrence, and it starts at text position i - m - 1 when the glued position is $i$ (in ab#aabab, position 4 gives 4 - 2 - 1 = 1). The separator must be a letter that appears in neither string. Then no match can run through it, so no number is larger than $m$, and a number equal to $m$ means the whole pattern. The search takes O(m + k) time and memory.

Borders and periods

Compare a string of length $n$ with itself shifted right by $p$, for $p$ from 1 to n - 1. If $p$ plus the number at position $p$ equals $n$, every letter equals the letter $p$ places before it: the string repeats with period $p$. In abaabaab (Z-array 0 0 1 5 0 1 2 0) this happens at p = 3, since 3 + 5 = 8, and at p = 6, since 6 + 2 = 8. So 3 is the shortest period.

Fig. 5. Shifting by 3 leaves 5 equal letters, so 3 + 5 = 8, the length of the string.

The overlapping part is both the start and the end of the string. Such a piece, shorter than the whole string, is a border. Each period $p$ gives a border of length n - p, so the shortest period gives the longest border: abaab, of length 5. The period 6 gives the border ab. To find the shortest period, check $p$ from 1 upward and take the first one that fits, in $O(n)$ once the Z-array is known. If none fits, the shortest period is $n$ and the string has no border.

A related question asks whether the string is a shorter string t written several times. The shortest such t has the length of the smallest period $p$ that also divides $n$, or $n$ if there is none. For abaabaab the periods 3 and 6 don't divide 8, so t is the whole string.

Implementation

Let's keep the numbers in a vector z of size n: z[i] is the number of letters from position i of the string s that repeat the start of s. A start of a string is also called its prefix. We set z[0] = 0.

The window is the stretch of positions from l to r - 1, written [l, r): r is one past its last letter, so r - i is the number of window letters from i on. It repeats the prefix of length r - l, and it starts empty, with l = r = 0. Position i in the window corresponds to position i - l. In the example, the window at positions 3 to 7 is l = 3, r = 8, and at i = 6 step 1 below gives min(8 - 6, z[3]) = min(2, 5) = 2, the cut from Fig. 3. Other sources call the window the Z-box.

For each position i from 1 to n - 1:

1. Copy from the window: if i < r, set z[i] = min(r - i, z[i - l]).

2. Compare past the window: while i + z[i] < n and s[z[i]] == s[i + z[i]], increase z[i].

3. Move the window: if i + z[i] > r, set l = i and r = i + z[i].

The program reads one line, the string, and prints its Z-array. For the main example the input is:

aabaabaaabb

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> z_function(const string& s) {
    int n = s.size();
    // start with an empty window
    vector<int> z(n, 0);
    int l = 0, r = 0;   // the window [l, r) repeats the prefix of length r - l
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);                  // copy from the window
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;  // compare past the window
        if (i + z[i] > r) { l = i; r = i + z[i]; }              // move the window
    }
    return z;
}

int main() {
    string s;
    cin >> s;
    vector<int> z = z_function(s);
    int n = z.size();
    for (int i = 0; i < n; i++) cout << z[i] << (i + 1 < n ? ' ' : '\n');
}

The Z-function runs in $O(n)$ time (the proof is below) and uses $O(n)$ memory for s and z. A string of 10^6 letters needs fewer than 2 \cdot 10^6 comparisons.

Finding all occurrences

The program reads the text t, then the pattern p, and prints how many times p occurs in t and where each occurrence starts, counting from 0. The function z_function is the same as above.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> z_function(const string& s) {
    int n = s.size();
    // start with an empty window
    vector<int> z(n, 0);
    int l = 0, r = 0;   // the window [l, r) repeats the prefix of length r - l
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);                  // copy from the window
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;  // compare past the window
        if (i + z[i] > r) { l = i; r = i + z[i]; }              // move the window
    }
    return z;
}

int main() {
    string t, p;
    cin >> t >> p;
    int m = p.size();

    string s = p + '#' + t;   // '#' must appear in neither p nor t
    vector<int> z = z_function(s);

    vector<int> found;
    for (int i = m + 1; i < (int)s.size(); i++)
        if (z[i] == m) found.push_back(i - m - 1);   // position in t, from 0

    cout << found.size() << '\n';
    for (int k = 0; k < (int)found.size(); k++)
        cout << found[k] << (k + 1 < (int)found.size() ? ' ' : '\n');
}

For the text aabab and the pattern ab it prints 2 occurrences, at positions 1 and 3. When a problem numbers positions from 1, print i - m instead. When the values are numbers rather than letters, keep them in a vector<int>, glue them the same way with -1 as the separator (or any value that can't occur), and write z_function for vector<int>.

Correctness proof

The comparisons in step 2 are made on real letters, so z_i can only be wrong if the start value from step 1 is too large. The algorithm keeps one invariant: the window [l, r) repeats the prefix of length r - l, that is, s_{l} \dots s_{r-1} = s_0 \dots s_{r-l-1}. Step 3 sets the window to a match that was just compared, so the invariant holds after it.

Take a position $i$ inside the window. By the invariant, the letters from $i$ to r - 1 equal the letters from i - l to r - l - 1, and z_{i-l} is already known because i - l < i. There are two cases, shown in Fig. 6.

Fig. 6. Top: the match and the unequal letter stay inside the brackets. Bottom: the red bracket was never compared.

If z_{i-l} < r - i, the match from i - l ends inside the prefix of length r - l, and so does the unequal letter right after it. Both reappear inside the window shifted by $l$, so the match from $i$ has exactly the same length, and the one comparison in step 2 fails at once. If z_{i-l} \ge r - i, the invariant only proves that the r - i letters up to the window's end match, so starting from r - i is safe, and step 2 compares everything past $r$. In both cases the start value \min(r - i, z_{i-l}) is never larger than the true z_i, so the result is exact.

The running time follows the two pointers argument. An equal comparison in step 2 looks at letter i + z_i \ge r, and once z_i grows past it, step 3 moves $r$ to at least one past that letter. So every equal comparison moves the window's end at least one step right. The end never moves left and never passes $n$, so there are fewer than $n$ equal comparisons. Each position adds at most one unequal comparison, so the total is below $2n$.

Common mistakes

• Copying z[i - l] without cutting it at the window's end. The wrong value creates a wrong window, which spoils later positions too: on aabaabaaabb, positions 9 and 10 as well as 6. Use min(r - i, z[i - l]).

• Comparing only when i is outside the window (if (i < r) … else while …). A copy that reaches exactly the window's end then never grows. Run the while loop after every copy.

• Searching without a separator and testing z[i] == m. For the pattern aa in the text aaa, the glued aaaaa has the Z-array 0 4 3 2 1, so only position 1 is reported and position 0 is missed. Glue p + '#' + t with a letter that is in neither string; if # can appear in the input, pick another one or switch to numbers with -1.

• Taking the shortest period as the answer to "the shortest t such that s is t repeated". Also require n % p == 0.

Similar algorithms

The prefix function solves the same problems in $O(n)$. It stores, for each end position, the longest border of the string up to there, while the Z-function stores, for each start position, the match with the prefix. The prefix function (in the KMP search) can read the text one letter at a time without keeping it, while the Z-function needs the glued string in memory. When a problem asks for the longest border of every prefix, the prefix function computes exactly that array.

String hashing compares any two substrings in $O(1)$ after $O(n)$ preparation, with a small chance of error. Use it when the pieces to compare aren't tied to the start of one string, such as a common substring of two strings.

Manacher's algorithm uses the same window idea, copying from the reflected position and comparing only past the window's end, to find the longest palindrome around every centre.

Practice