CF476E 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|)$。

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