题意：定义1阶回文串：从左到右读等于从右到左读。k（k>=2）阶回文串为：本身是1阶回文串，且左半边和右半边都是k-1阶回文串。左半边：[ l , l+(r-l+1)/2-1 ]；右半边：[ r-(r-l+1)/2+1 , r ]。求阶数为 1 到 len 的回文字串的个数。
题解：子问题！子问题！子问题！k阶回文串的第一个定义：自身是回文串，这个等价于s[ l+1 ][ r-1 ]是一个回文串 && s[ l ] == s[ r ]。第二个条件：左半边和右半边都是 k-1 阶回文串，显然当[ l .. r ]字串是一个回文串的时候，左右半边的阶数是相同的。那么我们可以按照长度来进行 dp ，这样保证在算[ l .. r ]最大的阶数的时候，左右半串都已经算完了。最后一个问题：一个k阶回文串，按照定义，他也是k-1阶，k-2阶……1阶回文串，因此我们只需要确定字串的最大阶就可以了。
dp[ l ][ r ]表示s[ l .. r ]的最大阶数。cot[ x ]表示 x阶串总共有cot[ x ]个。代码简单易懂，稍微注意一下初始条件就没问题了。
Code：
#include<bits/stdc++.h> using namespace std; const int MAX = 5050; char s[MAX]; int dp[MAX][MAX]; int cot[MAX]; int ans[MAX]; int main(){ scanf("%s",s); int len = strlen (s); for (int i=0;i<=len;i++){ dp[i][i] = 1; dp[i][i-1] = 1; } cot[1] = len; for (int k=2;k<=len;k++){ for (int l = 0;l<=len-k;l++){ int r = l+k-1; if (s[l]==s[r]&&dp[l+1][r-1]){ dp[l][r] = dp[l][l-1+((r-l+1)>>1)]+1; // printf("dp[%d][%d]:%d\n",l,r,dp[l][r]); cot[dp[l][r]]++; } } } int sum =0; for (int i=len;i>=1;i--){ sum+=cot[i]; ans[i] = sum; } for (int i=1;i<=len;i++){ printf("%d ",ans[i]); } return 0; }