Z-Function (Z-Algorithm)

The Z-function answers a different prefix question at every starting position. Z[i] is the longest length for which the substring beginning at i equals a prefix of the whole string. The value describes a match that starts at i, while π[i] describes a border that ends at i. Both arrays can be constructed in linear time, but their meanings and invariants should not be mixed.

This lesson uses Z[0]=0 by convention and keeps a rightmost verified prefix-matching interval [L,R). Reusing matches inside that interval prevents repeated comparisons. Applications include exact matching, locating repeated prefixes, and detecting periods.

Prerequisites: Introduction to String Algorithms; half-open intervals and amortized analysis. Prefix Function is helpful for comparison but not required.

Build the idea

1. 1. Define the entries with a concrete array

   For s=aabcaabxaaaz, Z is 0 1 0 0 3 1 0 0 2 2 1 0. At i=4, the substring begins aabx, while the full prefix begins aabc. The first three characters agree and the next differs, so Z[4]=3. At i=8, substring aaaz agrees for two characters before a differs from b.

   Mathematically the suffix starting at 0 matches the whole string, but this implementation deliberately stores Z[0]=0. Some references choose N instead. Either convention is valid when documented; applications involving position 0 must account for it. Empty input gives an empty array.

2. 2. Keep a verified matching box

   Maintain [L,R) such that s[L..R)=s[0..R−L), choosing a processed box whose right endpoint is farthest right. For a new position i outside that box, start its match length at zero and compare directly. For i inside, put k=i−L. The already verified box means the suffix of that box starting at i behaves like the prefix starting at k, at least until R.

   Therefore start with Z[i]=min(R−i,Z[k]). The minimum is essential: Z[k] may describe characters beyond what the current box has proved. Reuse only established equalities; do not assume the region after R also matches.

3. 3. Separate the two inside-box cases

   If Z[k]<R−i, its first mismatching character lies strictly inside the verified box. The same mismatch occurs at i, so the reused length is already final. If Z[k]≥R−i, all characters up to R are known equal, but the match might extend farther. Begin comparisons at that boundary, increasing Z[i] while characters agree.

   In the sample, i=4 builds box [4,7), matching aab. At i=5, k=1, Z[1]=1, and R−i=2. The inside-box value 1 is enough: the next mismatch is already implied. At i=8, a new direct match builds [8,10). At i=9, initialize with min(1,Z[1])=1, then compare beyond R and extend to 2, updating the box to [9,11).

4. 4. Extend, then update the rightmost box

   The direct comparison uses positions Z[i] and i+Z[i]. Test i+Z[i]<N before reading them. If the newly found endpoint i+Z[i] exceeds R, assign L=i and R=i+Z[i]. Otherwise keep the farther-reaching old box. Starting from L=R=0 gives an empty box, so the first real positions are handled naturally.

   Why is the construction correct? Outside the box, it is ordinary direct comparison. Inside, the box equality justifies the copied starting segment. The extension loop checks every still-unproved character in order and stops at the first mismatch or end of string. Thus the result is neither too short nor too long.

5. 5. Account for all comparisons

   Initialization and box updates cost O(1) per position. Successful comparisons that extend a box advance its right endpoint into previously unverified positions, so there are at most O(N) of them overall. When the copied value ends strictly inside a box, the next comparison immediately fails. There is at most one final failed comparison per position. These observations give O(N) time despite the nested extension loop.

   For pattern matching, form P + separator + T and inspect text positions whose Z value is at least M. The separator must not equal any alphabet symbol. If arbitrary byte values are allowed, encode bytes as integers 1..256 and use 0 as separator instead of guessing that # is absent. Handle an empty pattern separately as all boundaries. Another application: p>0 is a period exactly when Z[p]≥N−p; a whole repeating unit additionally needs N divisible by p. This lesson’s program outputs Z itself, keeping the construction distinct from those applications.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>zFunction(const string&s){
    int n=static_cast<int>(s.size());
    vector<int>z(n,0); // Convention: z[0]=0, including for a one-character string.
    int left=0,right=0; // Rightmost known matching box [left,right).
    for(int i=1;i<n;++i){
        if(i<right){
            z[i]=min(right-i,z[i-left]); // Copy only inside the verified box.
        }
        // Extend beyond the known prefix match, checking the boundary first.
        while(i+z[i]<n&&s[z[i]]==s[i+z[i]]){
            ++z[i];
        }
        if(i+z[i]>right){ // Keep the box with the farthest right endpoint.
            left=i;
            right=i+z[i];
        }
    }
    return z;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    getline(cin,s); // Read a full line; spaces compare like other bytes.
    vector<int>z=zFunction(s);
    for(int i=0;i<static_cast<int>(z.size());++i){
        cout<<z[i]<<(i+1==static_cast<int>(z.size())?'\n':' ');
    }
    if(z.empty()){
        cout<<'\n'; // Empty input has no entries.
    }
}

Complexity analysis

O(N) time: successful extension beyond the rightmost verified boundary advances it at most N times; other work is constant per position, including at most one final failed comparison. O(N) space for the returned Z array and input, with O(1) state beyond them.

Example input and output

One full line s, possibly empty and containing spaces, with length at most 1,000,000. Print Z values for indices 0..N−1. Use Z[0]=0. Empty s produces a blank line.

Input

aabcaabxaaaz

Output

0 1 0 0 3 1 0 0 2 2 1 0

Position 4 begins aabx and matches the whole prefix for three characters. Positions 8 and 9 both begin aa followed by a different third character, so each has value 2.

Practical applications

Exact matching, locating copies of a prefix, checking periods, and comparing a prefix to all suffixes in linear time. KMP is convenient for streaming text; Z is convenient when all prefix-match lengths at starting positions are useful together.

Check your understanding

Why initialize an inside-box Z value with min(R−i,Z[i−L])?

Put it into practice

Print every period p with 1≤p<N of a nonempty string, allowing the final repetition to be partial.