fork(1) download 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <map>
  4. #include <string>
  5. #include <vector>
  6. #include <set>
  7.  
  8. class Node
  9. {
  10. public:
  11.     bool endOfSentence = false;
  12.     std::set<int> weights;
  13.     std::map<std::string, Node> children;
  14.  
  15.     Node() = default;
  16.  
  17.     const Node* get(const std::string& word) const
  18.     {
  19.         auto it = children.find(word);
  20.  
  21.         if (it == children.end()) {
  22.             return nullptr;   
  23.         }
  24.         return &it->second;
  25.     }
  26.  
  27.     auto find_by_weight(int weight) const
  28.     {
  29.         return std::find_if(children.begin(),
  30.                             children.end(),
  31.                             [=](const auto& p){ return p.second.weights.count(weight);});
  32.     }
  33.  
  34. };
  35.  
  36.  
  37. class Trie
  38. {
  39.     Node root;
  40. public:
  41.  
  42.     void add(int weight, const std::vector<std::string>& phrase)
  43.     {
  44.         Node* node = &root;
  45.         for (const auto& word : phrase) {
  46.             node->weights.insert(weight);
  47.             node = &node->children[word];
  48.         }
  49.         node->weights.insert(weight);
  50.         node->endOfSentence = true;
  51.     }
  52.  
  53.     bool contains(const std::vector<std::string>& phrase) const
  54.     {
  55.         const Node* node = &root;
  56.         for (const auto& word : phrase) {
  57.             node = node->get(word);
  58.             if (node == nullptr) {
  59.                 return false;
  60.             }
  61.         }
  62.         return node->endOfSentence;
  63.     }
  64.  
  65.     void print(int weight) const
  66.     {
  67.         const Node* node = &root;
  68.         const char* sep = "";
  69.         while (node) {
  70.             const auto it = node->find_by_weight(weight);
  71.  
  72.             if (it == node->children.end()) {
  73.             	break;
  74.             }
  75.             std::cout << sep << it->first;
  76.             sep = " ";
  77.             node = &it->second;
  78.         }
  79.         std::cout << std::endl;
  80.     }
  81.  
  82.     void print_all() const
  83.     {
  84.         for (int i : root.weights) {
  85.             print(i);   
  86.         }
  87.     }
  88. };
  89.  
  90. int main(int argc, char* argv[]) {
  91.     const std::vector<std::vector<std::string>> sentences = {
  92.         {"My", "name", "is", "John"},
  93.         {"My", "house", "is", "small"},
  94.         {"Hello", "world"},
  95.         {"Hello", "world", "!"}
  96.     };
  97.  
  98.     Trie trie;
  99.     int i = 0;
  100.     for (const auto& sentence : sentences) {
  101.         trie.add(i, sentence);
  102.         ++i;
  103.     }
  104.  
  105.     const std::vector<std::vector<std::string>> queries = {
  106.         {"My", "name", "is", "John"},
  107.         {"My", "house"},
  108.         {"Hello", "world"}
  109.     };
  110.  
  111.     for (const auto& query : queries) {
  112.         std::cout << trie.contains(query) << std::endl;
  113.     }
  114.  
  115.     trie.print_all();
  116. }
  117.  
Success #stdin #stdout 0s 16072KB
comments (?)
stdin 
Standard input is empty
stdout 
1
0
1
My name is John
My house is small
Hello world
Hello world !
https://ideone.com/k3Yew3
language:
C++ (gcc 8.3)
created:
6 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!