Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- typedef long long ll;
- template<typename T>
- using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- const int N = 1007;
- const int MOD = 1e9 + 7;
- const double OO = 1e9;
- ll myhash(string &str) {
- ll ans = 0;
- for (char i : str) {
- ans |= 1 << (i - 'a');
- }
- return ans;
- }
- ll myhash(int *arr) {
- ll ans = 0;
- for (int i = 0; i < 26; ++i) {
- if (arr[i])
- ans |= 1 << i;
- }
- return ans;
- }
- ll prep[N][N];
- int n, q;
- string str;
- int hashed[26];
- void pre() {
- for (int k = 1; k < n; ++k) {
- ll letters = 0;
- memset(hashed, 0, sizeof hashed);
- for (int i = 0; i < k - 1; ++i) {
- letters ^= (1 << (str[i] - 'a'));
- hashed[str[i] - 'a']++;
- }
- for (int en = k - 1; en < n; ++en) {
- letters ^= (1 << (str[en] - 'a'));
- hashed[str[en] - 'a']++;
- if (__builtin_popcount(letters) <= 1)
- prep[k][en] = myhash(hashed);
- else
- prep[k][en] = 0;
- letters ^= (1 << (str[en-k+1] - 'a'));
- hashed[str[en-k+1] - 'a']--;
- }
- }
- }
- int k;
- string temp;
- int main() {
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "rt", stdin);
- #else
- freopen("wcup.in", "rt", stdin);
- #endif
- ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
- int t;
- cin >> t;
- while (t--) {
- cin >> n >> q;
- cin >> str;
- pre();
- while (q--) {
- cin >> k;
- cin >> temp;
- ll h = myhash(temp);
- bool ok = 0;
- for (int en = k - 1; en < n; ++en) {
- if (prep[k][en] == h) {
- cout << en << endl;
- ok = 1;
- break;
- }
- }
- cout << (ok ? "YES\n" : "NO\n");
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement