题目链接：http://codeforces.com/contest/835/problem/D
题意：给定一个字符串，定义kth回文是左半部分等于右半部分，并且左半部分和右半部分都是(k-1)th回文。 只要是回文字串都是1th回文。 对于1<=k<=strlen(s),输出kth回文的数量。
思路：预处理出每个子串是否是回文。然后len^2枚举区间，如果s[i][j]是回文的话，继续枚举左半部分s[i][i+(j-i+1)/2-1]是否是回文，是的话再继续枚举左半部分然后顺便统计答案即可。 对于统计贡献，假设s[i][j]连续枚举了x次左半部分都是回文，第x+1次的左半部分不是回文，则说明s[i][j]是xth回文, s[i][j]的左半部分是x-1th回文....相当于把(1~x)th贡献+1，代码里是逆着算贡献即xth回文算到1th中，但是并不影响最后对答案的贡献
#define _CRT_SECURE_NO_DEPRECATE #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> #include<time.h> #include<cmath> #include<set> #include<map> using namespace std; typedef long long int LL; const int MAXN = 5000 + 24; const int INF = 1e9; const int mod = 1e9 + 7; char str[MAXN]; LL ans[MAXN]; bool isPalind[MAXN][MAXN]; void Make_Palind(int len){ for (int i = 0; i < len; i++) { int l = i, r = i; for (int l = i, r = i; l >= 0 && r < len&&str[l] == str[r]; l--, r++){ //奇长度回文 isPalind[l][r] = true; } for (int l = i, r = i + 1; l >= 0 && r < len&&str[l] == str[r]; l--, r++){ //偶长度回文 isPalind[l][r] = true; } } } int main(){ #ifdef kirito freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif while (~scanf("%s", str)){ int len = strlen(str); memset(ans, 0, sizeof(ans)); memset(isPalind, false, sizeof(isPalind)); Make_Palind(len); for (int i = 0; i < len; i++){ for (int j = i; j < len; j++){ for (int l = i, r = j, k = 1; l >= 0 && r < len && r >= l && isPalind[l][r]; r = l + (r - l + 1) / 2 - 1, k++){ ans[k]++; } } } for (int i = 1; i <= len; i++){ printf("%lld%c", ans[i], (i == len ? ' ' : ' ')); } } return 0; }