String Algorithms

Z-Algorithm

The Z-algorithm produces the ”$z$-array” in $O(n)$ time, where each element $z[i]$ of the array indicates the length of the longest substring of $s$ that begins at position $i$ and is a prefix of $s$.

Resources

• https://cp-algorithms.com/string/z-function.html

For example, here are the values of the Z-function 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]$

Why is it 0 for the first index?

Z[0] is 0 here by convention. From cp-algorithms website:

• “The first element of Z-function,   $z[0]$ , is generally not well defined. In this article we will assume it is zero (although it doesn’t change anything in the algorithm implementation).”

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 $p$ inside the text $t$. Solution: Construct a new string $s=p+\diamond +t$, we use $\diamond$ as a separator. Then, go over the z-array and count the number of indices where $z[i]==s.length()$

Related

• Suffix Array