题目链接 题意是这样的:定义了一种k阶回文串，1-阶是普通的回文串，k-阶回文串的前半串和后半串必须是相等的(不是回文，例如abcabc,如果长度奇数中间的不管他)然后其前半串必须是k-1阶回文串，后半串必须是k-1阶回文串。 然后给一个串，问这个串有多少子串是i阶回文串(i从1到n，依次输出) 分析一下可以看出如果一个串是k阶回文串，那么他必然是k-1阶回文串，于是我们可以枚举该串的子串记录他最大能到达的阶数，然后通过区间dp转移一下。由于阶数的每次增长都必然伴随着串长的加倍，所以k最大只有logn个。直接区间dp复杂度o(n² logn)
#include<algorithm> #include<cstring> #include<string> #include<set> #include<map> #include<time.h> #include<cstdio> #include<vector> #include<list> #include<stack> #include<queue> #include<iostream> #include<stdlib.h> using namespace std; #define LONG long long const int INF=0x3f3f3f3f; const LONG MOD=1e9+ 7; const double PI=acos(-1.0); #define clrI(x) memset(x,-1,sizeof(x)) #define clr0(x) memset(x,0,sizeof x) #define clr1(x) memset(x,INF,sizeof x) #define clr2(x) memset(x,-INF,sizeof x) #define EPS 1e-10 #define lson l , mid , rt<< 1 #define rson mid + 1 ,r , (rt<<1)+1 #define root 1, n , 1 char str[5010] ; int ans [5010] ; int dp[5010][5010] ; int match[5010][5010] ; int main() { while(~scanf("%s",str+1)) { clr0(ans ) ; clr0(dp) ; str[0] = '#' ; int len = strlen(str ) ; len --; for(int i = 1 ; i <= len+5 ; ++i) dp[i][i-1] = 1 ; for(int i = 2 ; i <= len+5 ; ++i) dp[i][i-2] = 1 ; // for (int i=1;i<=len;i++) match[i][i]=1; for (int l=1;l<=len;l++) for (int i=1;i+l<=len;i++) if ( str[i] == str[i+l]) { if (l==1) match[i][i+l] = 1; else match[i][i+l] |= match[i+1][i+l-1]; } // for(int l = 1 ; l <= len ; ++ l) { for(int i = 1 ; i <= len ; ++ i) { int j = i + l -1; if( j > len ) break ; if(str[i] == str[j]) if(dp[i+1][j-1]) dp[i][j] = 1; int mid = l/2 ; if(l <= 1) continue ; if(l&1) { if(dp[i][i+mid-1] == dp[i+mid+1][j] ) { if( match[i][j] ) { if(str[i] == str[j]) dp[i][j] = max(dp[i][j] , dp[i][i+mid-1] + 1) ; } } } else { if(dp[i][i+mid-1] == dp[i+mid][j]) { if(str[i] == str[j] && match[i][j] ) dp[i][j] = max(dp[i][j] , dp[i][i+mid-1] + 1 ); } } } } for(int i = 1 ;i<= len ; ++ i) { for(int j = i ; j<= len ; ++ j) for(int k = 1 ;k<= dp[i][j] ; ++ k) ans[k] ++ ; } for(int i = 1;i <len ; ++ i)printf("%d ",ans[i]) ;printf("%d\n",ans[len]) ; } }