// s[0, ..., n-1], z[0] = 0
// z[i] is the length of the longest substring starting from s[i] which is also a prefix of s

// O(n), R increases...

int L = , R = ;

for (int i = ; 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+) z[i] = z[k];

    else {

      L = i;

      while (R < n && s[R-L] == s[R]) R++;

      z[i] = R-L; R--;

    }

  }

}