Advertisement
pasholnahuy

Макс и хранение слов

Sep 29th, 2023
1,022
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.82 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <unordered_map>
  4.  
  5. using namespace std;
  6.  
  7. class Trie{
  8.     struct Node {
  9.         unordered_map<char, Node> next;
  10.         int isTerminal = 0;
  11.         bool visited = false;
  12.     }
  13.             root;
  14.  
  15. public:
  16.     int symb_cnt = 0;
  17.     void Insert(const string& s) {
  18.         Node* cur = &root;
  19.         for (auto c: s) {
  20.             cur = &cur->next[c];
  21.             if (!cur->visited){
  22.                 ++symb_cnt;
  23.                 cur->visited = true;
  24.             }
  25.         }
  26.         ++cur->isTerminal;
  27.     }
  28.  
  29.  
  30. };
  31.  
  32. int main() {
  33.     int n;
  34.     cin >> n;
  35.     Trie trie;
  36.     int summ = 0;
  37.     for (int i = 0; i < n; ++i){
  38.         string s;
  39.         cin >> s;
  40.         summ += s.size();
  41.         trie.Insert(s);
  42.     }
  43.     cout << summ - trie.symb_cnt;
  44.     return 0;
  45. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement