String Algorithms

Z-Algorithm

The Z-algorithm produces the ”-array” in time, where each element of the array indicates the length of the longest substring of that begins at position and is a prefix of .

For example, here are the values of the Z-function computed for different strings:

  • “aaaaa” - 
  • “aaabaab” - 
  • “abacaba” -

Many string processing problems can be efficiently solved using the Z-array.

vector z_function(string s) { 
	int n = s.size(); 
	vector 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; 
}

Problems that you can solve with the Z-Algorithm

Search the substring: find all occurrences of the pattern  inside the text . Solution: Construct a new string , we use as a separator. Then, go over the z-array and count the number of indices where