trafik

Untitled

Mar 21st, 2022
830
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.26 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <set>
  5. #include <deque>
  6. #include <queue>
  7. #include <algorithm>
  8. #include <stack>
  9. #include <map>
  10. #include <string>
  11. #include <iomanip>
  12. #include <fstream>
  13. #include <unordered_map>
  14. #define all(v) v.begin(), v.end()
  15. #define ll long long
  16. #define ld long double
  17. #define lb lower_bound
  18. #define ub upper_bound
  19. #define len(v) (ll)v.size()
  20. #define last(v) (ll)v[len(v) - 1]
  21. using namespace std;
  22. const ll inf = 1e9;
  23. const ll MAXN = 1e6 + 1;
  24. const ll MAXM = 1e5 + 1;
  25. const int logn = 29;
  26. template<class T>
  27. istream& operator>>(istream& in, vector<T>& a) {
  28.     for (auto& i : a)
  29.         in >> i;
  30.     return in;
  31. }
  32. template<class T>
  33. ostream& operator<<(ostream& out, vector<T>& a) {
  34.     for (auto& i : a)
  35.         out << i << " ";
  36.     return out;
  37. }
  38.  
  39. struct node {
  40.     node* next[26];
  41.     short int strings;
  42.     node() {
  43.         for (int i = 0; i < 26; i++) {
  44.             next[i] = nullptr;
  45.         }
  46.         strings = 0;
  47.     }
  48. };
  49.  
  50. node* root = new node();
  51. void add(string s) {
  52.     node* curv = root;
  53.     for (int i = 0; i < len(s); ++i) {
  54.         char c = s[i];
  55.         if (curv->next[c - 'a'] == nullptr) {
  56.             curv->next[c - 'a'] = new node();
  57.         }
  58.         curv = curv->next[c - 'a'];
  59.     }
  60.     curv->strings++;
  61. }
  62.  
  63. vector<int> c;
  64.  
  65. string s;
  66. string ans = "";
  67. string cur_str = "";
  68. int curi = 0;
  69. void write(node* v = root) {
  70.     for (int i = 0; i < v->strings; i++) {
  71.         /*while (s[curi] == '.') {
  72.             ans += '.';
  73.             ++curi;
  74.         }
  75.         ans += cur_str;
  76.         while (s[curi] != '.') ++curi;*/
  77.         cout << cur_str;
  78.         cout << string(c[curi], '.');
  79.         curi++;
  80.     }
  81.  
  82.     for (int i = 0; i < 26; i++) {
  83.         if (v->next[i] != nullptr) {
  84.             cur_str.push_back('a' + i);
  85.             write(v->next[i]);
  86.             cur_str.pop_back();
  87.         }
  88.     }
  89. }
  90.  
  91.  
  92.  
  93. void solve() {
  94.     /*cin >> s;
  95.     s += '.';
  96.     bool f = 0;
  97.     if (s[0] != '.') f = 1;
  98.     string cur = "";
  99.     for (int i = 0; i < len(s); ++i) {
  100.         if (s[i] == '.' && f) {
  101.             f = 0;
  102.             add(cur);
  103.             cur = "";
  104.         }
  105.         else if (s[i] != '.' && !f) {
  106.             f = 1;
  107.             cur += s[i];
  108.         }
  109.         else if (s[i] != '.' && f) cur += s[i];
  110.     }
  111.     while (s[curi] == '.' && curi < (len(s) - 1)) {
  112.         ans += '.';
  113.         ++curi;
  114.     }
  115.     write();
  116.     while (s[curi] == '.' && curi < (len(s) - 1)) {
  117.         ans += '.';
  118.         ++curi;
  119.     }
  120.     cout << ans;*/
  121.  
  122.     cin >> s;
  123.     string curstr = "";
  124.     int cnt = 0;
  125.     for (int i = 0; i < len(s); ++i) {
  126.         if (s[i] == '.') {
  127.             ++cnt;
  128.             if (curstr.size() > 0) add(curstr);
  129.             //cout << curstr << endl;
  130.             curstr = "";
  131.         } else {
  132.             if (cnt > 0) c.push_back(cnt);
  133.             cnt = 0;
  134.             curstr += s[i];
  135.         }
  136.     }
  137.     if (cnt > 0) c.push_back(cnt);
  138.     if (curstr.size() > 0) {
  139.         add(curstr); //cout << curstr << endl;
  140.     }
  141.     c.push_back(0);
  142.  
  143.     if (s[0] == '.') cout << string(c[curi++], '.');
  144.     write();
  145. }
  146.  
  147. int main() {
  148.     ios::sync_with_stdio(false);
  149.     cin.tie(nullptr);
  150.     cout.tie(nullptr);
  151.  
  152.     solve();
  153.  
  154.     return 0;
  155. };
Advertisement
Add Comment
Please, Sign In to add comment