【cf477C】Dreamoon and Strings

2014年10月13日1,6680

Dreamoon has a string s and a pattern string p. He first removes exactly x characters from sobtaining 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 allx from 0 to |s| where |s| denotes the length of string s.

Input

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.

Output

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

Sample test(s)
input

output

input

output

Note

For the first sample, the corresponding optimal values of s after removal 0 through |s| = 5characters 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”, “”}.

 

题解

f[i][j]表示前i个删j个可以匹配的最大次数

f[i][j]=max(f[i-1][j],f[i-len(p)-cal()][j-cal()]+1)

cal()表示从第i位往前,使得s的末尾与p匹配最少要删多少个

因为f[i][j]>=f[i-1][j-1]所以多删没有意义