Palindromic characteristics of string s with length |s| is a sequence of |s|integers, where k-th number is the total number of non-empty substrings of s which are k-palindromes.
A string is 1-palindrome if and only if it reads the same backward as forward.
A string is k-palindrome (k > 1) if and only if:
- Its left half equals to its right half.
- Its left and right halfs are non-empty (k - 1)-palindromes.
The left half of string t is its prefix of length ⌊|t| / 2⌋, and right half — the suffix of the same length. ⌊|t| / 2⌋ denotes the length of string t divided by 2, rounded down.
Note that each substring is counted as many times as it appears in the string. For example, in the string "aaa" the substring "a" appears 3 times.
Input
The first line contains the string s (1 ≤ |s| ≤ 5000) consisting of lowercase English letters.
Output
Print |s| integers — palindromic characteristics of string s.
Examples
abba
6 1 0 0
abacaba
12 4 1 0 0 0 0
Note
In the first example 1-palindromes are substring «a», «b», «b», «a», «bb», «abba», the substring «bb» is 2-palindrome. There are no 3- and 4-palindromes here.
题意：
给定一个字符串，定义字符串的等级如下：
如果一个字符串是回文串，那么等级为1
如果他的左半边的字符串和右半边的字符串也都是回文串，那么等级为2.
如果他左半边的左半边和右半边是回文串，右边同，那么等级为3.
以此类推。。。。。
让求这个字符串的所有连续子串的等级情况，
你只需要输出等级为1~n的子串的个数就ok了。
思路：
用区间DP，n*n处理字符串，即dp[i][j] =1 则代表字符串s 中，s[i~j] 是一个回文串。
而数组f[i][j] 代表 s[i~j]的等级。
细节见代码，有详细的注释。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define dll(x) scanf("%I64d",&x) #define xll(x) printf("%I64d ",x) #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), ' ', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define db(x) cout<<"== [ "<<x<<" ] =="<<endl; using namespace std; typedef long long ll; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll powmod(ll a,ll b,ll MOD){ll ans=1ll;while(b){if(b&1)ans=ans*a%MOD;a=a*a%MOD;b>>=1;}return ans;} inline void getInt(int* p); const int maxn=1000010; const int inf=0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ char s[maxn]; int cnt[maxn]; const int N = 5e3+7; int dp[N][N]; int f[N][N]; int main() { // freopen("C:\Users\DH_M\Desktop\code_io\in.txt.txt","r",stdin); // freopen("C:\Users\DH_M\Desktop\code_io\out.txt.txt","w",stdout); scanf("%s",s+1); int len=strlen(s+1); repd(i,1,len) { dp[i][i]=dp[i][i-1]=1;// dp[i][i] 长度为1的字符串肯定是回文串，而dp[i][i-1]=1 是因为在区间DP转移的时候要用到。 f[i][i]=1;// 长度为1的串肯定只能是1等级的字符串 } cnt[1]+=len;// len个长度为1 的字符串加到等级为1的中 repd(k,2,len)// k 这里是枚举子串的长度 { // len = 5 // 1 2 3 4 5 // 1 5 // 1 2 repd(i,1,len+1-k) { int j=i+k-1;// 区间的左区间 dp[i][j]=dp[i+1][j-1]&(s[i]==s[j]);// 转移过程用到的”与“运算 // 因为s[i]~s[j] 想要是回文串，那么要在s[i+1]~s[j-1]是回文串的基础上，s[i]==s[j] // 这里长度为2的时候就要用到dp[i][i-1]=1 f[i][j]=dp[i][j] ? f[i][(i+j-1)/2]+1:0;// 等级转移， // 首先判断是不是回文串，如果不是，等级只能为0 // 如果是回文串，那么这个字符串的等级为他的左半边字符串的等级+1 cnt[f[i][j]]++;// 在答案数组中加一下 } } for(int i=len;i>=1;i--) { cnt[i]+=cnt[i+1];// 处理下答案数组，因为i+1等级的字符串一定也满足i等级 } repd(i,1,len) { printf("%d ",cnt[i] );// 输出答案 } // Input // abba // Output // 6 1 0 0 return 0; } inline void getInt(int* p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == ' ');if (ch == '-') {*p = -(getchar() - '0'); while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}} else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}}}