§ Z algorithm

§ 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;
}