ZAlgorithm.cpp

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>

using namespace std;

int main() {
  string s;
  cin >> s;

  int n = s.length();
  int z[n];
  z[0] = 0;

  // L and R are bounding box inclusives
  int L = 0, R = 0;
 
  // start conputing the prefix match from idx
  auto z_start = [&](int idx) {
    L = R = idx;
    int j = 0;
    while((L + j < n) && (s[j] == s[L + j])) j++;
    R = L + j - 1;
    z[idx] = j;
  };


  for (int i = 1; i < n; i++) {
    if (i > R) {
      z_start(i);
    } else {
      int k = i - L;
      int pre_l = z[k] + i;
      if (pre_l > R) {
	z_start(i);
      } else {
	z[i] = z[k];
      }
    }
  }

  for (int i = 0; i < n; i++) {
    printf("%d ", z[i]);
  }
  puts("");

  return 0;
}