fork(2) download 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <string>
  5. #include <sstream>
  6. #include <map>
  7. #include <list>
  8. #include <queue>
  9. #include <set>
  10. #include <algorithm>
  11. #include <climits>
  12. #include <cmath>
  13. #include <cassert>
  14. #include <stack>
  15. #include <bitset>
  16. #include <tr1/unordered_map>
  17. #include <tr1/unordered_set>
  18.  
  19. #define mp make_pair
  20. #define ll long long
  21. #define ull unsigned long long
  22. #define null NULL
  23.  
  24. const int INF=(INT_MAX>>2);
  25.  
  26. using namespace std;
  27.  
  28. string s;
  29.  
  30. struct node;
  31. struct node {
  32.     char s;
  33.     map<int,node*> e;
  34.     int pn;
  35.     node *f;
  36.     node(char c){
  37.         s=c;
  38.         f=null;
  39.         pn=-1;
  40.     }
  41. };
  42. node *root;
  43. void bfs() {
  44.     queue<node*> q;
  45.     for(map<int,node*>::iterator i=root->e.begin();i!=root->e.end();++i) {
  46.         i->second->f=root;
  47.         q.push(i->second);
  48.     }
  49.     for(;!q.empty();) {
  50.         node *u=q.front();
  51.         q.pop();
  52.         for(map<int,node*>::iterator v=u->e.begin();v!=u->e.end();++v) {
  53.             for(v->second->f=u->f;;) {
  54.                 if(v->second->f->e.find(v->second->s)!=v->second->f->e.end()) {
  55.                     v->second->f=v->second->f->e[v->second->s];
  56.                     break;
  57.                 } else {
  58.                     if(v->second->f==root) break;
  59.                     v->second->f=v->second->f->f;
  60.                 }
  61.             }
  62.             q.push(v->second);
  63.         }
  64.     }
  65. }
  66. int q;
  67. bool pf[1000];
  68. int h[1000];
  69. void search() {
  70.     memset(pf,0,sizeof(pf));
  71.     node *i=root;
  72.     for(string::iterator c=s.begin();c!=s.end();) {
  73.         if(i->e.find(*c)!=i->e.end()) {
  74.             i=i->e[*c];
  75.             for(node*k=i;k;k=k->f) {
  76.                 if(k->pn!=-1) {
  77.                     pf[k->pn]=true;
  78.                 }
  79.             }
  80.             ++c;
  81.         } else {
  82.             for(;i!=root && (i->e.find(*c)==i->e.end());i=i->f);
  83.             if(i->e.find(*c)!=i->e.end()) {
  84.                 continue;
  85.             } else {
  86.                 ++c;
  87.             }
  88.         }
  89.     }
  90.     for(int i=0;i<q;++i) printf("%c\n",pf[h[i]]?'y':'n');
  91. }
  92.  
  93. int main() {
  94. //    freopen("me.txt","r",stdin);
  95.     int t;
  96.     cin>>t;
  97.     for(string p;t--;) {
  98.         root=new node(0);
  99.         cin>>s;
  100.         cin>>q;
  101.         for(int i=0;i<q;++i) {
  102.             cin>>p;
  103.             node *k=root;
  104.             h[i]=i;
  105.             for(int j=0;j<p.size();++j) {
  106.                 if(k->e.find(p[j])!=k->e.end()) {
  107.                     k=k->e[p[j]];
  108.                 }  else {
  109.                     k=(k->e[p[j]]=new node(p[j]));
  110.                 }
  111.                 if(j==p.size()-1) {
  112.                     if(k->pn==-1){
  113.                         k->pn=i;
  114.                     } else {
  115.                         h[i]=k->pn;
  116.                     }
  117.                 }
  118.             }
  119.         }
  120.         bfs();
  121.         search();
  122.     }
  123.     return 0;
  124. }
  125.  
Success #stdin #stdout 0.02s 2828KB
comments (?)
stdin 
2
abcdefghABCDEFGH
2
abc
abAB
xyz
1
xyz
stdout 
y
n
y
https://ideone.com/zkDol
language:
C++ (gcc 8.3)
created:
14 years ago
visibility:
secret

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!