# 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$.

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]$

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

### 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+⋄+t$, we use $⋄$ as a separator. Then, go over the z-array and count the number of indices where $z[i]==s.length()$