## § Z algorithm (TODO)

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 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.