В далеком будущем информация — самый ценный ресурс. Ты — элитный криптограф в Межгалактической разведке. Недавно был перехвачен бинарный сигнал $$$s$$$ длиной $$$n$$$ — предположительно, сообщение вражеской организации. По данным разведки, они используют специальный код $$$t$$$ длины $$$m$$$, который вставляется в передаваемые сигналы, чтобы передать секретные команды.
Но есть проблема: из-за космических помех часть битов могла быть случайно испорчена. Теперь перед тобой стоит важная задача: изменить минимум битов в сигнале $$$s$$$, чтобы в нем ровно $$$k$$$ раз встречалась подстрока $$$t$$$, для каждого возможного $$$k$$$ от $$$0$$$ до $$$n - m + 1$$$.
Минимальное число изменений — это количество замен 0 → 1 или 1 → 0, которые нужно сделать в $$$s$$$, чтобы точно $$$k$$$ вхождений подстроки $$$t$$$ появилось в измененной версии $$$s$$$.
Штаб-квартира ждет отчета: для каждого $$$k$$$ — какова минимальная цена (в изменениях), чтобы получить $$$k$$$ вхождений $$$t$$$?
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ — длины бинарных строк a и b соответственно $$$ (1 \le m \le n \le 500) $$$. Вторая строка содержит бинарную строку $$$s$$$ длины $$$n$$$. Третья строка содержит бинарную строку $$$t$$$ длины $$$m$$$.
Выведите $$$n - m + 2$$$ целых чисел: Пусть $$$k$$$ — это количество вхождений строки $$$b$$$ в строку $$$a$$$. Тогда $$$k+1$$$-е выведенное число должно означать минимальное число изменений (замен 0 на 1 или 1 на 0) в строке $$$s$$$, которые необходимо сделать, чтобы строка $$$t$$$ встретилась ровно $$$k$$$ раз как подстрока в $$$s$$$.
5 2 01010 10
2 1 0 -1 -1
k = 0 (чтобы убрать все вхождения 10): Можно изменить 1 символ, например 01010 → 00000, тогда 10 ни разу не встретится. Ответ: 2.
k = 1 (чтобы осталась одна подстрока 10): Строка 01010 можно оставить как есть и изменить один из двух вхождений. Например: 01010 → 01110. Ответ: 1.
k = 2 (оставить оба вхождения): Исходная строка уже подходит. Ничего менять не нужно. Ответ: 0.
