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