Advertisement
trafik

Untitled

Mar 21st, 2022
824
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.93 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 vertex {
  40.     map<char, int> next;
  41.     int leaf;
  42. };
  43.  
  44. string s;
  45. vertex t[MAXN + 1];
  46. int sz;
  47.  
  48. void add(const string& s) {
  49.     int v = 0;
  50.     for (int i = 0; i < len(s); ++i) {
  51.         char c = s[i];
  52.         if (t[v].next[c] == 0) {
  53.             t[v].next[c] = sz++;
  54.         }
  55.         v = t[v].next[c];
  56.     }
  57.     t[v].leaf++;
  58. }
  59. vector<int> c;
  60.  
  61. int curi = 0;
  62. string curstr = "";
  63. void write(vertex v) {
  64.     for (int i = 0; i < v.leaf; ++i) {
  65.         cout << curstr;
  66.         cout << string(c[curi++], '.');
  67.     }
  68.  
  69.     for (int i = 0; i < 26; ++i) {
  70.         char c = ('a' + i);
  71.         if (v.next[c] != 0) {
  72.             curstr.push_back(c);
  73.             write(t[v.next[c]]);
  74.             curstr.pop_back();
  75.         }
  76.     }
  77. }
  78.  
  79.  
  80.  
  81. void solve() {
  82.     /*cin >> s;
  83.     s += '.';
  84.     bool f = 0;
  85.     if (s[0] != '.') f = 1;
  86.     string cur = "";
  87.     for (int i = 0; i < len(s); ++i) {
  88.         if (s[i] == '.' && f) {
  89.             f = 0;
  90.             add(cur);
  91.             cur = "";
  92.         }
  93.         else if (s[i] != '.' && !f) {
  94.             f = 1;
  95.             cur += s[i];
  96.         }
  97.         else if (s[i] != '.' && f) cur += s[i];
  98.     }
  99.     while (s[curi] == '.' && curi < (len(s) - 1)) {
  100.         ans += '.';
  101.         ++curi;
  102.     }
  103.     write();
  104.     while (s[curi] == '.' && curi < (len(s) - 1)) {
  105.         ans += '.';
  106.         ++curi;
  107.     }
  108.     cout << ans;*/
  109.     sz = 1;
  110.     cin >> s;
  111.     string curstr = "";
  112.     int cnt = 0;
  113.     for (int i = 0; i < len(s); ++i) {
  114.         if (s[i] == '.') {
  115.             ++cnt;
  116.             if (curstr.size() > 0) add(curstr);
  117.             //cout << curstr << endl;
  118.             curstr = "";
  119.         } else {
  120.             if (cnt > 0) c.push_back(cnt);
  121.             cnt = 0;
  122.             curstr += s[i];
  123.         }
  124.     }
  125.     if (cnt > 0) c.push_back(cnt);
  126.     if (curstr.size() > 0) {
  127.         add(curstr); //cout << curstr << endl;
  128.     }
  129.     c.push_back(0);
  130.  
  131.     if (s[0] == '.') cout << string(c[curi++], '.');
  132.     write(t[0]);
  133. }
  134.  
  135. int main() {
  136.     ios::sync_with_stdio(false);
  137.     cin.tie(nullptr);
  138.     cout.tie(nullptr);
  139.  
  140.     solve();
  141.  
  142.     return 0;
  143. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement