A9576. 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$ .

The first line of the input contains the string $s$ ( $1<=|s|<=2000$ ).

The second line of the input contains the string $p$ ( $1<=|p|<=500$ ).

Both strings will only consist of lower case English letters.

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

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", ""}.