Blocks of string (Editorial)

Сompute the $z$-function for the string $S$ and store its values in the array $v$. Print the $z$-function values for all positions i~(0 \le i < n).

Algorithm realization

The input string $s$ contains no more than 10^6 characters. The $z$-function of the string $s$ is stored in the vector $v$.

vector<int> v;
string s;

The z function computes and returns the $z$-function for the string $s$.

vector<int> z(string s)
{
  int i, l, r, len = s.size();
  vector<int> z(len, 0);
  l = 0, r = 0;
  for (i = 1; i < len; i++)
  {
    if (i <= r) z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < len && s[z[i]] == s[i + z[i]]) z[i]++;
    if (i + z[i] - 1 > r)
    { 
      l = i;
      r = i + z[i] - 1;
    }
  }
  return z;
}

The main part of the program. Read the input string $s$.

getline(cin,s);

Compute the $z$-function.

v = z(s);

Print the $z$-function values for all positions of the input string.

for (i = 0; i < v.size(); i++) 
  printf("%d ", v[i]);
printf("\n");