Palindromic characteristics [Codeforces Round #427 (Div. 2) D]

http://codeforces.com/contest/835/problem/D

概要

アルファベット小文字からなる文字列Sがある。

1-palindromeは回文
k-palindromeは
1. 前半と後半が等しい
2. 前半と後半が(k-1)-palindromeである
文字列

前半は前半floor(len/2)の文字列で、後半も後半floor(len/2)の文字列。

k-palindromeとなる連続する文字列が何通りあるか、それぞれ答えよ

解法

http://codeforces.com/contest/835/submission/29087550

公式解説のほぼ和訳

大事な観察が2つある。
1つ目は「k-palindromeであれば(k-1)-palindromeである」
2つ目は「ある連続文字列が回文で前半が(k-1)-palindromeであれば、その文字列はk-palindromeである」
これを元に解法を作る
　
pand[i][j] := 連続部分文字列[i,j]は回文か
「S[i] == S[j] && pand[i+1][j-1]==1 であれば pand[i][j]=1」を漸化式としながら作る。
　
dp[i][j] := 連続部分文字列[i,j]の最大のpalindrome数(kのこと)
「pand[i][j] == 1であれば、dp[i][j] = dp[i][i + len / 2 - 1] + 1」を漸化式としながら作る。
　
あとは、ans[dp[i][j]]++をして最大のpalindromeをカウントするが、観察1より、それ以下にもインクリメントする必要があるため、累積和的に足していって答えとする。

string S; int N;
int pand[5010][5010];
int dp[5010][5010];
int ans[5010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    N = S.length();

    rep(i, 0, N) pand[i][i] = 1;
    rep(len, 2, N + 1) rep(i, 0, N) {
        int j = i + len - 1;
        if (N <= j) break;

        int ok = 1;
        if (S[i] != S[j]) ok = 0;
        if (i + 1 < j) if (!pand[i + 1][j - 1]) ok = 0;
        pand[i][j] = ok;
    }

    rep(i, 0, N) dp[i][i] = 1;
    rep(len, 2, N + 1) rep(i, 0, N) {
        int j = i + len - 1;
        if (N <= j) break;

        if (pand[i][j]) dp[i][j] = dp[i][i + len / 2 - 1] + 1;
    }

    rep(i, 0, N) rep(j, i, N) ans[dp[i][j]]++;
    rrep(i, 5000, 0) ans[i] += ans[i + 1];

    rep(i, 0, N) {
        if (i) printf(" ");
        printf("%d", ans[i + 1]);
    }
    printf("\n");
}