CF1469E A Bit Similar

我们称两个长度为 $k$ 的字符串 $a$ 和 $b$ 是“位相似”的，如果它们在某个位置上有相同的字符，即存在至少一个 $i \in [1, k]$ 使得 $a_i = b_i$。 给定一个长度为 $n$ 的二进制字符串 $s$（即由 $n$ 个 $0$ 和/或 $1$ 组成的字符串）和一个整数 $k$。我们用 $s[i..j]$ 表示从第 $i$ 个字符到第 $j$ 个字符的子串（即 $s[i..j] = s_i s_{i+1} s_{i+2} \dots s_{j-1} s_j$）。 我们称一个长度为 $k$ 的二进制字符串 $t$ 是“美丽的”，如果它与 $s$ 的所有长度恰好为 $k$ 的子串都是“位相似”的；也就是说，$t$ 与 $s[1..k], s[2..k+1], \dots, s[n-k+1..n]$ 都是“位相似”的。 你的任务是找出字典序最小的美丽字符串 $t$，或者报告不存在这样的字符串。字符串 $x$ 的字典序小于字符串 $y$，当且仅当 $x$ 是 $y$ 的前缀且 $x \ne y$，或者存在某个 $i$（$1 \le i \le \min(|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$）。第二行包含一个长度为 $n$ 的字符串 $s$，每个字符都是 $0$ 或 $1$。 保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每个测试用例，按如下方式输出答案： - 如果无法构造出美丽字符串，输出一行，内容为 NO（注意必须为大写，不能输出 No 等）。 - 否则，输出两行。第一行输出 YES（同样必须为大写）；第二行输出字典序最小的美丽字符串，长度为 $k$，只包含 $0$ 和 $1$。

由 ChatGPT 4.1 翻译