Guest User

Untitled

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