CF1575H Holiday Wall Ornaments

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 $ .

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.