← 返回题目列表

Codeforces · 476/E

E. 梦月和弦乐

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

Dreamoon 有一个字符串 s 和一个模式字符串 p。他首先从 s 中删除 x 个字符,得到字符串 s' 作为结果。然后他计算$$\mathsf{occ}(s',p)$$,它被定义为可以在s'中找到的等于p的非重叠子串的最大数量。他想让这个数字尽可能大。

更正式地说,让我们将 $$\operatorname{ans}(x)$$ 定义为 $$\mathsf{occ}(s',p)$$ 在所有 s' 上的最大值,该最大值可以通过从 s 中精确删除 x 个字符来获得。 Dreamoon 想知道 $$\operatorname{ans}(x)$$ 对于从 0 到 |s| 的所有 x其中|s|表示字符串 s 的长度。

输入

输入的第一行包含字符串 s (1 ≤ |s| ≤ 2 000)。

输入的第二行包含字符串 p (1 ≤ |p| ≤ 500)。

两个字符串都仅包含小写英文字母。

输出

打印 |s| + 单行中的 1 个空格分隔的整数,表示从 0 到 |s| 的所有 x 的 $$\operatorname{ans}(x)$$。

示例

输入 #1

aaaaa
aa

输出 #1

2 2 1 1 0 0

输入 #2

axbaxxb
ab

输出 #2

0 1 1 2 1 1 0 0

注意

对于第一个样本,去除 0 到 |s| 后 s' 对应的最佳值= s 中的 5 个字符是 {"aaaaa", "aaaa", "aaa", "aa", "a", ""}。

对于第二个样本,s'可能对应的最佳值为{“axbaxxb”,“abaxxb”,“axbab”,“abab”,“aba”,“ab”,“a”,“”}。