题目描述

给你一个串，让你求出 $k$ 阶回文子串有多少个。$k$ 阶回文的定义是如下：

1. 所有回文串都是 $1$ 阶回文。
2. 如果一个回文串是 $k$ 阶回文，那么它首先是一个回文串，并且它的左半边是一个 $k-1$ 阶回文。（$k\ge2$）

这里字符串的左半边指的是长度为一半（向下取整）的前缀。例如 aabaa 的左半边是 aa。

需要注意如果一个字符串是 $k$ 阶回文，那它同时也是 $k-1$ 阶以及更低阶的回文。

给出字符串 $s$，记 $n$ 为字符串的长度，对 $k=1\sim n$ 分别求出 $k$ 阶子串的个数。（位置不同就算是不同的子串）

输入格式

$1$ 行，包含 $1$ 个字符串 $s$。

输出格式

用 $1$ 行输出 $n$ 个整数，第 $i$ 个整数表示 $i$ 阶回文子串的数量。数之间用空格分隔。

说明与提示

在第一个样例中，$1$ 阶子串有 a、b、b、a、bb、abba。$2$ 阶子串只有 bb。

来源

浩轩OJ 4384 · 原题图片

数据范围与约定

字符串 $s$ 只含小写英文字母，记 $n$ 是字符串长度，$1\le n\le5000$。

可见测试数据

输入数据 1

abba

输出数据 1

6 1 0 0

输入数据 2

abacaba

输出数据 2

12 4 1 0 0 0 0

输入数据 3

sjjs

输出数据 3

6 1 0 0