Advertisement
YEZAELP

TOI10: รหัสวิฬาร์ (CAT Codes)

Dec 31st, 2020
135
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.24 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. const lli PB = 98765431;
  6. unordered_map <lli, int> hashing;
  7. int ans[1000000];
  8. char str[1000010];
  9.  
  10. int main(){
  11.  
  12.     int n, m;
  13.     scanf("%d%d", &n, &m);
  14.  
  15.     lli rem = 1;
  16.     for(int i=1;i<=n;i++){
  17.         lli hsh = 0;
  18.         scanf("%s", str);
  19.         for(int j=0;j<m;j++){
  20.             if(i == 1 and j != 0) rem *= PB;
  21.             hsh = hsh * PB + str[j];
  22.         }
  23.         hashing[hsh] = i;
  24.     }
  25.  
  26.     scanf("%d", &n);
  27.  
  28.     for(int i=1;i<=n;i++){
  29.         int l, idx = 0;
  30.         scanf("%d", &l);
  31.         lli hsh = 0;
  32.         scanf("%s", str);
  33.         for(int j=0;j<l;j++){
  34.             hsh = hsh * PB + str[j];
  35.             if(j >= m-1){
  36.                 if(hashing[hsh] != 0){
  37.                     ans[idx] = hashing[hsh];
  38.                     idx ++;
  39.                 }
  40.                 hsh = hsh - rem * str[j-m+1];
  41.             }
  42.         }
  43.         if(idx == 0) printf("OK\n");
  44.         else {
  45.             sort(ans, ans + idx);
  46.             int prev = 0;
  47.             for(int j=0;j<idx;j++){
  48.                 if(prev != ans[j]) printf("%d ", ans[j]);
  49.                 prev = ans[j];
  50.             }
  51.             printf("\n");
  52.         }
  53.     }
  54.  
  55.     return 0;
  56. }
  57.  
Advertisement
RAW Paste Data Copied
Advertisement