xgCQFQ - Online C++0x Compiler & Debugging Tool

// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

template<class T>
    bool minimize(T &a, const T &b) {
        if (a > b) return a = b, true;
        return false;
    }

template<class T>
    bool maximize(T &a, const T &b) {
        if (a < b) return a = b, true;
        return false;
    }

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "kstring"

const int MOD = 1e9 + 2277;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 50000 + 5;
const int base = 311;
struct Suffix_Array {
    const static int SIZE = 256;
    int p[N], c[N], pn[N], cn[N], cnt[N], tempClass[20][N], pos[N], rmq[N][20];
    string s;
    int n, classes;

    Suffix_Array() {
        n = 0;
        s = "";
    }

    void assignment(string _s) {
        s = _s;
        n = (int)_s.size();
        memset(cnt, 0, sizeof cnt);
    }

    void prepare() {
        for(char c : s) cnt[c]++;
        FOR(i, 1, SIZE) cnt[i] += cnt[i - 1];
        REP(i, n) p[--cnt[s[i]]] = i;
        classes = c[p[0]] = 0;
        FOR(i, 1, n - 1) {
            if (s[p[i]] != s[p[i - 1]])
                classes++;
            c[p[i]] = classes;
        }
    }

     void build_SA() {
        REP(h, 20) if (MASK(h) < n) {
            REP(i, n) tempClass[h][i] = c[i];
            REP(i, n) {
                pn[i] = p[i] - MASK(h);
                if (pn[i] < 0) pn[i] += n;
            }
            fill(cnt, cnt + classes + 1, 0);
            REP(i, n) cnt[c[pn[i]]]++;
            FOR(i, 1, classes) cnt[i] += cnt[i - 1];

            RED(i, n) {
                int cur_class = c[pn[i]];
                p[--cnt[cur_class]] = pn[i];
            }
            cn[p[0]] = classes = 0;
            FOR(i, 1, n - 1) {
                ii cur = mp(c[p[i]], c[(p[i] + MASK(h)) % n]);
                ii pre = mp(c[p[i - 1]], c[(p[i - 1] + MASK(h)) % n]);
                if (cur != pre) classes++;
                cn[p[i]] = classes;
            }

            REP(i, n) c[i] = cn[i];
        }
    }

    int LCP(int i, int j) {
        int ans = 0;
        RED(h, 20) if (MASK(h) < n && tempClass[h][i % n] == tempClass[h][j % n]) {
            ans += MASK(h);
            i += MASK(h);
            j += MASK(h);
        }
        return ans;
    }

    void build_SuffixArray(string s) {
        assignment(s);
        prepare();
        build_SA();
        REP(i, n) pos[p[i]] = i;
        REP(i, n - 1) rmq[i][0] = LCP(p[i], p[i + 1]);
        FOR(j, 1, 19) for(int i = 0; i < n - MASK(j); i++)
            rmq[i][j] = min(rmq[i][j - 1], rmq[i + MASK(j - 1)][j - 1]);
    }

    int lcp(int i, int j) {
        if (i == j) return n;
        i = pos[i-1]; j = pos[j-1];
        if (i > j) swap(i, j);
        j--;
        int k = __lg(j - i + 1);
        return min(rmq[i][k], rmq[j - MASK(k) + 1][k]);
    }
} SA;

int n, d;
string s;
int hsh[N], power[N];
vector<long long> newHash[N];

int getHash(int l, int r) {
    if (l > r) return 0;
    return (hsh[r] - 1LL * hsh[l - 1] * power[r - l + 1] % MOD + MOD) % MOD;
}

long long eraseHash(int pos, int l, int r) {
    int hashLeft = getHash(l, pos - 1);
    int hashRight = getHash(pos + 1, r);
    long long finalHsh = (1LL * hashLeft * power[r - pos] + hashRight);
    return finalHsh;
}

void init(void) {
    cin >> n >> d >> s;
    SA.build_SuffixArray(s + "#");
    s = " " + s;
    power[0] = 1;
    FOR(i, 1, n) {
        power[i] = 1LL * power[i - 1] * base % MOD;
        hsh[i] = (1LL * hsh[i - 1] * base + s[i]) % MOD;
    }
}

void process(void) {
    if (d == 0) {
        map<int, int> cnt;
        FOR(k, 1, n) {
            cnt.clear();
            for(int i = k; i <= n; i += k) cnt[getHash(i - k + 1, i)]++;
            ll ans = 0;
            for(auto x : cnt) ans += 1LL * x.se * (x.se - 1) / 2;
            cout << ans << ' ';
        }
    } else {
        int S = min(100, n);
        FOR(k, 1, S) {
            ll ans = 0;
            FOR(i, 0, k) newHash[i].clear();
            FOR(i, 1, n / k) {
                int l = (i - 1) * k + 1;
                int r = i * k;
                newHash[0].push_back(getHash(l, r));
                FOR(j, l, r) newHash[j - l + 1].push_back(eraseHash(j, l, r));
            }
            ll countSame = 0;
            FOR(i, 0, k) {
                sort(all(newHash[i]));
                int cnt = 1;
                FOR(j, 1, (int)newHash[i].size() - 1) {
                    if (newHash[i][j] == newHash[i][j - 1]) {
                        if (i == 0) countSame += cnt++;
                        else ans += cnt++;
                    } else cnt = 1;
                }
            }
            ans -= 1LL * countSame * (k - 1);
            cout << ans << ' ';
        }

        FOR(k, S + 1, n) {
            int m = n / k;
            ll ans = 0;
            FOR(i, 1, m) FOR(j, i + 1, m) {
                int l = (i - 1) * k + 1;
                int u = (j - 1) * k + 1;

                int same = SA.lcp(l, u);
                if (same >= k) ans++;
                else if (SA.lcp(l + same + 1, u + same + 1) >= k - same - 1) ans++;
            }
            cout << ans << ' ';
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int tc = 1;
//    cin >> tc;
    while(tc--) {
        init();
        process();
    }
    return 0;
}