Codeforces 835D(区间DP+字符串DP)

第$k$阶的回文串本身是回文串
第$k$阶的回文串左右两边是第$k-1$阶的回文串

那么我们可以DP，设$dp(i,j)$为$[i,j]$为多少阶回文串
先判$[i,j]$是否回文，如果不是，那么$[i,j]$不构成任何阶的回文串；
否则$dp(i,j)=dp(i, i +\frac{ (j - i + 1)}{2} - 1)+1$，因为第$k$阶的回文串左右两边是第$k-1$阶的回文串
然后$[1, k-1]$阶的回文串一定包含了$[k, n]$的回文串，所以累加一下就行
然后区间DP用记忆化做

Codeforces Submission

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 5000 + 10;
char s[MAXN];
int n, f[MAXN][MAXN], ans[MAXN];
int dp(int i, int j) {
    if (f[i][j] >= 0) return f[i][j];
    if (i > j) return f[i][j] = 0;
    if (i == j) return f[i][j] = 1;
    if (s[i] != s[j] || (i + 1 <= j - 1 && dp(i + 1, j - 1) == 0)) return f[i][j] = 0;
    int a = dp(i, i + (j - i + 1) / 2 - 1);
    return f[i][j] = a + 1;
}
void clean() {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) f[i][j] = -1;
        ans[i] = 0;
    }
}
void solve() {
    n = strlen(s + 1);
    clean();
    for (int i = 1; i <= n; i++) 
    for (int j = i; j <= n; j++) dp(i, j);

    for (int i = 1; i <= n; i++) 
    for (int j = i; j <= n; j++) ans[f[i][j]]++;

    for (int i = n; i > 0; i--) ans[i] += ans[i + 1];

    for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
}
int main() {
    scanf("%s", s + 1), solve();
    return 0;
}