Substring Distribution

const int max_v = 1e5 +10, LOGN = 40;
char str[max_v];
int sa[max_v], rk[max_v], buckets[max_v], lcp[max_v];
int tmp[max_v], pos[max_v], st[max_v * 2][LOGN], n;
ll psum[MX];
void print_arr(int n, int * arr){
  for(int i = 1; i<=n; i++) printf("%d ", arr[i]);
  puts("");
}

void comp_SA(){
  int mx = 260;
  for(int i = 1; i<=n; i++){
    sa[i] = i;
    rk[i] = str[i];
  }

  for(int i = 1; i >> 1 < n; i <<= 1){
    int k = i >> 1, p = k;
    for(int j = 1; j<=k; j++) buckets[j] = n - (j - 1);
    for(int j = 1; j<=n; j++) if(sa[j] > k) buckets[++p] = sa[j] - k;
    memset(pos, 0, sizeof(pos));
    for(int j = 1; j<=n; j++) pos[rk[j]]++;
    for(int j = 1; j<=mx; j++) pos[j] += pos[j - 1];
    for(int j = n; j; j--) sa[pos[rk[buckets[j]]]--] = buckets[j];
    for(int j = 1; j<=n; j++) tmp[sa[j]] = tmp[sa[j - 1]] + (rk[sa[j]] != rk[sa[j - 1]] || rk[sa[j] + k] != rk[sa[j - 1] + k]);
    for(int j = 1; j<=n; j++) rk[j] = tmp[j];
    mx = rk[sa[n]];
    if(mx == n) break; //optimization to help run faster on 'sparser strings'
  }

}

void make_lcp(){
  for(int i = 1; i<=n; i++){
        if(rk[i] == 1) cont;
    lcp[rk[i]] = max(0, lcp[rk[i - 1]] - 1);
    for(; str[i + lcp[rk[i]]] == str[sa[rk[i] - 1] + lcp[rk[i]]]; lcp[rk[i]]++);
  }
}

int main(){
  cin.tie(0) -> sync_with_stdio(0);
    cin >> (str + 1);
    n = strlen(str + 1);
    comp_SA();
    make_lcp();
    for(int i = 1; i<=n; i++){
        int l = lcp[i], r = sa[i];
        psum[l+1]++;
        psum[r+1]--;
    }
    for(int i = 1; i<=n; i++){
        psum[i] += psum[i - 1];
    }
    for(int i = 1; i<=n; i++){
        cout << psum[i] << " ";
    }
    cout << "\n";
  return 0;
}