Codeforces Round #427 (Div. 2) D.Palindromic characteristics【DP、字尾和】

D. Palindromic characteristics

題意：

k-回文的定義：

1.它的左半部分等于右半部分，即本身是1-回文。

2.它的左半部分和右半部分都是(k-1)-回文，奇數長度不考慮正中間。

給你一串長度為n的字元串，讓你統計其所有子串中，是1-回文到n-回文的個數，并輸出。

思路：

1.暴力枚舉所有子串，計算它們的最高回文等級。

2.

dp[i][j]

表示從第i位到第j位的最高回文等級為

dp[i][j]

。

3.預處理長度小于等于2的子串。

4.先判斷計算的子串是不是回文串，如果不是回文串則

dp[i][j] = 0

。如果是回文串，即滿足題意中的1。

5.計算的子串長度為偶數時，

dp[l][r] = dp[l][mid] + 1

。

6.計算的子串長度為奇數時，

dp[l][r] = dp[l][mid-1] + 1

。

7.統計一下字尾和就是結果，因為k回文一定是k-1回文。

代碼：

#include <bits/stdc++.h>
using namespace std;
int dp[][]; //表示從i到j的回文等級為dp[i][j]
int ans[];
int main() {
    string s;
    cin >> s;
    int n = s.size();
    memset(ans, , sizeof(ans));
    memset(dp, , sizeof(dp));
    //len=1時，回文等級等于1
    for(int i = ; i < n; ++ i)
        dp[i][i] = ;
    //len=2時，如果兩個相等，那回文等級等于2，不然就不是回文串
    for(int i = ; i < n - ; ++ i)
        dp[i][i+] = (s[i] == s[i+] ?  : );
    //從len=3開始，n2周遊求dp[i][j]，長度大的可以由長度小的遞推而來，是以len從小到大周遊
    for(int len = ; len <= n; ++ len) {
        for(int l = ; l <= n - len; ++ l) {
            int r = l + len - ;
            //因為要求左字元串等于右字元串，是以也就是說整個字元串必須是回文串
            if(s[l] != s[r] || dp[l + ][r - ] == ) {
                dp[l][r] = ;
                continue;
            }

            //自己拿個紙畫下就知道邊界怎麼寫
            //由于已經知道字元串是回文串，是以它的結果就等于左邊/右邊等級+1
            //如果左邊不是回文串，那麼0+1就是1，也就是整個字元串回文等級為1
            int mid = l + r >> ;
            if(len %  == ) {
                dp[l][r] = dp[l][mid] + ;
            } else {
                dp[l][r] = dp[l][mid - ] + ;
            }
        }
    }
    //統計下最大等級為i的個數ans[i]
    for(int len = ; len <= n; ++ len) {
        for(int l = ; l <= n - len; ++ l) {
            ans[dp[l][l + len - ]]++;
        }
    }
    //求字尾和。因為k回文一定是k-1回文
    for(int i = n - ; i >= ; -- i) {
        ans[i] += ans[i + ];
    }
    for(int i = ; i <= n; ++ i) {
        if(i > ) putchar(' ');
        printf("%d", ans[i]);
    }
    putchar('\n');
}