fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int conv(char c) {
  5.     return (int)c;
  6. }
  7.  
  8. class Trie {
  9.     public:
  10.         Trie *next[256], *del[256], *suff, *dictSuff;
  11.         vector<int> ind;
  12.         bool done;
  13.         Trie();
  14.         ~Trie();
  15.         void destroy();
  16.         Trie *step(int ch);
  17. };
  18.  
  19. Trie::Trie(): suff(NULL), ind(vector<int>()), dictSuff(NULL), done(false) {
  20.     for (int i=0; i<256; i++) {
  21.         next[i]=NULL;
  22.         del[i]=NULL;
  23.     }
  24. }
  25.  
  26. Trie::~Trie() {
  27. }
  28.  
  29. void Trie::destroy() {
  30.     for (int i=0; i<256; i++) if (this->del[i]) this->del[i]->destroy();
  31.     delete this;
  32. }
  33.  
  34. Trie *Trie::step(int ch) {
  35.     if (this->next[ch]) {
  36.         return this->next[ch];
  37.     }
  38.     else if (this->suff) {
  39.         return this->next[ch]=this->suff->step(ch);
  40.     }
  41.     else return this;
  42. }
  43.  
  44. void addDict(Trie *t, vector<string>& v2) {
  45.     vector<pair<string,int> > v;
  46.     for (int i=0; i<(int)v2.size(); i++) {
  47.         v.push_back(make_pair(v2[i],i));
  48.     }
  49.     sort(v.begin(),v.end(),[](const pair<string,int>& a, const pair<string,int>& b)->bool {
  50.             return a.first.length()<b.first.length();
  51.             });
  52.     vector<Trie*> tnode(v.size(),t);
  53.     int j=0;
  54.     for (int i=0; j<v.size(); i++) {
  55.         for (int k=j; k<v.size(); k++) {
  56.             int ch=conv(v[k].first[i]);
  57.             if (!tnode[k]->next[ch]) {
  58.                 tnode[k]->next[ch]=new Trie();
  59.                 tnode[k]->del[ch]=tnode[k]->next[ch];
  60.             }
  61.             Trie *nd=tnode[k];
  62.             bool chng=(nd->next[ch]->suff==NULL);
  63.             if (chng) nd->next[ch]->suff=nd->suff;
  64.             nd=nd->next[ch];
  65.             if (chng) {
  66.                 while (nd->suff && !nd->suff->next[ch]) {
  67.                     nd->suff=nd->suff->suff;
  68.                 }
  69.                 if (nd->suff) {
  70.                     nd->suff=nd->suff->next[ch];
  71.                 }
  72.                 else {
  73.                     nd->suff=t;
  74.                 }
  75.                 nd->dictSuff=nd->suff;
  76.                 while (nd->dictSuff && nd->dictSuff->ind.size()==0) {
  77.                     nd->dictSuff=nd->dictSuff->dictSuff;
  78.                 }
  79.                 if (!nd->dictSuff) {
  80.                     nd->dictSuff=t;
  81.                 }
  82.             }
  83.             tnode[k]=nd;
  84.         }
  85.         while (j<v.size() && i+1==v[j].first.length()) {
  86.             tnode[j]->ind.push_back(v[j].second);
  87.             j++;
  88.         }
  89.     }
  90. }
  91.  
  92. string readstr() {
  93.     char c;
  94.     string ret="";
  95.     while ((c=getchar())!=EOF && c!='\n') {
  96.         ret+=c;
  97.     }
  98.     return ret;
  99. }
  100.  
  101. int readint() {
  102.     char c;
  103.     int tot=0;
  104.     while ((c=getchar())!=EOF && c!='\n') {
  105.         tot*=10;
  106.         tot+=c-'0';
  107.     }
  108.     return tot;
  109. }
  110.  
  111. int main(void) {
  112.     string s, ex;
  113.     int n;
  114.     vector<string> v;
  115.     vector<bool> good;
  116.     Trie *t=new Trie();
  117.     s=readstr();
  118.     n=readint();
  119.     for (int i=0; i<n; i++) {
  120.         ex=readstr();
  121.         v.push_back(ex);
  122.         good.push_back(false);
  123.     }
  124.     addDict(t,v);
  125.     Trie *now=t;
  126.     for (int i=0; i<s.length(); i++) {
  127.         now=now->step(conv(s[i]));
  128.         if (now->ind.size()>0) {
  129.             Trie *ex=now;
  130.             while (ex && ex->ind.size()>0 && !ex->done) {
  131.                 for (int val: ex->ind) good[val]=true;
  132.                 ex->done=true;
  133.                 ex=ex->dictSuff;
  134.             }
  135.         }
  136.     }
  137.     for (int i=0; i<n; i++) cout << (good[i]? 'Y': 'N') << "\n";
  138.     t->destroy();
  139.     return 0;
  140. }
  141.  
Success #stdin #stdout 0s 3288KB
comments (?)
stdin 
abghABCDE
2
abAB
ab
stdout 
N
Y
https://ideone.com/WFr1IN
language:
C++14 (gcc 8.3)
created:
10 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!