fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct node{
  6. node* pos[26];
  7.  
  8. node(){
  9. for(int j = 0; j < 26; j++)
  10. pos[j] = NULL;
  11. }
  12. };
  13.  
  14. bool add(node* root, string& s, int pos, int n){
  15. if(pos == n-1){
  16. node* curr = root->pos[s[pos] - 'a'];
  17. if(curr) return false;
  18. root->pos[s[pos] - 'a'] = new node;
  19. return true;
  20. }
  21. if(root->pos[s[pos] - 'a']) return add(root->pos[s[pos] - 'a'], s, pos+1, n);
  22. else{
  23. root->pos[s[pos] - 'a'] = new node;
  24. return add(root->pos[s[pos] - 'a'], s, pos+1, n);
  25. }
  26. }
  27.  
  28. map<string, int> m;
  29.  
  30. string at[12];
  31.  
  32. string arr[11][201];
  33.  
  34. int counts[11] = {0};
  35.  
  36. vector<string> ans[11];
  37.  
  38. int cnt = 1;
  39.  
  40. bool cmp(string& s1, string& s2){
  41. return s1.size() > s2.size();
  42. }
  43.  
  44. void build(){
  45. int n;
  46. cin >> n;
  47. while(n--){
  48. string name;
  49. cin >> name;
  50. int pos = 0;
  51. if(m[name]) pos = m[name];
  52. else{ m[name] = cnt; pos = cnt; at[cnt] = name; cnt++; }
  53.  
  54. int num;
  55. cin >> num;
  56. while(num--){
  57. string s;
  58. cin >> s;
  59. arr[pos][counts[pos]++] = s;
  60. }
  61. }
  62.  
  63. for(int j = 1; j < cnt; j++)
  64. sort(arr[j], arr[j] + counts[j], cmp);
  65. }
  66.  
  67. void solve(){
  68. for(int j = 1; j < cnt; j++){
  69. node* root = new node;
  70. for(int k = 0; k < counts[j]; k++)
  71. if(add(root, arr[j][k], 0, arr[j][k].length())) ans[j].push_back(arr[j][k]);
  72. }
  73. }
  74.  
  75. int main(){
  76. build();
  77. cout << "builder complete!\n";
  78. solve();
  79.  
  80. cout << (cnt-1) << endl;
  81. for(int j = 1; j < cnt; j++){
  82. cout << at[j] << " ";
  83. cout << ans[j].size() << " ";
  84. for(int k = 0; k < ans[j].size(); k++)
  85. cout << ans[j][k] << " ";
  86. cout << endl;
  87. }
  88. return 0;
  89. }
  90.  
Runtime error #stdin #stdout 0s 4544KB
stdin
4
ivan 3 123 123 456
ivan 2 456 456
ivan 8 789 3 23 6 56 9 89 2
dasha 2 23 789
stdout
Standard output is empty