Codeforces Round #427 (Div. 2) D. Palindromic characteristics

D. Palindromic characteristics

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:

1. Its left half equals to its right half.
2. 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

Input

abba

Output

6 1 0 0 

Input

abacaba

Output

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-len阶回文串，k阶回文串的左边是有k-1阶回文串组成的，1阶回文串就是字符串的每一个子串回文串。

用dp来做，dp[i][j]表示字符串str[i...j]是否是回文串。O（n^2）的复杂度。

然后求dp[i][j]是第几阶回文串，可以用递归来做，如果str[i..j]不是回文串的话，则返回0，否则返回str[i...m]+1,m表示子串str[i....j]的左串的右边位置。i==j,在递归会出现m<l的因为，返回0；

只好可以把1阶回文串的左边看成由0阶回文串组成的。由于k阶回文串又是k-1,k-2...1阶会文串，所以要ans[i-1] += ans[i]

#include <bits/stdc++.h>
using namespace std;
const int MAX = 5010;
char str[MAX];
int dp[MAX][MAX], ans[MAX], n;
int getK(int l, int r) {
    if(dp[l][r] == 0) return 0;
    else {
        int m = (l+r);
        if(m&1) return getK(l,m/2)+1;
        else return getK(l,m/2-1)+1;
    }
}
int main() {
    scanf("%s",str+1);
    int n = strlen(str+1);
    for(int i = 1; i <= n; i ++) {
        dp[i][i] = 1;
        if(i+1 <= n && str[i] == str[i+1]) dp[i][i+1] = 1;
    }
    for(int i = 3; i <= n; i ++) {
        for(int j = 1; j <= n-i+1; j ++) {
            int r = j+i-1;
            if(dp[j+1][r-1] && str[j] == str[r]) dp[j][r] = 1;
        }
    }
    for(int i = 1; i <= n; i ++) {
        for(int j = i; j <= n; j ++) {
            ans[getK(i,j)] ++;
        }
    }
    for(int i = n; i > 0; i --)
        ans[i-1] += ans[i];
    for(int i = 1; i <= n; i ++)
        printf("%d%c",ans[i],(i==n?'
':' '));
    return 0;
}