长度为 |s| 的字符串 s 的回文特征是 |s| 的序列整数,其中第 k 个数字是 s 中 k 个回文的非空子串的总数。
一个字符串是 1 回文当且仅当它向后读与向前读相同。
字符串是 k 回文 (k > 1) 当且仅当:
1. 左半部分等于右半部分。
2.它的左右半部分是非空的(k - 1)-回文。
字符串 t 的左半部分是其长度为 ⌊|t| 的前缀/ 2⌋,和右半部分——相同长度的后缀。 ⌊|t| / 2⌋ 表示字符串 t 的长度除以 2,向下舍入。
请注意,每个子字符串的计数次数与它在字符串中出现的次数相同。例如,在字符串“aaa”中,子字符串“a”出现了 3 次。
输入
第一行包含由小写英文字母组成的字符串 s (1 ≤ |s| ≤ 5000)。
输出
打印 |s|整数 — 字符串 s 的回文特征。
示例
输入 #1
abba
输出 #1
6 1 0 0
输入 #2
abacaba
输出 #2
12 4 1 0 0 0 0
注意
在第一个示例中,1-回文是子串“a”、“b”、“b”、“a”、“bb”、“abba”,子串“bb”是 2-回文。这里没有 3 回文和 4 回文。