Guest User

Untitled

a guest
May 21st, 2018
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.08 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<string>
  5. #include<map>
  6. using namespace std;
  7.  
  8. int startsWith(const string &s, int i, const string &t, int j)
  9. {
  10.     if(t.size()-j > s.size()-i)
  11.         return 0;
  12.     for(int ii = j; ii < t.size(); ii++)
  13.         if(s[i+ii-j] != t[ii])
  14.             return 0;
  15.     return t.size()-j;
  16. }
  17.  
  18. int LCP(const string &s, int i, const string &t, int j)
  19. {
  20.     if(t.size()-j > s.size()-i)
  21.         return 0;
  22.     for(int ii = j; ii < t.size(); ii++)
  23.         if(s[i+ii-j] != t[ii])
  24.             return ii-j;
  25.     return t.size()-j;
  26. }
  27.  
  28. class node
  29. {
  30. public:
  31.     map<string, node*> cs;
  32.     bool isend;
  33.     int N;
  34.     node():isend(false), N(0){}
  35.  
  36.     void add(const string &s, int i)
  37.     {
  38.         N++;
  39.         if(i == s.size())
  40.         {
  41.             isend = true;
  42.             return;
  43.         }
  44.  
  45.         for(map<string, node*>::iterator it = cs.begin(); it != cs.end(); it++)
  46.         {
  47.             int len = startsWith(s, i, it->first, 0);
  48.             if(len)
  49.             {
  50.                 it->second->add(s, i+len);
  51.                 return;
  52.             }
  53.         }
  54.  
  55.         for(map<string, node*>::iterator it = cs.begin(); it != cs.end(); it++)
  56.         {
  57.             int len = LCP(it->first, 0, s, i);
  58.             if(len)
  59.             {
  60.                 tmp = it->second;
  61.                 node *c = new node();
  62.                 c->cs[it->first.substr(len, it->first.size()-len)] = tmp;
  63.                 c->N = it->second->N;
  64.                 cs.erase(it);
  65.                 cs[s.substr(i, len)] = c;
  66.                 c->add(s, i+len);
  67.                 return;
  68.             }
  69.         }
  70.  
  71.         cs[s.substr(i, s.size()-i)] = new node();
  72.         cs[s.substr(i, s.size()-i)]->add(s, s.size());
  73.         return;
  74.     }
  75.  
  76.     void get(string &prefix, int ptr, vector<string> &vs, vector<bool> &ended, int id, int n)
  77.     {
  78.         if(ptr == prefix.size())
  79.         {
  80.             if(isend)
  81.             {
  82.                 ended[id] = true;
  83.                 id++;
  84.                 n--;
  85.             }
  86.             for(map<string, node*>::iterator it = cs.begin(); it != cs.end(); it++)
  87.             {
  88.                 int sz = it->second->N;
  89.                 for(int j = 0; j < min(sz, n); j++)
  90.                     vs[id+j] += it->first;
  91.                 it->second->get(prefix, ptr, vs, ended, id, min(sz, n));
  92.                 id += min(sz, n);
  93.                 n = max(0, n - sz);
  94.             }
  95.         }
  96.         else
  97.         {
  98.            
  99.             for(map<string, node*>::iterator it = cs.begin(); it != cs.end(); it++)
  100.             {
  101.                 if(it->first[0] == prefix[ptr])
  102.                 {
  103.                     if(prefix.size()-ptr >= it->first.size())
  104.                         it->second->get(prefix, ptr+it->first.size(), vs, ended, id, n);
  105.                     else
  106.                     {
  107.                         int len = LCP(it->first, 0, prefix, ptr);
  108.                         if(len)
  109.                         {
  110.                             tmp = it->second;
  111.                             node *c = new node();
  112.                             c->cs[it->first.substr(len, it->first.size()-len)] = tmp;
  113.                             c->N = N;
  114.                             cs.erase(it);
  115.                             cs[prefix.substr(ptr, prefix.size()-ptr)] = c;
  116.                             c->get(prefix, prefix.size(), vs, ended, id, n);
  117.                         }
  118.                     }
  119.                     return;
  120.                 }
  121.             }
  122.         }
  123.     }
  124. } *root, *tmp;
  125.  
  126. int main()
  127. {
  128.     root = new node();
  129.     root->add("sun", 0);
  130.     string s;
  131.     while(cin >> s)
  132.     {
  133.         if(s[0] == '+')
  134.         {
  135.             root->add(string(s.begin()+1, s.end()), 0);
  136.         }
  137.         else
  138.         {
  139.             vector<string> vs(20);
  140.             vector<bool> ed(20);
  141.             int id = 0;
  142.             int n = 20;
  143.             root->get(s, 1, vs, ed, id, n);
  144.  
  145.             cout << string(s.begin()+1, s.end()) << endl;
  146.             for(int i = 0; i < vs.size(); i++)
  147.                 if(ed[i])
  148.                     cout << "  " << string(s.begin()+1, s.end()) << vs[i] << endl;
  149.         }
  150.     }
  151.  
  152.     return 0;
  153. }
Add Comment
Please, Sign In to add comment