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:
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
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.
题目大意
找回文串，一个k阶回文串的定义是他的左边一半是一个k-1阶回文串。输出1-|s|阶回文串的个数。
注意题目要求，一个k阶回文串也会在k-1阶里面计数，但这问题不大。
首先用通用技巧，在每两个字符之间增加一个字符，来避免讨论奇偶。
然后为了方便的判断阶数，我们可以暴力的开一个数组，来记录以L为起点以R为终点的字符串的阶数，非回文串为0，于是我们只需要枚举中间数，向两边拓展，然后阶数就等于一边的阶数加一即可。注意不要把前面增加的字符算进来。具体可以参见代码。
代码：
1 |
|