Dreamoon and Strings

题意翻译

## 题目描述： Dreamoon 有一个字符串 $s$ 和一个模式串 $p$，他会先从 $s$ 中删除恰好 $x$ 个字符来产生一个新的字符串 $s'$。然后他会计算 $occ(s',p)$，即从 $s'$ 中能找到的等于 $p$ 的不相交的子串数量的最大值。他想让 $occ(s',p)$ 的值尽可能大。 更形式地说，让我们用 $ans(x)$ 表示所有可以从 $s$ 中删去恰好 $x$ 个字符得到的 $s'$ 中 $occ(s',p)$ 的最大值。Dreamoon 想要知道对于所有的 $x$ $(0 \leq x \leq |s|)$，$ans(x)$ 的值。 ## 输入格式： 第一、二行分别输入一个字符串：$s$，$p$。$(1 \leq |s| \leq 2000,1 \leq |p| \leq 500)$，两串只包含小写英文字母。 ## 输出格式： 一行，$(|s|+1)$ 个数，分别代表 $ans(0),ans(1),\dots,ans(|s|)$。

题目描述

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

输入输出样例

输入样例 #1

aaaaa
aa

输出样例 #1

2 2 1 1 0 0

输入样例 #2

axbaxxb
ab

输出样例 #2

0 1 1 2 1 1 0 0

说明

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