Разбор

Построим для строки $S z$ -функцию и сохраним ее значения в массиве $v$ . Выведем значения $z$ -функции для всех позиций $i (0 \leq i < n)$ .

Реализация алгоритма

Входная строка $s$ содержит не более $1 0^{6}$ символов. $z$ -функцию строки $s$ сохраняем в векторе $v$ .

vector<int> v;
string s;

Функция z строит и возвращает $z$ -функцию для строки $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;
}

Основная часть программы. Читаем входную строку $s$ .

getline(cin,s);

Вычисляем $z$ -функцию.

v = z(s);

Выводим значения $z$ -функции для всех позиций входной строки.

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