题目描述

WBY 有一个字符串 s 和一个模式串 p。他想知道依次从字符串 s 里删除 x (0 \(\leq\) x \(\leq\) |s|) 个字符得到字符串 s',在 s' 中能得到最多有多少个模式串 p。

输入格式

第一行一个字符串 s；
第二行一个模式串 p；
所有字符串仅有小写字母组成。

输出格式

输出 |s| + 1 个整数，表示依次从字符串 s 中删除 x (0 \(\leq\) x \(\leq\) |s|) 个字符得到字符串 s'，在字符串 s' 中最多有多少个模式串 p。

样例1

输入

aaaaa
aa

输出

2 2 1 1 0 0

样例2

输入

axbaxxb
ab

输出

0 1 1 2 1 1 0 0

数据范围

对于 30%的数据，1 \(\leq\) |s| \(\leq\) 100，1 \(\leq\) |p| \(\leq\) 50；
对于 100%的数据，1 \(\leq\) |s| \(\leq\) 2000，1 \(\leq\) |p| \(\leq\) 500。

限制

1s

样例解释

样例 1：字符串 s'= {"aaaaa", "aaaa", "aaa", "aa", "a", ""}，模式串p的个数={2 2 1 1 0 0}；
样例2：字符串s’= {"axbaxxb", "abaxxb", "axbab", "abab", "aba", "ab", "a", ""}，模式串p的个数={0 1 1 2 1 1 0 0}。

来源

Codeforces476E
CWOI新高二专题测试十⑨