fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int p = 261, mod = 1e9+7, N = 100010;
  5. string str;
  6. int n, arr[N], p_pow[N];
  7.  
  8. void cal_arr() {
  9.     p_pow[0] = 1;
  10.     for(int i=0, curr=0; i<n; i++) {
  11.         curr += 1LL*p_pow[i]*(str[i]-'0'+1)%mod;
  12.         p_pow[i+1] = 1LL*p_pow[i]*p%mod;
  13.         if(curr>=mod)
  14.             curr -= mod;
  15.         arr[i] = curr;
  16.     }
  17. }
  18.  
  19. int get_hash(string str) {
  20.     int hash = 0;
  21.     for(int i=0; i<(int)str.length(); i++) {
  22.         hash += 1LL*p_pow[i]*(str[i]-'0'+1)%mod;
  23.         if(hash>=mod)
  24.             hash -= mod;
  25.     }
  26.     return hash;
  27. }
  28.  
  29. bool check(int x, int k) {
  30.     int hash = 0;
  31.     for(int i=k-1; i<n; i++) {
  32.         hash = arr[i] - (i>=k ? arr[i-k] : 0);
  33.         if(hash<0)
  34.             hash += mod;
  35.         if(hash==x)
  36.             return 1;
  37.         x = 1LL*p*x%mod;
  38.     }
  39.     return 0;
  40. }
  41.  
  42. void solve() {
  43.     cin >> str;
  44.     n = str.length();
  45.     cal_arr();
  46.     int k;
  47.     cin >> k;
  48.     string t;
  49.     while(k--) {
  50.         cin >> t;
  51.         cout << ( check(get_hash(t), t.length()) ? 'Y' : 'N' ) << '\n';
  52.     }
  53. }
  54.  
  55. signed main() {
  56.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  57.  
  58.     #ifndef ONLINE_JUDGE
  59.         freopen("input.txt", "r", stdin);
  60.         freopen("output.txt", "w", stdout);
  61.     #endif
  62.  
  63.     //int _t; cin >> _t; while(_t--)
  64.     solve();
  65. }
Success #stdin #stdout 0s 4788KB
comments (?)
stdin
copy 
abghABCDE
2
abAB
ab
stdout
copy 
N
Y
https://ideone.com/zrInz2
problem SUB_PROB, based on SPOJ submission 27316130 (CPP14), 2021-01-21 16:53:46
language:
C++14 (gcc 8.3)
created:
3 years 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!