codeforces.contest/835/problem/D Palindromic characteristics （記憶化搜尋）

 Palindromic characteristics time limit per test 3 seconds memory limit per test 256 megabytes input standard input output standard output

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 tdivided 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.

一開始用STL T了，這題帶有結構性質，是以可以用記憶化搜尋，預處理任意兩個區間是否是合法（雙向搜尋），想不到這個預處理就很傷

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include <bits/stdc++.h>
using namespace std;
const int N = 5000+7;
typedef  long long LL;
const LL mod = 1e9+7;
char str[N];
int a[N][N], dp[N][N], ans[N];
int dfs(int l,int r)
{
    if(l>r) return 0;
    int len=(r-l+1)/2;
    if(dp[l][r]!=-1) return dp[l][r];
    if(!a[l][r]) return dp[l][r]=0;
    return  dp[l][r]=dfs(l,l+len-1)+1;
}


int main()
{
    scanf("%s",str);
    int len=strlen(str);
    memset(dp,-1,sizeof(dp));
    memset(a,0,sizeof(a));
    memset(ans,0,sizeof(ans));
    for(int i=0;i<len;i++)
    {
        for(int j=i, k=i;j>=0&&k<len;k++,j--)
        {
            if(str[j]==str[k]) a[j][k]=1;
            else break;
        }
        for(int j=i, k=i+1;j>=0&&k<len;k++,j--)
        {
            if(str[j]==str[k]) a[j][k]=1;
            else break;
        }
    }
    for(int i=0;i<len;i++)
    {
        for(int j=i;j<len;j++)
        {
            dp[i][j]=dfs(i,j);
            ans[dp[i][j]]++;
        }
    }
    for(int i=len;i>=1;i--)   ans[i]+=ans[i+1];
    for(int i=1;i<=len;i++)  printf("%d%c",ans[i],i==len?'\n':' ');
    return 0;
}