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.     ~Trie() {
  16.         for (int i = 0; i < chars; i++) {
  17.             if (child[i]) {
  18.                 delete child[i];
  19.             }
  20.         }
  21.     }
  22.  
  23.     void insert(const string& s, int idx = 0) {
  24.         if (idx == s.length()) {
  25.             isLeaf = true;
  26.         } else {
  27.             int cur = s[idx] - 'a';
  28.             if (child[cur] == nullptr) {
  29.                 child[cur] = new Trie();
  30.             }
  31.             child[cur]->insert(s, idx + 1);
  32.         }
  33.     }
  34.  
  35.     bool wordExists(const string& s, int idx = 0) const {
  36.         if (idx == s.size()) return isLeaf;
  37.         int cur = s[idx] - 'a';
  38.         if (!child[cur]) return false;
  39.         return child[cur]->wordExists(s, idx + 1);
  40.     }
  41.  
  42.     bool prefixExists(const string& s, int idx = 0) const {
  43.         if (idx == s.size()) return true;
  44.         int cur = s[idx] - 'a';
  45.         if (!child[cur]) return false;
  46.         return child[cur]->prefixExists(s, idx + 1);
  47.     }
  48.  
  49.     // Check if a word exists by modifying one character
  50.     //Problem 3 : hw2
  51.     bool findModifiedWord(string s) {
  52.         for (int i = 0; i < s.length(); i++) {
  53.             char original = s[i];
  54.             for (char j = 'a'; j <= 'z'; j++) {
  55.                 if (j != original) {
  56.                     s[i] = j;
  57.                     if (wordExists(s)) {
  58.                         return true;
  59.                     }
  60.                 }
  61.             }
  62.             s[i] = original;
  63.         }
  64.         return false;
  65.     }
  66.  
  67.     void insertAllSubs(const string& s) {
  68.         for (size_t i = 0; i < s.length(); i++) {
  69.             for (size_t j = i + 1; j <= s.length(); j++) {
  70.                 insert(s.substr(i, j - i));
  71.             }
  72.         }
  73.     }
  74.  
  75.     vector<string> findSubs(const string& s, const vector<string>& q) {
  76.         Trie subTrie;
  77.         subTrie.insertAllSubs(s);
  78.         vector<string> ans;
  79.         for (const auto& word : q) {
  80.             if (subTrie.wordExists(word)) {
  81.                 ans.push_back(word);
  82.             }
  83.         }
  84.         return ans;
  85.     }
  86. };
  87.  
  88. int main() {
  89.     Trie trie;
  90.     trie.insert("hello");
  91.     trie.insert("world");
  92.  
  93.     vector<string> q = {"hello", "world", "elhabbal", "cr7"};
  94.  
  95.     vector<string> subs = trie.findSubs("helloworldmanarelhabbal", q);
  96.     for (const auto& word : subs) {
  97.         cout << word << endl;
  98.     }
  99.  
  100.     return 0;
  101. }
  102.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
hello
world
elhabbal
https://ideone.com/zNZNxM
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!