SHARE
TWEET

Untitled

a guest Nov 12th, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. typedef long long ll;
  7. template<typename T>
  8. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  9.  
  10. const int N = 1007;
  11. const int MOD = 1e9 + 7;
  12. const double OO = 1e9;
  13.  
  14. ll myhash(string &str) {
  15.     ll ans = 0;
  16.     for (char i : str) {
  17.         ans |= 1 << (i - 'a');
  18.     }
  19.     return ans;
  20. }
  21.  
  22. ll myhash(int *arr) {
  23.     ll ans = 0;
  24.     for (int i = 0; i < 26; ++i) {
  25.         if (arr[i])
  26.             ans |= 1 << i;
  27.     }
  28.     return ans;
  29. }
  30.  
  31. ll prep[N][N];
  32. int n, q;
  33. string str;
  34.  
  35. int hashed[26];
  36.  
  37. void pre() {
  38.     for (int k = 1; k < n; ++k) {
  39.         ll letters = 0;
  40.         memset(hashed, 0, sizeof hashed);
  41.         for (int i = 0; i < k - 1; ++i) {
  42.             letters ^= (1 << (str[i] - 'a'));
  43.             hashed[str[i] - 'a']++;
  44.         }
  45.         for (int en = k - 1; en < n; ++en) {
  46.             letters ^= (1 << (str[en] - 'a'));
  47.             hashed[str[en] - 'a']++;
  48.  
  49.             if (__builtin_popcount(letters) <= 1)
  50.                 prep[k][en] = myhash(hashed);
  51.             else
  52.                 prep[k][en] = 0;
  53.  
  54.             letters ^= (1 << (str[en] - 'a'));
  55.             hashed[str[en] - 'a']--;
  56.         }
  57.     }
  58. }
  59.  
  60. int k;
  61. string temp;
  62.  
  63. int main() {
  64. #ifndef ONLINE_JUDGE
  65.     freopen("input.txt", "rt", stdin);
  66. #else
  67.     freopen("wcup.in", "rt", stdin);
  68. #endif
  69.     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  70.     int t;
  71.     cin >> t;
  72.     while (t--) {
  73.         cin >> n >> q;
  74.         cin >> str;
  75.         pre();
  76.         while (q--) {
  77.             cin >> k;
  78.             cin >> temp;
  79.             ll h = myhash(temp);
  80.             bool ok = 0;
  81.             for (int en = k - 1; en < n; ++en) {
  82.                 if (prep[k][en] == h) {
  83.                     cout << en << endl;
  84.                     ok = 1;
  85.                     break;
  86.                 }
  87.             }
  88.             cout << (ok ? "YES\n" : "NO\n");
  89.         }
  90.     }
  91.     return 0;
  92. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top