← 返回题目列表

Codeforces · 1469/E

E. 有点相似

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

如果两个字符串 $$$a$$$ 和 $$$b$$$ (长度均为 $$$k$$$)在某个位置具有相同的字符,那么我们称它们有点相似,即。 e. [1, k]$$$ 中至少存在一个 $$$i 使得 $$$a_i = b_i$$$。

给定一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$(由 $$$n$$$ 字符 0 和/或 1 组成的字符串)和一个整数 $$$k$$$。我们将字符串 $$$s[i..j]$$$ 表示为 $$$s$$$ 的子字符串,从第 $$$i$$$ 个字符开始,到第 $$$j$$$ 个字符结束(即 $$$s[i..j] = s_i s_{i + 1} s_{i + 2} \dots s_{j - 1} s_j$$$)。

如果长度为 $$$k$$$ 的二进制字符串 $$$t$$$ 与长度恰好为 $$$k$$$ 的 $$$s$$$ 的所有子字符串有点相似,我们称其为漂亮;也就是说,它有点类似于 $$$s[1..k], s[2..k+1], \dots, s[n-k+1..n]$$$。

您的目标是找到按字典顺序排列的最小且漂亮的字符串 $$$t$$$,或者报告不存在这样的字符串。如果 $$$x$$$ 是 $$$y$$$ 的前缀(和 $$$x \ne y$$$),或者存在这样的 $$$i$$$ ($$$1 \le i \le \min(|x|, |y|)$$$),则字符串 $$$x$$$ 按字典顺序小于字符串 $$$y$$$,且 $$$x_i < y_i$$$,并且对于任何$$$j$$$ ($$$1 \le j < i$$$) $$$x_j = y_j$$$。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10000$$$) — 测试用例的数量。每个测试用例由两行组成。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 10^6$$$)。第二行包含字符串 $$$s$$$,由 $$$n$$$ 个字符组成(每个字符为 0 或 1)。

保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,打印答案如下:

- 如果无法构造一个漂亮的字符串,则打印包含字符串 NO 的一行(注意:例如,完全大写,您不能打印 No);
- 否则,打印两行。第一行应包含字符串 YES(也是大写);第二行 — 按字典顺序排列的最小的漂亮字符串,由 $$$k$$$ 字符 0 和/或 1 组成。

示例

输入 #1

7
4 2
0110
4 2
1001
9 3
010001110
9 3
101110001
10 3
0101110001
10 10
1111111111
11 10
11111111110

输出 #1

YES
11
YES
00
YES
010
YES
101
NO
YES
0000000001
YES
0000000010