Advertisement
Guest User

Untitled

a guest
Nov 17th, 2019
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.96 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <set>
  4. #include <map>
  5. using namespace std;
  6.  
  7. struct Trie {
  8.     map<char,Trie*> next;
  9.     set<string> words;
  10. }root;
  11.  
  12. void find_words(string s) {
  13.     Trie* current = &root;
  14.     cout << s << '\n';
  15.     for (int i = 0; i < s.size(); ++i) {
  16.         if (current->next[s[i]] == NULL)
  17.             return;
  18.         current = current->next[s[i]];
  19.     }
  20.     for (auto i : current->words)
  21.         cout << "  " << i << '\n';
  22. }
  23.  
  24. void add_word(string s) {
  25.     Trie* current = &root;
  26.     for (int i = 0; i < s.size(); ++i) {
  27.         if (current->next[s[i]] == NULL)
  28.             current->next[s[i]] = new Trie();
  29.         current->words.insert(s);
  30.         if (current->words.size() > 20)
  31.             current->words.erase(--(current->words.end()));
  32.         current = current->next[s[i]];
  33.     }
  34.     current->words.insert(s);
  35. }
  36.  
  37. int main() {
  38.     string s;
  39.     add_word("sun");
  40.     while (cin >> s) {
  41.         char comm = s[0];
  42.         s = s.substr(1, s.size() - 1);
  43.         if (comm == '?')
  44.             find_words(s);
  45.         else
  46.             add_word(s);
  47.     }
  48.     return 0;
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement