§ Z algorithm

• The Z algorithm, for a given string $s$, computes a function $Z: [len(s)] \rightarrow [len(s)]$.
• $Z[i]$ is the length of the longest common prefix between $S$ and $S[i:]$.
• So, $S[0] = S[i]$, $S[1] = S[i+1]$, $S[2] = S[i+2]$, and so on till $S[Z[i]] = S[i + Z[i]]$, and then $S[Z[i]+1] \neq S[i + Z[i] + 1]$.

• If we can compute the Z function for a string, we can then check if pattern Pis a substring of text T by constructing the string P#T$. Then, if we have an index such that Z[i] = len(P), we know that at that index, we have the string P as a substring.

• Note that the Z-algorithm computes the Z function in linear time .

• The key idea of the Z algorithm is to see that if we are at an index i, but we have an index l < isuch that i < l + z[l], then we have that s[0:z[l]] = s[l:l+z[l]]. Thus, we are "in the shade" of the l.

• In this situation, we can reuse z[i-l] as a seed for z[i]. There are two cases: i + z[i-l] > l + z[l] and the converse.
• If i + z[i-l] < l + z[l], then we are still "in the shade" of l, so we can safely set z[i] = z[i-l].
• If not, we set z[i] = l + z[l], since we know that we match at least this much of the beginning of the string.

§ Specification

vector<int> calcz(std::string s) {
 const int n = s.size();
 vector<int> z(n);
 z[0] = 0;
 for(int i = 1; i < s.size(); ++i) {
   z[i] = 0;
   while(i + z[i] < n && s[i+z[i]] == s[z[i]]) {
     z[i]++;
   }
 }

 return z;
}

§ Implementation

vector<int> myz(std::string s) {
    const int n = s.size();
    vector<int> z(n);
    for(int i = 0; i < n; ++i) { z[i] = 0; }

    // shade that was last computed.
    int l = 0;
    for(int i = 1; i < n; ++i) {
        // shade: (l + z[l]) - i
        // guess from start: z[i-l]
        z[i] = max(0, min(l + z[l] - i, z[i-l]));

        // compare with initial portion of string.
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) { z[i]++; }

        // we exceed the current shade. Begin ruling.
        if (i + z[i] >= l + z[l]) { l = i; }
    }

    return z;
}

• Reference: Algorithms on strings, trees, and sequences.