Holiday Wall Ornaments

题意翻译

- 给你两个二进制串 $a,b$，长度分别为 $n,m(m\le n\le 500)$。 - 对于每个 $i(0\le i\le n-m+1)$，你需要求出对串 $a$ 经过**最小**几次变换后，使串中出现串 $b$ 的**次数**为 $i$。若无法得到，则输出-1。每次询问**独立**，不受之前影响。 - 每次变换能使 $a$ 中的某一位变成1或0。

题目描述

The Winter holiday will be here soon. Mr. Chanek wants to decorate his house's wall with ornaments. The wall can be represented as a binary string $ a $ of length $ n $ . His favorite nephew has another binary string $ b $ of length $ m $ ( $ m \leq n $ ). Mr. Chanek's nephew loves the non-negative integer $ k $ . His nephew wants exactly $ k $ occurrences of $ b $ as substrings in $ a $ . However, Mr. Chanek does not know the value of $ k $ . So, for each $ k $ ( $ 0 \leq k \leq n - m + 1 $ ), find the minimum number of elements in $ a $ that have to be changed such that there are exactly $ k $ occurrences of $ b $ in $ a $ . A string $ s $ occurs exactly $ k $ times in $ t $ if there are exactly $ k $ different pairs $ (p,q) $ such that we can obtain $ s $ by deleting $ p $ characters from the beginning and $ q $ characters from the end of $ t $ .

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1 \leq m \leq n \leq 500 $ ) — size of the binary string $ a $ and $ b $ respectively. The second line contains a binary string $ a $ of length $ n $ . The third line contains a binary string $ b $ of length $ m $ .

输出格式

Output $ n - m + 2 $ integers — the $ (k+1) $ -th integer denotes the minimal number of elements in $ a $ that have to be changed so there are exactly $ k $ occurrences of $ b $ as a substring in $ a $ .

输入输出样例

输入样例 #1

9 3
100101011
101

输出样例 #1

1 1 0 1 6 -1 -1 -1

说明

For $ k = 0 $ , to make the string $ a $ have no occurrence of 101, you can do one character change as follows. 100101011 $ \rightarrow $ 100100011 For $ k = 1 $ , you can also change a single character. 100101011 $ \rightarrow $ 100001011 For $ k = 2 $ , no changes are needed.