Palindromic characteristics | Codeforces Round #427 (Div. 2)

const int R = 14;
// isp[k-1][l][r]は
// 部分文字列s[l, r)が
// k-回文であるかどうかを表す
bitset<5001> isp[R][5000];

// 部分文字列s[l, r)のハッシュ値
pii ha[5001][5001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    int n = sz(s);
    // 長さ1の文字列は1-回文
    rep(i, n)isp[0][i][i + 1] = isp[0][i][i] = 1;
    RollingHash rh(s);
    rep(i, n)FOR(j, i + 1, n + 1)ha[i][j] = rh.getHash(i, j);
    // ans[k-1]はk-回文の個数
    vi ans(n);
    // とりあえずながさ1の文字列はを1-回文として数える
    ans[0] = n;
    // 1-回文を全部調べる。すでにある回文の左右が同じ文字なら、更に長い回文を作れる
    for (int len = 0; len <= n-2; ++len) {
        for (int i = 1; i + len <= n - 1; ++i) {
            if (isp[0][i][i + len] && s[i - 1] == s[i + len]) {
                isp[0][i - 1][i + len + 1] = 1;
                ans[0]++;
            }
        }
    }

    // 実はk-回文に対してk+1回文の長さは2倍以上になるから
    // 2^(k-1) <= 文字列の長さ
    // くらいまで見ればいい。
    for (int k = 1; k < R; ++k)rep(i, n)FOR(j, i + 2, n + 1) {
        int len = (j - i) / 2;
        // 条件をそのまま見る。部分文字列の比較はローリングハッシュで
        if (isp[k - 1][i][i + len] && isp[k - 1][j - len][j] && ha[i][i + len] == ha[j - len][j]) {
            isp[k][i][j] = 1;
            ans[k]++;
        }
    }

    rep(i, n)cout << ans[i] << (i != n - 1 ? ' ' : '\n');
}