A Bit Similar

题意翻译

多测。 给定长度为 $n$ 的串 $\alpha$，求字典序最小的串长为 $k$ 的串 $\beta$，满足： $$\forall i\in[1,n-k+1](\ \exists j\in[1,k] \ \alpha_{j+i-1}=\beta_{j})$$ 若无解输出一行 NO。 有解第一行输出 YES，第二行输出串 $\beta$。

题目描述

Let's call two strings $ a $ and $ b $ (both of length $ k $ ) a bit similar if they have the same character in some position, i. e. there exists at least one $ i \in [1, k] $ such that $ a_i = b_i $ . You are given a binary string $ s $ of length $ n $ (a string of $ n $ characters 0 and/or 1) and an integer $ k $ . Let's denote the string $ s[i..j] $ as the substring of $ s $ starting from the $ i $ -th character and ending with the $ j $ -th character (that is, $ s[i..j] = s_i s_{i + 1} s_{i + 2} \dots s_{j - 1} s_j $ ). Let's call a binary string $ t $ of length $ k $ beautiful if it is a bit similar to all substrings of $ s $ having length exactly $ k $ ; that is, it is a bit similar to $ s[1..k], s[2..k+1], \dots, s[n-k+1..n] $ . Your goal is to find the lexicographically smallest string $ t $ that is beautiful, or report that no such string exists. String $ x $ is lexicographically less than string $ y $ if either $ x $ is a prefix of $ y $ (and $ x \ne y $ ), or there exists such $ i $ ( $ 1 \le i \le \min(|x|, |y|) $ ), that $ x_i < y_i $ , and for any $ j $ ( $ 1 \le j < i $ ) $ x_j = y_j $ .

输入输出格式

输入格式

The first line contains one integer $ q $ ( $ 1 \le q \le 10000 $ ) — the number of test cases. Each test case consists of two lines. The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le k \le n \le 10^6 $ ). The second line contains the string $ s $ , consisting of $ n $ characters (each character is either 0 or 1). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^6 $ .

输出格式

For each test case, print the answer as follows: - if it is impossible to construct a beautiful string, print one line containing the string NO (note: exactly in upper case, you can't print No, for example); - otherwise, print two lines. The first line should contain the string YES (exactly in upper case as well); the second line — the lexicographically smallest beautiful string, consisting of $ k $ characters 0 and/or 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

题意翻译

多测。 给定长度为 $n$ 的串 $\alpha$，求字典序最小的串长为 $k$ 的串 $\beta$，满足： $$\forall i\in[1,n-k+1](\ \exists j\in[1,k] \ \alpha_{j+i-1}=\beta_{j})$$ 若无解输出一行 NO。 有解第一行输出 YES，第二行输出串 $\beta$。