C. Dreamoon ба мөрүүд

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Dreamoon-д $s$ мөр мөн загвар мөр $p$ байна. Эхлээд тэр $s$ мөрөөс яг $x$ ширхэг тэмдгүүдийг устгах замаар үр дүнгийн $s'$ мөрийг гаргаж авна. $occ(s', p)$ нь $s'$-с $p$ мөртэй тэнцүү давхардаагүй дэд хэсгүүдийн хамгийн их тоог тооцож олно. Тэр энэ тоог аль болох их байлгахыг хүсэж байгаа.

Тодорхойлж хэлбэл $s$ мөрөөс яг $x$ тэмдэгт устгах замаар гаргаж авсан бүх $s'$ мөрийн $occ(s', p)$-ийн хамгийн их утгыг $ans(x)$ гэе. Dreamoon $ans(x)$-ийн $0$-с $|s|$ хүртэл бүх $x$-ийн утгыг мэдэхийг хүсэж байгаа, $|s|$ нь $s$ мөрийн уртыг илэрхийлнэ.

Оролт

Эхний мөрөнд $s$ ($1 ≤ |s| ≤ 2 000$) мөрийг оруулна.

Хоёрдугаар мөрөнд $p$ ($1 ≤ |p| ≤ 500$) мөрийг орулна.

Эдгээр хоёр мөр нь зөвхөн Англи жижиг үсэгнээс бүрдэнэ.

Гаралт

Нэг мөрөнд $|s| + 1$ ширхэг бүхэл тоог зайгаар тусгаарлан хэвлэнэ. $0$-с $|s|$ хүртэл бүх $x$ нь $ans(x)$-г төлөөлнө.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
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", ""} байна.

Сэтгэгдлүүдийг ачааллаж байна...