Z Algorithm

Z algorithm is a linear time string matching algorithm which runs in $O(n)$ complexity. It is used to find all occurrence of a pattern $P$ in a string $S$, which is common string searching problem.

Algorithm

Given a string $S$ of length $n$, the Z Algorithm produces an array $Z$ where $Z[i]$ is the length of the longest substring starting from $S[i]$ which is also a prefix of $S$, i.e. the maximum $k$ such that $S[j]\hspace{0.17em}=\hspace{0.17em}S[i\hspace{0.17em}+\hspace{0.17em}j]$ for all $0\hspace{0.17em}\le \hspace{0.17em}j\hspace{0.17em}<\hspace{0.17em}k$. Note that $Z[i]\hspace{0.17em}=\hspace{0.17em}0$ means that $S[0]\hspace{0.17em}\ne \hspace{0.17em}S[i]$. For easier terminology, let's refer to substrings which are also a prefix as prefix-substrings.

The algorithm relies on a single, crucial invariant. Iterate over the letters in the string (index $i$ from $1$ to $n-1$) and maintain an interval $[L,\hspace{0.17em}R]$ which is the interval with maximum $R$ such that $1\le \hspace{0.17em}L\hspace{0.17em}\le \hspace{0.17em}i\hspace{0.17em}\le \hspace{0.17em}R$ and $S[L...R]$ is a prefix-substring (if no such interval exists, just let $L\hspace{0.17em}=\hspace{0.17em}R\hspace{0.17em}=\hspace{0.17em}\hspace{0.17em}-\hspace{0.17em}1$). For $i\hspace{0.17em}=\hspace{0.17em}1$, simply compute $L$ and $R$ by comparing $S[\mathrm{0...}]$ to $S[\mathrm{1...}]$. $Z[1]$ is obtained during this process.

Now, suppose the correct interval $[L,\hspace{0.17em}R]$ for $i-1$ and all of the $Z$ values up to $i-1$. Compute $Z[i]$ and the new $[L,\hspace{0.17em}R]$ by the following steps:

• If $i\hspace{0.17em}>\hspace{0.17em}R$, then there does not exist a prefix-substring of $S$ that starts before $i$ and ends at or after $i$. If such a substring existed, $[L,\hspace{0.17em}R]$ would have been the interval for that substring rather than its current value. Thus "reset" and compute a new $[L,\hspace{0.17em}R]$ by comparing $S[\mathrm{0...}]$ to $S[i...]$ and get $Z[i]$ at the same time ($Z[i]\hspace{0.17em}=\hspace{0.17em}R\hspace{0.17em}-\hspace{0.17em}L\hspace{0.17em}+\hspace{0.17em}1$).
• Otherwise, $i\hspace{0.17em}\le \hspace{0.17em}R$, so the current $[L,\hspace{0.17em}R]$ extends at least to $i$. Let $k\hspace{0.17em}=\hspace{0.17em}i-L$. It is known that $Z[i]\hspace{0.17em}\ge \hspace{0.17em}min(Z[k],\hspace{0.17em}R\hspace{0.17em}-\hspace{0.17em}i\hspace{0.17em}+\hspace{0.17em}1)$ because $S[i...]$ matches $S[k...]$ for at least $R\hspace{0.17em}-\hspace{0.17em}i\hspace{0.17em}+\hspace{0.17em}1$ characters (they are in the $[L,\hspace{0.17em}R]$ interval which is known to be a prefix-substring).
• If $Z[k]\hspace{0.17em}<\hspace{0.17em}R\hspace{0.17em}-\hspace{0.17em}i\hspace{0.17em}+\hspace{0.17em}1$, then there is no longer prefix-substring starting at $S[i]$ (or else $Z[k]$ would be larger), meaning $Z[i]\hspace{0.17em}=\hspace{0.17em}Z[k]$ and $[L,\hspace{0.17em}R]$ stays the same. The latter is true because $[L,\hspace{0.17em}R]$ only changes if there is a prefix-substring starting at $S[i]$ that extends beyond $R$, which is not the case here.
• If $Z[k]\hspace{0.17em}\ge \hspace{0.17em}R\hspace{0.17em}-\hspace{0.17em}i\hspace{0.17em}+\hspace{0.17em}1$, then it is possible for $S[i...]$ to match $S[\mathrm{0...}]$ for more than $R\hspace{0.17em}-\hspace{0.17em}i\hspace{0.17em}+\hspace{0.17em}1$ characters (i.e. past position $R$). Thus, there's a need to update $[L,\hspace{0.17em}R]$ by setting $L\hspace{0.17em}=\hspace{0.17em}i$ and matching from $S[R\hspace{0.17em}+\hspace{0.17em}1]$forward to obtain the new $R$. Again, $Z[i]$ is obtained during this process.

The process computes all of the $Z$ values in a single pass over the string, so we're done. Correctness is inherent in the algorithm and is pretty intuitively clear.

Time Complexity

The algorithm runs in $O(n)$ time. Characters are never compared at positions less than $R$, and every time a match is found, $R$ is increased by one, so there are at most $n$ comparisons.

Implementation

Note that the optimization $L\hspace{0.17em}=\hspace{0.17em}R\hspace{0.17em}=\hspace{0.17em}i$ is used when $S[0]\hspace{0.17em}\ne \hspace{0.17em}S[i]$ (it doesn't affect the algorithm since at the next iteration $i\hspace{0.17em}>\hspace{0.17em}R$ regardless).

int L = 0, R = 0;
for (int i = 1; i < n; i++) 
{
    if (i > R) 
    {
        L = R = i;
        while (R < n && s[R-L] == s[R]) 
        {
            R++;
        }
        z[i] = R-L; 
        R--;
    } 
    else 
    {
        int k = i-L;
        if (z[k] < R-i+1) 
        {
            z[i] = z[k];
        } 
        else 
        {
            L = i;
            while (R < n && s[R-L] == s[R]) 
            {
                R++;
            }
            z[i] = R-L; 
            R--;
        }
    }
}

Applications

One application of the Z Algorithm is for the standard string matching problem of finding matches for a pattern $T$of length $m$ in a string $S$ of length $n$. This can be done in $O(n\hspace{0.17em}+\hspace{0.17em}m)$ time by using the Z Algorithm on the string $T\mathrm{\Phi }S$ (that is, concatenating $T$, $\Phi$, and $S$) where $\Phi$ is a character that matches nothing. The indices $i$ with $Z[i]\hspace{0.17em}=\hspace{0.17em}m$ correspond to matches of $T$ in $S$.