Theoretical Introduction to the Z Function:

In string processing and pattern matching, the Z function is a powerful tool used to efficiently find all occurrences of a pattern within a given string. Named after its creator Igor Zverovich, this function associates each position i in a string S with the length of the longest substring starting from i that matches the prefix of S.

The Z function is particularly useful in scenarios where we need to efficiently find occurrences of a pattern within a string, as it preprocesses the string to provide valuable information about substring matches. This function allows for faster substring searches and can be applied in various algorithms such as string searching, compression, and substring analysis.

Trivial Algorithm for Computation

We just iterate through every position i and update  z[i]  for each one of them, starting from z[i] = 0 and incrementing it as long as we don't find a mismatch (and as long as we don't reach the end of the line).

Of course, this is not an efficient implementation.

vector<int> z_function_trivial(string s) { 
	int n = s.size(); 
	vector<int> z(n); 
	for (int i = 1; i < n; i++) { 
		while (i + z[i] < n && s[z[i]] == s[i + z[i]]) { 
		z[i]++; 
		} 
	} 
	return z; 
  }

Efficient Algorithm to compute the Z-Function

To compute the z[i] we need to use the precompute the previous values of z[i]
The value of the desired Z-function z[i] is the length of the segment match starting at position i and that ends at position i + z[i] - 1

[l,r) : indices of the rightmost segment match among all the detected segments its is the one which is the rightmost.
r is the boundary upto which the string is scanned.

This means [ l ... r-1 ) has been scanned already

Case 1 : i >= r

Then compute using the trivial algorithm :

while (i + z[i] < n && s[z[i]] == s[i + z[i]]) { 
		z[i]++; 
		} 

Case 2 : i < r

Use the initialise with the already calculated z[i] values

But How ????

Observation :
For this, we observe that the substrings s[l...r) and s[0...r-l) match.

As an initial approximation we can take z[i] as z[i-l] as i can be mapped as i-l

But it may be too far-fetched so we take a safe limit of r - i

so z[i] = min( r - , z[i-l])

C++ Implementation

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

References :
Z-function - Algorithms for Competitive Programming (cp-algorithms.com)

Related Question :
3031. Minimum Time to Revert Word to Initial State II