§ Z algorithm (TODO)

The Z algorithm, for a given string ss, computes a function Z:[len(s)][len(s)]Z: [len(s)] \rightarrow [len(s)]. Z[i]Z[i] is the length of the longest common prefix between SS and S[i:]S[i:]. So, S[0]=S[i]S[0] = S[i], S[1]=S[i+1]S[1] = S[i+1], S[2]=S[i+2]S[2] = S[i+2], and so on till S[Z[i]]=S[i+Z[i]]S[Z[i]] = S[i + Z[i]], and then S[Z[i]+1]S[i+Z[i]+1]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 P is 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.
const int N = 1000;
int z[N];
char s[N] = "hello, world";
int n;

// write the z array into the array z for the string s
void mkz(const char *s, int *z) {
    const int N = strlen(s);
    int curi = 0;
    while(s[curi]) {
        int matchlen = 0; 
        while(curi + matchlen < N) {
            if (s[curi + matchlen] == s[matchlen]) { matchlen++; }
            else { break; }
        }
        z[curi] = matchlen;

        for(int i = 0; i < matchlen && i < curi; ++i) { z[curi + i] = z[i]; }
        curi += matchlen;
    }
}

int main() {
in
}
  • Reference: Algorithms on strings, trees, and sequences.