Given a string s of length n. The Z-array for this string is an array of length n where the i-th element is the size of longest string starting from the position that is also a substring starting from s[0]. The first element of Z-array, is set to 0.
Here are some example values of the Z-array computed for different strings:
* "aaaaa" - [0,4,3,2,1]
* "aaabaab" - [0,2,1,0,2,1,0]
* "abacaba" - [0,0,1,0,3,0,1]
A trivial algorithm implementation,
```
vector<int> z_function_trivial(string s) {
int n = (int) s.length();
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;
}
```
To obtain an efficient algorithm we will still compute the values of z[i] in turn from i=1 to n-1, but when computing a new value, we'll try to make the best use of the previously computed values.
Let's call them <b>segment matches</b> for those substrings that coincide with a prefix of s. For example, 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).
To do this, we will keep the [l,r] indices of the rightmost segment match. That is, among all detected segments we will keep the one that ends rightmost. In a way, the index can be seen as the "boundary" to which our string has been scanned by the algorithm; everything beyond that point is not yet known.
Then, if the current index (for which we have to compute the next value of the Z-function) is , we have one of two options:
* i>r: the current position is outside of what we have already processed. We will then compute z[i] with the trivial algorithm (that is, just comparing values one by one). Note that in the end, if z[i]>0, we'll have to update the indices of the rightmost segment, because it's guaranteed that the new r=i+z[i]-1 is better than the previous r.
* i<=r: the current position is inside the current segment match [l,r]. Then we can use the already calculated Z-values to "initialize" the value of z[i] to something (it sure is better than "starting from zero"), maybe even some big number. For this, we observe that the substrings s[l...r] and s[0...r-l] match. This means that as an initial approximation for z[i] we can take the value already computed for the corresponding segment s[0...r-l], and that is z[i-l]. However, the value z[i-l] could be too large: when applied to position i it could exceed the index r. This is not allowed because we know nothing about the characters to the right of r: they may differ from those required. Here is an example of a similar scenario: s="aaaabaa". When we get to the last position (i=6), the current match segment will be [5,6]. Position 6 will then match position 6-5=1, for which the value of the Z-function is z[1]=3. Obviously, we cannot initialize z[6] to 3, it would be completely incorrect. The maximum value we could initialize it to is 1 -- because it's the largest value that doesn't bring us beyond the index r of the match segment [l,r]. Thus, as an initial approximation for z[i] we can safely take: z<sub>0</sub>[i]=min(r-i+1,z[i=l]). After having z[i] initialized to z<sub>0</sub>[i], we try to increment z[i] by running the trivial algorithm -- because in general, after the border r, we cannot know if the segment will continue to match or not. Thus, the whole algorithm is split in two cases, which differ only in the initial value of z[i]: in the first case it's assumed to be zero, in the second case it is determined by the previously computed values (using the above formula). After that, both branches of this algorithm can be reduced to the implementation of the trivial algorithm, which starts immediately after we specify the initial value.
The algorithm turns out to be very simple. Despite the fact that on each iteration the trivial algorithm is run, we have made significant progress, having an algorithm that runs in linear time. It can be prove that the running time is linear.
```
vector<int> z_function(string s) {
int n = (int) s.length();
vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; ++i) {
if (i <= r)
z[i] = min (r - i + 1, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
++z[i];
if (i + z[i] - 1 > r)
l = i, r = i + z[i] - 1;
}
return z;
}
```