← 返回题目列表

Codeforces · 1575/H

H. 节日墙饰

中文机器翻译题面 查看原题

寒假马上就要到了。查内克先生想用装饰品装饰他房子的墙壁。墙可以表示为长度为 $$$n$$$ 的二进制字符串 $$$a$$$。他最喜欢的侄子有另一个长度为 $$$m$$$ 的二进制字符串 $$$b$$$ ($$$m \leq n$$$)。

Chanek 先生的侄子喜欢非负整数 $$$k$$$。他的侄子想要 $$$k$$$ 出现 $$$b$$$ 作为 $$$a$$$ 中的子字符串。

然而,Chanek 先生不知道 $$$k$$$ 的价值。因此,对于每个 $$$k$$$ ($$$0 \leq k \leq n - m + 1$$$),找到 $$$a$$$ 中必须更改的最小元素数,使得 $$$a$$$ 中 $$$b$$$ 恰好出现 $$$k$$$ 次。

如果存在 $$$k$$$ 个不同的对 $$$(p,q)$$$,则字符串 $$$s$$$ 在 $$$t$$$ 中恰好出现 $$$k$$$ 次,这样我们可以通过删除 $$$t$$$ 开头的 $$$p$$$ 字符和删除 $$$t$$$ 结尾的 $$$q$$$ 字符来获得 $$$s$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq m \leq n \leq 500$$$) — 分别是二进制字符串 $$$a$$$ 和 $$$b$$$ 的大小。

第二行包含长度为 $$$n$$$ 的二进制字符串 $$$a$$$。

第三行包含长度为$$$m$$$的二进制字符串$$$b$$$。

输出

输出 $$$n - m + 2$$$ 整数 — 第 $$$(k+1)$$$ 个整数表示 $$$a$$$ 中必须更改的最小元素数,因此 $$$b$$$ 作为子字符串在 $$$a$$$ 中恰好出现 $$$k$$$ 次。

示例

输入 #1

9 3
100101011
101

输出 #1

1 1 0 1 6 -1 -1 -1

注意

对于$$$k = 0$$$,要使字符串$$$a$$$中不出现101,可以按如下方式进行一个字符更改。

100101011 $$$\右箭头$$$ 100100011

对于 $$$k = 1$$$,您还可以更改单个字符。

100101011 $$$\右箭头$$$ 100001011

对于 $$$k = 2$$$,无需进行任何更改。