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] = S[i + j]$$ for all $$0 \le j \lt k$$. Note that $$Z[i] = 0$$ means that $$S[0] \ne 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, R]$$ which is the interval with maximum $$R$$ such that $$1\le L \le i \le R$$ and $$S[L...R]$$ is a prefix-substring (if no such interval exists, just let $$L = R = - 1$$). For $$i = 1$$, simply compute $$L$$ and $$R$$ by comparing $$S[0...]$$ to $$S[1...]$$. $$Z[1]$$ is obtained during this process.
Now, suppose the correct interval $$[L, R]$$ for $$i-1$$ and all of the $$Z$$ values up to $$i-1$$. Compute $$Z[i]$$ and the new $$[L, R]$$ by the following steps:
-
If $$i > 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, R]$$ would have been the interval for that substring rather than its current value. Thus "reset" and compute a new $$[L, R]$$ by comparing $$S[0...]$$ to $$S[i...]$$ and get $$Z[i]$$ at the same time ($$Z[i] = R - L + 1$$).
-
Otherwise, $$i \le R$$, so the current $$[L, R]$$ extends at least to $$i$$. Let $$k = i-L$$. It is known that $$Z[i] \ge min(Z[k], R - i + 1)$$ because $$S[i...]$$ matches $$S[k...]$$ for at least $$R - i + 1$$ characters (they are in the $$[L, R]$$ interval which is known to be a prefix-substring).
-
If $$Z[k] < R - i + 1$$, then there is no longer prefix-substring starting at $$S[i]$$ (or else $$Z[k]$$ would be larger), meaning $$Z[i] = Z[k]$$ and $$[L, R]$$ stays the same. The latter is true because $$[L, 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] \ge R - i + 1$$, then it is possible for $$S[i...]$$ to match $$S[0...]$$ for more than $$R - i + 1$$ characters (i.e. past position $$R$$). Thus, there's a need to update $$[L, R]$$ by setting $$L = i$$ and matching from $$S[R + 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 = R = i$$ is used when $$S[0] \ne S[i]$$ (it doesn't affect the algorithm since at the next iteration $$i > 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 + m)$$ time by using the Z Algorithm on the string $$T\; \Phi\; S$$ (that is, concatenating $$T$$, $$ \Phi $$, and $$S$$) where $$ \Phi $$ is a character that matches nothing. The indices $$i$$ with $$Z[i] = m$$ correspond to matches of $$T$$ in $$S$$.
