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

样例输入 #1

aaaaa
aa

样例输出 #1

2 2 1 1 0 0

样例 #2

样例输入 #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", ""}.