1469E - A Bit Similar

#include<bits/stdc++.h>
#define ri register int
#define ll long long
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid+1, r
using namespace std;
void re(int &x){
x = 0;
int b = 0;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') b = 1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
if(b == 1)
x *= -1;
}
const int maxn = 1100000;
const int p = 998244353;
int n, t, q, k;
int pw[maxn], has[maxn], a[maxn], num[maxn];
int ban[maxn];
char s[maxn];
int hashup(int l, int r){
return (has[r] - (ll)has[l-1] * pw[r-l+1] % p + p)%p;
}
void solve(){
for(int i = 1;i+k-1 <= n;i ++){
int x = hashup(max(i, i+k-20), i+k-1);
if(k > 20 && num[i+k-20] - num[i-1] > 0) continue;
if(x > 1e6) continue;
ban[x] = 1;
}
int x = -1, r = (1<<min(k, 21)) - 1;
for(int i = 0;i <= r;i ++){
if(!ban[i]){
x = i;
break;
}
}
string ans = "";
if(k >= 20) for(int i = 20;i <= k;i ++) ans += "0";
r = min(19, k);
for(int i = r-1;i >= 0;i --){
if(x&(1<<i)) ans += "1";
else ans += "0";
}
if(x != -1){
puts("YES");
cout << ans << endl;
}
else puts("NO");
}
int main(){
re(t);
pw[0] = 1;
for(int i = 1;i <= 30;i ++)
pw[i] = pw[i-1] * 2%p;
while(t --){
re(n), re(k);
scanf("%s",s+1);
memset(ban, 0, sizeof(ban));
for(int i = 1;i <= n;i ++){
a[i] = (s[i] == '0');
has[i] = (has[i-1]*2%p + a[i]) % p;
num[i] = num[i-1] + a[i];
}
solve();

}

return 0;
}