notebook/code/ZFunction.cpp

const int maxn = 1000;
/*
	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][i+j] for all 0 <= j<k. Note that Z[i]=0 means that S[0]!=S[i].
	O(n)
*/
string s;
int n;
int z[maxn];
void z_function() {
	z[0] = 1;
	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--;
    		}
  		}
	}
}
void test() {
	memset(z, 0, sizeof(z));
	s = "abcabcabcabc";
	n = s.length();
	z_function();
	for (int i = 0; i < n; i++)
		cout << i << " " << s[i] << " " << z[i] << endl;
}