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