fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Trie{
  5.     private:
  6.     static const int chars =26;
  7.     Trie* child[chars];
  8.     bool isLeaf {};
  9.  
  10.     public:
  11.     Trie(){
  12.         memset(child,0,sizeof(child));
  13.     }
  14.  
  15.     void insert(string s ,int idx){
  16.         if(idx == s.length()){
  17.             isLeaf =true;
  18.         }
  19.         else{
  20.             int cur = s[idx]-'a';
  21.             if(child[cur] == nullptr){
  22.                 child[cur] = new Trie();
  23.             }
  24.             child[cur]->insert(s,idx+1);
  25.         }
  26.     }
  27.     vector<string>getAllsubstr(string s){
  28.         vector<string> res;
  29.         for(int i=0;i<s.length();i++){
  30.             for(int j=i+1;j<=s.length();j++){
  31.                 res.push_back(s.substr(i,j-i));
  32.             }
  33.         }
  34.         return res;
  35.     }
  36.     vector<string> findSubs(const string& s,vector<string>&q){
  37.         vector<string> poss=getAllsubstr(s);
  38.         vector<string>ans;
  39.         for(auto word :q){
  40.             for(auto sub : poss){
  41.                 if(sub==word){
  42.                     ans.push_back(sub);
  43.                     break;
  44.                 }
  45.             }
  46.         }
  47.         return ans;
  48.     }
  49. };
  50. int main(){
  51.     Trie trie;
  52.     trie.insert("hello",0);
  53.     trie.insert("world",0);
  54.  
  55.     vector<string> q = {"hello","world","elhabbal","cr7"};
  56.     vector<string> subs = trie.findSubs("helloworldmanarelhabbal",q);
  57.     for(auto word : subs){
  58.         cout<<word<<endl;
  59.     }
  60.  
  61.     return 0;
  62. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
hello
world
elhabbal
https://ideone.com/iHwqpD
language:
C++ (gcc 8.3)
created:
4 days 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!