{"raw_statement":[{"iden":"statement","content":"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.\n\nA string is 1\\-palindrome if and only if it reads the same backward as forward.\n\nA string is _k_\\-palindrome (_k_ > 1) if and only if:\n\n1.  Its left half equals to its right half.\n2.  Its left and right halfs are non-empty (_k_ - 1)-palindromes.\n\nThe 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.\n\nNote 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."},{"iden":"input","content":"The first line contains the string _s_ (1 ≤ |_s_| ≤ 5000) consisting of lowercase English letters."},{"iden":"output","content":"Print |_s_| integers — palindromic characteristics of string _s_."},{"iden":"examples","content":"Input\n\nabba\n\nOutput\n\n6 1 0 0 \n\nInput\n\nabacaba\n\nOutput\n\n12 4 1 0 0 0 0"},{"iden":"note","content":"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."}],"translated_statement":[{"iden":"statement","content":"字符串 #cf_span[s]（长度为 #cf_span[|s|]）的回文特征是一个包含 #cf_span[|s|] 个整数的序列，其中第 #cf_span[k] 个数表示 #cf_span[s] 中所有是 #cf_span[k]-回文串的非空子串的总数。\n\n一个字符串是 #cf_span[1]-回文串，当且仅当它正读和反读完全相同。\n\n一个字符串是 #cf_span[k]-回文串（#cf_span[k > 1]），当且仅当：\n\n字符串 #cf_span[t] 的左半部分是其长度为 #cf_span[⌊|t| / 2⌋] 的前缀，右半部分是其长度相同的后缀。#cf_span[⌊|t| / 2⌋] 表示字符串 #cf_span[t] 的长度除以 #cf_span[2] 后向下取整的结果。\n\n注意，每个子串根据其在字符串中出现的次数被重复计数。例如，在字符串 \"aaa\" 中，子串 \"a\" 出现了 3 次。\n\n第一行包含一个由小写英文字母组成的字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 5000]）。\n\n请输出 #cf_span[|s|] 个整数——字符串 #cf_span[s] 的回文特征。\n\n在第一个例子中，1-回文串是子串 «a»、«b»、«b»、«a»、«bb»、«abba»，子串 «bb» 是 2-回文串。这里不存在 3-回文串和 4-回文串。"},{"iden":"input","content":"第一行包含一个由小写英文字母组成的字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 5000]）。"},{"iden":"output","content":"请输出 #cf_span[|s|] 个整数——字符串 #cf_span[s] 的回文特征。"},{"iden":"examples","content":"输入\nabba\n输出\n6 1 0 0 \n输入\nabacaba\n输出\n12 4 1 0 0 0 0 "},{"iden":"note","content":"在第一个例子中，1-回文串是子串 «a»、«b»、«b»、«a»、«bb»、«abba»，子串 «bb» 是 2-回文串。这里不存在 3-回文串和 4-回文串。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s $ be a string of length $ n = |s| $, with $ s[i] \\in \\{a, b, \\dots, z\\} $ for $ i \\in \\{1, \\dots, n\\} $.  \nFor $ k \\in \\mathbb{Z}^+ $, a non-empty substring $ t = s[i:j] $ (with $ 1 \\leq i \\leq j \\leq n $) is a **$ k $-palindrome** if:\n\n- $ k = 1 $: $ t $ is a palindrome, i.e., $ t_\\ell = t_{|t|+1-\\ell} $ for all $ \\ell \\in \\{1, \\dots, |t|\\} $.\n- $ k > 1 $:  \n  (i) $ t $ is a palindrome, and  \n  (ii) the left half of $ t $, defined as the prefix of length $ \\left\\lfloor \\frac{|t|}{2} \\right\\rfloor $, is a $ (k-1) $-palindrome.\n\nLet $ P_k \\subseteq \\{ s[i:j] \\mid 1 \\leq i \\leq j \\leq n \\} $ be the set of all $ k $-palindromic substrings of $ s $.\n\n**Constraints**  \n$ 1 \\leq n = |s| \\leq 5000 $\n\n**Objective**  \nCompute the sequence $ (c_1, c_2, \\dots, c_n) $, where for each $ k \\in \\{1, \\dots, n\\} $:  \n$$\nc_k = |P_k|\n$$  \ni.e., $ c_k $ is the total number of non-empty substrings of $ s $ that are $ k $-palindromes.  \n\nOutput $ c_1, c_2, \\dots, c_n $.","simple_statement":null,"has_page_source":false}