fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct node{
  4.     int cnt_trees;
  5.     bool endmark;
  6.     node *next[26];
  7.     node(){
  8.         cnt_trees=0;
  9.         endmark=false;
  10.         for(int i=0;i<26;i++) next[i]=NULL;
  11.     }
  12. }*root;
  13.  
  14. void insert_into_Trie(char* str,int len){
  15.     node *cur=root;
  16.     for(int i=0;i<len;i++){
  17.         int id=str[i]-'a';
  18.         if(cur->next[id]==NULL)
  19.             cur->next[id]=new node();
  20.             cur=cur->next[id];
  21.     }
  22.     cur->endmark=true;
  23. }
  24.  
  25. node* search_into_Trie(char* str,int len){
  26.     node *cur=root;
  27.     for(int i=0;i<len;i++){
  28.         int id=str[i]-'a';
  29.         if(cur->next[id]==NULL) return NULL;
  30.         cur=cur->next[id];
  31.     }
  32.     return cur;
  33. }
  34.  
  35. void lexicograpPrint(node *cur,char* prefix,vector<char>print_word){
  36.  
  37.         if(cur->endmark and print_word.size()!=0){
  38.             printf("%s",prefix);
  39.             for(auto x:print_word) printf("%c",x);
  40.             printf("\n");
  41.         }
  42.  
  43.     for(int i=0;i<26;i++){
  44.         if(cur->next[i]!=NULL){
  45.             print_word.push_back(i+'a');  //push converting integer int character
  46.             lexicograpPrint(cur->next[i],prefix,print_word);
  47.             print_word.pop_back();
  48.         }
  49.     }
  50.     print_word.pop_back();
  51. }
  52.  
  53. int main()
  54. {
  55.  
  56.     int n,q;
  57.     char str[21];
  58.     root=new node();
  59.     scanf("%d",&n);
  60.     while(n--){
  61.         scanf(" %s",str);
  62.         insert_into_Trie(str,strlen(str));
  63.     }
  64.     scanf("%d",&q);
  65.     int tc=0;
  66.     while(q--){
  67.         scanf(" %s",str);
  68.         cout<<"Case #"<<++tc<<":"<<endl;
  69.         bool childrenThere=false;
  70.         node *temp=search_into_Trie(str,strlen(str));
  71.         if(temp!=NULL){            //that means the whole prefix remains in the Trie
  72.             for(int i=0;i<26;i++){
  73.                 if(temp->next[i]!=NULL){childrenThere=true;break;} //prefix has children.so needed to print
  74.             }
  75.             if(childrenThere){
  76.                 vector<char>print_word;
  77.                 lexicograpPrint(temp,str,print_word);   //printing Trie Lexicographically
  78.             }
  79.             else cout<<"No match."<<endl;
  80.         }
  81.         else cout<<"No match."<<endl;
  82.     }
  83.     return 0;
  84. }
  85.  
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
5

set

lol

setter

setting

settings

2

set

happy
stdout
copy 
Case #1:
setter
setting
settings
Case #2:
No match.
https://ideone.com/AkFgDI
language:
C++14 (gcc 8.3)
created:
7 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!