Z-Algorithm
Z-Algorithm is a an efficient string pre-processing algorithm capable of solving many string problems with a more efficient time complexity. It is more easier to understand than some of the complex string pre-processing algorithms. It relies on building a Z -array in linear time complexity which can then be leveraged to solve some of the common string problems, most common being the pattern matching or pattern finding.
Given a string S , we calculate the z-array Z using z-algorithm.
Understanding the Z - Array:
Z [i] tells the length of largest substring starting from ith index which is also a prefix of the string S
Z [0] is of no significance
Computing the Z - array in O(n) time:
vector<int> z(string s) {
int n = s.size();
vector<int> z(n);
int x = 0,y = 0;
for(int i = 1; i < n; i++) {
z[i] = max(0, min(z[i-x], y-i+1));
while(i+z[i] < n && s[z[i]] == s[i+z[i]]) {
x = i; y = i+z[i]; z[i]++;
}
}
return z;
}
Explaining z-algorithm:
At each point, we maintain a window [x,y] which mean S [x...y] is a prefix of S . Now when we want to calculate for some i,
the value of Z [i], we do the following:
we know S [0...y-x] and S [x...y] are equal, we can use this information while calculating Z [x], Z [x+1], ....., Z [y] .
at each i we first calculate Z [i-x],
if i+Z [i-x] < y :
Z [i] = Z [i-x]
else:
we know S [0...y-i] equals S [i....y], to get Z [i], we need to compare string charater by character. Since we start comparing at positions y-i+1 and y+1, overall algorithms works in O(n) time