CF476E.Dreamoon and Strings

Dreamoon has a string s and a pattern string p. He first removes exactly x characters from s obtaining string s' as a result. Then he calculates that is defined as the maximal number of non-overlapping substrings equal to p that can be found in s'. He wants to make this number as big as possible.

More formally, let's define as maximum value of over all s' that can be obtained by removing exactly x characters from s. Dreamoon wants to know for all x from 0 to |s| where |s| denotes the length of string s.

Dreamoon 有一个字符串 $s$ 和一个模式字符串 $p$。他首先恰好从 $s$ 中删除 $x$ 个字符，得到字符串 $s'$。然后他计算
，其定义为：在 $s'$ 中所能找到的互不重叠且等于 $p$ 的子串的最大数目。他希望使该数值尽可能大。

更形式化地，定义
为对所有可通过从 $s$ 中恰好删除 $x$ 个字符而得到的 $s'$，对应
的最大值。Dreamoon 想要求出所有 $x$（从 $0$ 到 $|s|$）对应的
，其中 $|s|$ 表示字符串 $s$ 的长度。

The first line of the input contains the string s (1 ≤ |s| ≤ 2 000).

The second line of the input contains the string p (1 ≤ |p| ≤ 500).

Both strings will only consist of lower case English letters.

输入的第一行包含字符串 $s$（$1 \le |s| \le 2\,000$）。

输入的第二行包含字符串 $p$（$1 \le |p| \le 500$）。

两个字符串均由小写英文字母组成。

Print |s| + 1 space-separated integers in a single line representing the for all x from 0 to |s|.

在一行中输出 $\lfloor s \rfloor + 1$ 个以空格分隔的整数，表示对所有从 $0$ 到 $\lfloor s \rfloor$ 的 $x$ 对应的 。

For the first sample, the corresponding optimal values of s' after removal 0 through |s| = 5 characters from s are {"aaaaa", "aaaa", "aaa", "aa", "a", ""}.

For the second sample, possible corresponding optimal values of s' are {"axbaxxb", "abaxxb", "axbab", "abab", "aba", "ab", "a", ""}.

对于第一个样例，从字符串 $s$ 中分别删除 $0$ 到 $|s| = 5$ 个字符后，对应的最优 $s'$ 值依次为 $\{"aaaaa",\ "aaaa",\ "aaa",\ "aa",\ "a",\ ""\}$。

对于第二个样例，可能的对应最优 $s'$ 值依次为 $\{"axbaxxb",\ "abaxxb",\ "axbab",\ "abab",\ "aba",\ "ab",\ "a",\ ""\}$。