Guest User

Untitled

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