fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define PB push_back
  5. #define FI first
  6. #define SE second
  7. #define MP make_pair
  8. #define ALL(cont) cont.begin(), cont.end()
  9.  
  10. class trienode
  11. {
  12. public:
  13.     trienode *children[256];
  14.     bool word;
  15.     trienode()
  16.     {
  17.         for(int i=0;i<256;i++)
  18.             children[i] = NULL;
  19.         word = false;
  20.     }
  21. };
  22.  
  23. void insert(trienode *head, string val)
  24. {
  25.     int n = val.length();
  26.     for(int i=0;i<n;i++)
  27.     {
  28.         if(head->children[val[i]]==NULL)
  29.             head->children[val[i]] = new trienode();
  30.         head = head->children[val[i]];
  31.     }
  32.     head->word = true;
  33. }
  34.  
  35. void recur(trienode *head, string val)
  36. {
  37.     if(head->word==true)
  38.         cout<<val<<endl;
  39.     for(int i=0;i<256;i++)
  40.     {
  41.         if(head->children[i]!=NULL)
  42.             recur(head->children[i],val+((char)i));
  43.     }
  44. }
  45.  
  46. void query(trienode *head, string val)
  47. {
  48.     int n = val.length();
  49.     for(int i=0;i<n;i++)
  50.     {
  51.         if(head->children[val[i]]==NULL)
  52.         {
  53.             cout<<"No suggestions"<<endl;
  54.             return;
  55.         }
  56.         head = head->children[val[i]];
  57.     }
  58.     recur(head,val);
  59. }
  60.  
  61. int main()
  62. {
  63.     ios::sync_with_stdio(0);
  64.     cin.tie(0);
  65. #ifndef ONLINE_JUDGE
  66.     freopen("input.txt", "r", stdin);
  67.     freopen("output.txt", "w", stdout);
  68. #endif
  69.  
  70.  
  71.     int n;
  72.     string x;
  73.     cin>>n;
  74.     trienode *head = new trienode();
  75.     while(n--)
  76.     {
  77.         cin>>x;
  78.         insert(head,x);
  79.     }
  80.     int q;
  81.     cin>>q;
  82.     while(q--)
  83.     {
  84.         cin>>x;
  85.         query(head,x);
  86.     }
  87.     return 0;
  88.  
  89.  
  90. }
Success #stdin #stdout 0s 4464KB
comments (?)
stdin
copy 
4
pet
peter
rat
rack
5
pe
pet
r
rac
rat
stdout
copy 
pet
peter
pet
peter
rack
rat
rack
rat
https://ideone.com/GY1MPg
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!