← 返回题目列表

Codeforces · 835/D

D. 回文特征

中文机器翻译题面 查看原题

长度为 |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 回文。