fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define sz(o) ((int)o.size())
  5. #define all(o) o.begin(), o.end()
  6. #define rep(i, a, b) for(int i = (a); i <= (b); i++)
  7. #define repr(i, a, b) for(int i = (a); i >= (b); i--)
  8.  
  9. typedef long long int ll;
  10. typedef vector<ll> vll;
  11. typedef vector<int> vi;
  12.  
  13. const int MAX = 26, INF = 1e7;
  14. vector<pair<string, int>> pats, texts;
  15. int q, n, m;
  16.  
  17. int getIdx(char c){ return c-'a'; }
  18.  
  19. struct node{
  20.     node* fail;
  21.     node* child[MAX];
  22.     int time;
  23.  
  24.     node(){
  25.         memset(child, 0, sizeof(child));
  26.         time = INF;
  27.         fail = NULL;
  28.     }
  29.  
  30.     void insert(string &str, int pos, int len, int id){
  31.         if(pos == len){
  32.             time = min(time, id);
  33.         }else{
  34.             int idx = getIdx(str[pos]);
  35.             if(!child[idx]){
  36.                 child[idx] = new node();
  37.                 child[idx]->insert(str, pos+1, len, id);
  38.             }else{
  39.                 child[idx]->insert(str, pos+1, len, id);
  40.             }
  41.         }
  42.     }
  43.  
  44. };
  45.  
  46. void move(node* &k, int c){
  47.     while(!k->child[c]) k = k->fail;
  48.     k = k->child[c];
  49. }
  50.  
  51. node* buildAhoTree(){
  52.     node* root = new node();
  53.     root->fail = root;
  54.     rep(i, 0, n-1){
  55.         root->insert(pats[i].first, 0, sz(pats[i].first), pats[i].second);
  56.     }
  57.  
  58.     queue<node*> q;
  59.     rep(i, 0, MAX-1){
  60.         if(root->child[i]){
  61.             root->child[i]->fail = root;
  62.             q.push(root->child[i]);
  63.         }else root->child[i] = root;
  64.     }
  65.  
  66.     while(!q.empty()){
  67.         node* cur = q.front();
  68.         q.pop();
  69.  
  70.         rep(i, 0, MAX-1){
  71.             if(cur->child[i]){
  72.                 q.push(cur->child[i]);
  73.                 node* k = cur->fail;
  74.                 move(k, i);
  75.                 cur->child[i]->fail = k;
  76.             }
  77.         }
  78.     }
  79.  
  80.     return root;
  81. };
  82.  
  83. bool match(node* root, string T, int id){
  84.     node* k = root;
  85.     rep(i, 0, sz(T)-1){
  86.         int idx = getIdx(T[i]);
  87.         while(k != root && !k->child[idx]) k = k->fail;
  88.         k = k->child[idx];
  89.         if(k->time < id) return 1;
  90.     }
  91.     return 0;
  92. }
  93.  
  94. void solve(int testcase) {
  95.     cin >> q;
  96.     rep(i, 1, q){
  97.         int t;
  98.         string str;
  99.         cin >> t >> str;
  100.         if(t==0) pats.push_back({str, i});
  101.         else texts.push_back({str, i});
  102.     }
  103.     n = sz(pats);
  104.     m = sz(texts);
  105.  
  106.     node* root = buildAhoTree();
  107.  
  108.     rep(i, 0, m-1){
  109.         if(match(root, texts[i].first, texts[i].second)) cout << "YES\n";
  110.         else cout << "NO\n";
  111.     }
  112. }
  113.  
  114. int main(){
  115.     #ifdef VPAL
  116.     freopen("in.txt", "r", stdin);
  117.     freopen("out.txt", "w", stdout);
  118.     #endif
  119.     ios_base::sync_with_stdio(false);
  120.     cin.tie(NULL);
  121.     cout.tie(NULL);
  122.     cout << setprecision(10);
  123.     clock_t b = clock();
  124.     int t = 1;
  125.     //cin >> t;
  126.     rep(tt, 1, t) solve(tt);
  127.     clock_t e = clock();
  128.     cerr << (double(e - b) / CLOCKS_PER_SEC) << " sec";
  129.     return 0;
  130. }
Success #stdin #stdout #stderr 0s 4448KB
comments (?)
stdin
copy 
12
0 cat
1 dogville
0 dog
1 dogville
1 gooutwithcat
1 gooutwithcrocodile
1 fancyconcatenation
0 crocodile
1 lacoste
1 gooutwithcrocodile
1 catalanreferendum
1 rocodile
stdout
copy 
NO
YES
YES
NO
YES
NO
YES
YES
NO
stderr
copy 
5.4e-05 sec
https://ideone.com/pqJHPQ
language:
C++14 (gcc 8.3)
created:
5 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!