Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<vector>
- #include<algorithm>
- #include<string>
- #include<map>
- using namespace std;
- int startsWith(const string &s, int i, const string &t, int j)
- {
- if(t.size()-j > s.size()-i)
- return 0;
- for(int ii = j; ii < t.size(); ii++)
- if(s[i+ii-j] != t[ii])
- return 0;
- return t.size()-j;
- }
- int LCP(const string &s, int i, const string &t, int j)
- {
- for(int ii = j; ii < t.size(); ii++)
- if(s[i+ii-j] != t[ii])
- return ii-j;
- return t.size()-j;
- }
- class node
- {
- public:
- map<string, node*> cs;
- bool isend;
- int N;
- node():isend(false), N(0){}
- void add(const string &s, int i)
- {
- N++;
- if(i == s.size())
- {
- isend = true;
- return;
- }
- for(map<string, node*>::iterator it = cs.begin(); it != cs.end(); it++)
- {
- int len = startsWith(s, i, it->first, 0);
- if(len)
- {
- it->second->add(s, i+len);
- return;
- }
- }
- for(map<string, node*>::iterator it = cs.begin(); it != cs.end(); it++)
- {
- int len = LCP(it->first, 0, s, i);
- if(len)
- {
- tmp = it->second;
- node *c = new node();
- c->cs[it->first.substr(len, it->first.size()-len)] = tmp;
- c->N = it->second->N;
- cs.erase(it);
- cs[s.substr(i, len)] = c;
- c->add(s, i+len);
- return;
- }
- }
- cs[s.substr(i, s.size()-i)] = new node();
- cs[s.substr(i, s.size()-i)]->add(s, s.size());
- return;
- }
- void get(string &prefix, int ptr, vector<string> &vs, vector<bool> &ended, int id, int n)
- {
- if(ptr == prefix.size())
- {
- if(isend)
- {
- ended[id] = true;
- id++;
- n--;
- }
- for(map<string, node*>::iterator it = cs.begin(); it != cs.end(); it++)
- {
- int sz = it->second->N;
- for(int j = 0; j < min(sz, n); j++)
- vs[id+j] += it->first;
- it->second->get(prefix, ptr, vs, ended, id, min(sz, n));
- id += min(sz, n);
- n = max(0, n - sz);
- }
- }
- else
- {
- for(map<string, node*>::iterator it = cs.begin(); it != cs.end(); it++)
- {
- if(it->first[0] == prefix[ptr])
- {
- if(prefix.size()-ptr >= it->first.size())
- it->second->get(prefix, ptr+it->first.size(), vs, ended, id, n);
- else
- {
- int len = LCP(it->first, 0, prefix, ptr);
- if(len)
- {
- tmp = it->second;
- node *c = new node();
- c->cs[it->first.substr(len, it->first.size()-len)] = tmp;
- c->N = N;
- cs.erase(it);
- cs[prefix.substr(ptr, prefix.size()-ptr)] = c;
- c->get(prefix, prefix.size(), vs, ended, id, n);
- }
- }
- return;
- }
- }
- }
- }
- } *root, *tmp;
- int main()
- {
- /*
- for(int i = 0; i < 50; i++)
- {
- cout <<"+a";
- for(int j = 0; j < 10; j++)
- cout <<char('a'+rand()%23);
- cout << endl;
- }
- */
- root = new node();
- root->add("sun", 0);
- string s;
- while(cin >> s)
- {
- if(s[0] == '+')
- {
- root->add(string(s.begin()+1, s.end()), 0);
- }
- else
- {
- vector<string> vs(20);
- vector<bool> ed(20);
- int id = 0;
- int n = 20;
- root->get(s, 1, vs, ed, id, n);
- cout << string(s.begin()+1, s.end()) << endl;
- for(int i = 0; i < vs.size(); i++)
- if(ed[i])
- cout << " " << string(s.begin()+1, s.end()) << vs[i] << endl;
- }
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment