证明在Tutorial的评论版里
/*
CodeForces 835D - Palindromic characteristics [ 分析,DP ] | Codeforces Round #427 (Div. 2)
题意：
定义 k 回文串满足：
1. 左右子串相等
2. 左右子串为k-1回文串
1 回文串 就是回文串
问你字符串s的子串的每阶回文子串的数目
分析：
研究一下可以发现 k 回文串的要求等价于
1. 本身是回文串
2. 左右子串是k-1回文串
然后可以dp了，还有一个结论是：
若一个串是 k 回文，那它一定是 k-1 回文
方便最后统计
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
char s[N];
int len;
int dp[N][N], ans[N];
void init()
{
int l;
for (int i = 0; i < len; i++)
{
l = 0;
while (i-l >= 0 && i+l < len && s[i-l] == s[i+l])
{
dp[i-l][i+l] = 1; ++ans[1];
++l;
}
l = 0;
while (i-l >= 0 && i+l+1 < len && s[i-l] == s[i+l+1])
{
dp[i-l][i+l+1] = 1; ++ans[1];
++l;
}
}
}
void solve()
{
for (int k = 2; k <= len; k++)
{
for (int i = 0; i < len; i++)
{
int j = i+k-1;
int mid = i+k/2-1;
if (dp[i][mid] && dp[i][j])
{
dp[i][j] = max(dp[i][j], dp[i][mid]+1);
ans[dp[i][j]]++;
}
}
}
}
int main()
{
scanf("%s", s);
len = strlen(s);
init();
solve();
for (int i = len; i >= 2; i--)
ans[i] += ans[i+1];
for (int i = 1; i <= len; i++)
printf("%d ", ans[i]);
puts("");
}
update*修改了错误的代码