Z-array

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i=a;i<(b);++i)
#define all(x) begin(x),end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;

const int N = 1e6;
int Z[N];

void zar(const string& s) {
  int a = 0, b = 0;
  rep(i,1,sz(s)) {
    if (i + Z[i - a] < b) {
      Z[i] = Z[i - a];
      continue;
    }
    int j = i < b ? b - i : 0;
    for (; j < sz(s); ++j) {
      if (s[i+j] != s[j]) break;
    }
    if (i+j > b) {
      a = i;
      b = i+j;
    }
    Z[i] = j;
  }
  Z[0] = sz(s);
}

int main() {
  string a;
  cin >> a;
  zar(a);
  rep(i,0,sz(a)) cout << Z[i] << ' ';
  cout << '\n';
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED