| Codeforces Round 272 (Div. 2) |
|---|
| Закончено |
У Dreamoon есть строка s и шаблон p. Сперва он удаляет ровно x символов из s, в результате чего получается строка s'. Затем он подсчитывает 
, которое определяется как максимальное количество непересекающихся подстрок, равняющихся p, которые можно выделить в s'. Он хочет, чтобы это число было как можно больше.
Более формально, определим 
как максимальное значение по всем s', которые можно получить, удалив ровно x символов из s.
Dreamoon хочет знать для всех x от 0 до |s|, где |s| обозначает длину строки s.
В первой строке записана строка s (1 ≤ |s| ≤ 2 000).
Во второй строке записана строка p (1 ≤ |p| ≤ 500).
Обе строки состоят только из строчных букв латинского алфавита.
Выведите на единственной строке |s| + 1 целых чисел через пробел — для всех x от 0 до |s|.
aaaaa
aa
2 2 1 1 0 0
axbaxxb
ab
0 1 1 2 1 1 0 0
В первом примере соответствующие оптимальные s' после удаления от 0 до |s| = 5 символов из s таковы: {«aaaaa», «aaaa», «aaa», «aa», «a», «»}.
Для второго примера оптимальные s' могут выглядеть как {«axbaxxb», «abaxxb», «axbab», «abab», «aba», «ab», «a», «»}.
