fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. using pii = pair<int,int>;
  5.  
  6. struct Hash {
  7.     static const int base1 = 1e9 + 975, base2 = 1e9 + 1357;
  8.     static const int mod1 = 1e9 + 5277, mod2 = 1e9 + 7277;
  9.     vector<int> pw1, pw2, h1, h2;
  10.     int n;
  11.     void assign(const string &s) {
  12.         n = s.size();
  13.         pw1.assign(n+1,0);
  14.         pw2.assign(n+1,0);
  15.         h1.assign(n+1,0);
  16.         h2.assign(n+1,0);
  17.         pw1[0] = pw2[0] = 1;
  18.         for(int i = 1; i <= n; i++){
  19.             pw1[i] = (pw1[i-1] * 1LL * base1) % mod1;
  20.             pw2[i] = (pw2[i-1] * 1LL * base2) % mod2;
  21.             int v = s[i-1] - 'A' + 1;
  22.             h1[i] = (h1[i-1] * 1LL * base1 + v) % mod1;
  23.             h2[i] = (h2[i-1] * 1LL * base2 + v) % mod2;
  24.         }
  25.     }
  26.     pii get(){
  27.         int x1 = h1[n];
  28.         int x2 = h2[n];
  29.         return {x1, x2};
  30.     }
  31. };
  32.  
  33. bool cmp(const pii &A, const pii &B){
  34.     return A.first == B.first && A.second == B.second;
  35. }
  36.  
  37.  
  38.  
  39. signed main(){
  40.     ios::sync_with_stdio(false);
  41.     cin.tie(nullptr);
  42.  
  43.     int n, m; cin >> n;
  44.     string x;
  45.     vector<Hash> A(n);
  46.     vector<pii> a(n);
  47.  
  48.     for(int i = 0; i < n; i++){
  49.     	cin >> x;
  50.     	A[i].assign(x);
  51.     	a[i] = (A[i].get());
  52.     }
  53.     cin >> m;
  54.     vector<Hash> B(m);
  55.     vector<pii> b(m);
  56.     for(int i = 0; i < m; i++){
  57.     	cin >> x;
  58.     	bool flg = 0;
  59.     	B[i].assign(x);
  60.     	pii k = B[i].get();
  61.     	for(int j = 0; j < n; j++){
  62.     		if(k == a[j]){
  63.     			cout << "YES" << endl;
  64.     			flg = 1;
  65.     			break;
  66.     		}
  67.     	}
  68.     	if(!flg) cout << "NO" << endl;
  69.  
  70.     }
  71.  
  72.  
  73.  
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
4
Book
Chair
Time
Laptop
3
PC
Time
time
stdout 
NO
YES
NO
https://ideone.com/krKmV1
language:
C++14 (clang 8.0)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!