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.     vector<string>allwords;
  12.     Trie() {
  13.         memset(child, 0, sizeof(child));
  14.     }
  15.     ~Trie() {
  16.         for (int i = 0; i < chars; i++) {
  17.             if (child[i]) {
  18.                 delete child[i];
  19.             }
  20.         }
  21.     }
  22.     //Problem 1 : a
  23.     void insert(string s) {
  24.         Trie* current = this;
  25.         for (char c : s) {
  26.             int index = c - 'a';
  27.             if (!current->child[index]) {
  28.                 current->child[index] = new Trie();
  29.             }
  30.             current = current->child[index];
  31.         }
  32.         allwords.push_back(s);
  33.         current->isLeaf = true;
  34.     }
  35.     //Problem 1 : b
  36.     bool word_exists(string s) {
  37.         Trie* current = this;
  38.         for (char c : s) {
  39.             int index = c - 'a';
  40.             if (!current->child[index]) {
  41.                 return false;
  42.             }
  43.             current = current->child[index];
  44.         }
  45.         return current->isLeaf;
  46.     }
  47.     //Problem 2 : minimal prefix
  48.     string first_word_prefix(const string &str){
  49.         vector<string>all;
  50.         Trie* current = this;
  51.         string prefix = "";
  52.         for (char c : str) {
  53.             int index = c - 'a';
  54.             if (!current->child[index]) break; 
  55.             prefix += c;
  56.             current = current->child[index];
  57.             if (current->isLeaf) all.push_back(prefix);
  58.         }
  59.         if(all.empty()){
  60.             return str;
  61.         }
  62.         return *min_element(all.begin(), all.end());
  63.     }
  64.     //Problem 3 : Is suffix
  65.     void SuffixExists(const string& s) {
  66.         for(auto word : allwords){
  67.             vector<string>allsuffixes;
  68.             for(int i = 0; i <(int) word.size(); i++){
  69.                 allsuffixes.push_back(word.substr(i));
  70.             }
  71.             for(auto w: allsuffixes){
  72.                 if(w == s){
  73.                     cout << "yes it is found \n";
  74.                     return;
  75.                 }
  76.             }
  77.         }
  78.         cout << "No suffix found" << endl;
  79.     }
  80. };
  81.  
  82. //Problem 4 and 5:
  83. class Trie3 {
  84. private:
  85.     //static const int size =256;
  86.     unordered_map<string, Trie3*> child;
  87.     bool isLeaf;
  88.  
  89. public:
  90.     Trie3() : isLeaf(false) {}
  91.  
  92.     ~Trie3() {
  93.         for (auto &entry : child) {
  94.             delete entry.second;
  95.         }
  96.     }
  97.  
  98.     void insert(const vector<string>& path) {
  99.         Trie3* current = this;
  100.         for (const auto& word : path) {
  101.             if (current->child.find(word) == current->child.end()) {
  102.                 current->child[word] = new Trie3();
  103.             }
  104.             current = current->child[word];
  105.         }
  106.         current->isLeaf = true; 
  107.     }
  108.  
  109.     bool subpath_exists(const vector<string>& path) {
  110.         Trie3* current = this;
  111.         for (const auto& word : path) {
  112.             if (current->child.find(word) == current->child.end()) {
  113.                 //first change than insert
  114.                 return false;
  115.             }
  116.             current = current->child[word];
  117.         }
  118.         //second change than insert
  119.         return true;  
  120.     }
  121. };
  122. int main() {
  123.     string s;cin >> s;
  124.     Trie trie;
  125.     trie.insert("hello");
  126.     trie.insert("manar");
  127.     trie.insert("man");
  128.     trie.insert("elhabbal");
  129.     trie.insert("xyz");
  130.     trie.insert("xyzea");
  131.     trie.insert("a");
  132.     trie.insert("bc");
  133.  
  134.     trie.SuffixExists("habbal");
  135.     trie.SuffixExists("nar");
  136.     trie.SuffixExists("lo");
  137.     trie.SuffixExists("gold");
  138.     cout <<"--------------------------------\n";
  139.     cout << trie.first_word_prefix("x")<<endl;
  140.     cout << trie.first_word_prefix("xyzabc")<<endl;
  141.     cout << trie.first_word_prefix("manarelhabbal")<<endl;
  142.     cout <<"--------------------------------\n";
  143.     Trie3 trie3;
  144.     vector<string> path1 = {"home","software","eclipse"};
  145.     vector<string> path2 = {"home","software","eclipse","bin"};
  146.     vector<string> path3 = {"home","installed","gnu"};
  147.     vector<string> path4 = {"user","mostafa","temp"};
  148.     trie3.insert(path1);
  149.     trie3.insert(path2);
  150.     trie3.insert(path3);
  151.     trie3.insert(path4);
  152.     vector<string>f1={"user","mostafa","temp"};
  153.     vector<string>f2={"user","mostafa"};
  154.     vector<string>f3={"user","mos"};
  155.     vector<string>f4={"user","mostafa","private"};
  156.     cout << trie3.subpath_exists(f1) << endl;
  157.     cout << trie3.subpath_exists(f2) << endl;
  158.     cout << trie3.subpath_exists(f3) << endl;
  159.     cout << trie3.subpath_exists(f4) << endl;
  160.     cout <<"--------------------------------\n";
  161.     return 0;
  162. }
  163.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Trie homwork1
stdout
copy 
yes it is found 
yes it is found 
yes it is found 
No suffix found
--------------------------------
x
xyz
man
--------------------------------
1
1
0
0
--------------------------------
https://ideone.com/IEPaGw
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!