CF1575H Holiday Wall Ornaments

寒假即将来临。Chanek 先生想用装饰品装饰他家的墙壁。墙壁可以表示为一个长度为 $n$ 的二进制字符串 $a$。他最喜欢的侄子有另一个长度为 $m$ 的二进制字符串 $b$（$m \leq n$）。 Chanek 先生的侄子非常喜欢非负整数 $k$。他的侄子希望字符串 $a$ 中恰好有 $k$ 个 $b$ 作为子串出现。 然而，Chanek 先生并不知道 $k$ 的值。因此，对于每个 $k$（$0 \leq k \leq n - m + 1$），请你求出最少需要修改 $a$ 中多少个字符，使得 $b$ 在 $a$ 中恰好出现 $k$ 次。 如果字符串 $s$ 在字符串 $t$ 中恰好出现 $k$ 次，表示存在恰好 $k$ 对不同的 $(p, q)$，使得通过从 $t$ 的开头删除 $p$ 个字符和从结尾删除 $q$ 个字符，可以得到 $s$。

第一行包含两个整数 $n$ 和 $m$（$1 \leq m \leq n \leq 500$），分别表示二进制字符串 $a$ 和 $b$ 的长度。 第二行包含一个长度为 $n$ 的二进制字符串 $a$。 第三行包含一个长度为 $m$ 的二进制字符串 $b$。

输出 $n - m + 2$ 个整数，第 $(k+1)$ 个整数表示将 $a$ 修改为恰好包含 $k$ 个 $b$ 作为子串所需最少修改的字符数。

对于 $k = 0$，要使字符串 $a$ 不包含 101，可以只修改一个字符，例如： 100101011 $\rightarrow$ 100100011 对于 $k = 1$，也可以只修改一个字符： 100101011 $\rightarrow$ 100001011 对于 $k = 2$，无需修改。 由 ChatGPT 4.1 翻译