fork download
copy 
  1. #include <bits/stdc++.h> 
  2. #include <iostream>
  3. #include <string> 
  4. using namespace std; 
  5.  
  6. class Node {
  7. 	public : 
  8.     char c;
  9.     Node* arr[5];
  10.     int count;
  11.     bool word;
  12. };
  13.  
  14. class TrieDictionary {
  15. 	    public :
  16.     	Node root;
  17.  
  18. 	    void insertWord(string word) {
  19. 	        int i = 0, max = word.length();
  20. 	        Node* walker = &root;
  21. 	        walker -> count += max;
  22. 	        while (i < max) {
  23. 	            char c = word[i];
  24. 	            int index = c - 97;
  25. 	            if (walker -> arr[index] == NULL) {
  26. 	                Node* newnode;
  27. 	                newnode -> c = c;
  28. 	                walker -> arr[index] = newnode;
  29. 	            }
  30. 	            walker = walker -> arr[index];
  31. 	            walker -> count += ((max-1) - i);
  32. 	            if (i == word.length() - 1) {
  33. 	                walker -> word = true;
  34. 	            }
  35. 	            i++;
  36. 	        }
  37. 	    }
  38.  
  39. 	    Node* buildPossibilities(string pattern) {
  40. 	        Node* walker = &root;
  41. 	        int i = 0;
  42. 	        try {
  43. 	            while (i < pattern.length()) {
  44. 	                walker = walker -> arr[pattern.at(i) - 97];
  45. 	                i++;
  46. 	            }
  47. 	        } catch (...) {
  48. 	            return NULL;
  49. 	        }
  50. 	        return walker;
  51. 	    }
  52.  
  53. 	    void asLeftAsPossible(Node* walker, string prefix) {
  54. 	        cout << prefix;
  55. 	        while (true) {
  56. 	            if (walker -> word) {
  57. 	                return;
  58. 	            }
  59. 	            bool m = false;
  60. 	            for (int i = 0; i < 5; i++) {
  61. 	                if (walker -> arr[i] != NULL) {
  62. 	                    cout << walker -> arr[i] -> c;
  63. 	                    walker = walker -> arr[i];
  64. 	                    m = true;
  65. 	                    break;
  66. 	                }
  67. 	                if (m) {
  68. 	                	continue;
  69. 	                }
  70. 	            }
  71. 	            break;
  72. 	        }
  73. 	    }
  74.  
  75. 	    void asRightAsPossible(Node* walker, string prefix) {
  76. 	        cout << prefix;
  77. 	        while (true) {
  78. 	        	bool m = false;
  79. 	            for (int i = 4; i >= 0; i--) {
  80. 	                if (walker -> arr[i] != NULL) {
  81. 	                    cout << walker -> arr[i] -> c;
  82. 	                    walker = walker -> arr[i];
  83. 	                    m = true;
  84. 	                    break;
  85. 	                }
  86. 	                if (m) {
  87. 	                	continue;
  88. 	                }
  89. 	            }
  90. 	            break;
  91. 	        }
  92. 	    }
  93. 	};
  94.  
  95. 	int main()  {
  96. 	    TrieDictionary *trieDictionary = new TrieDictionary;
  97. 	    int N, Q;
  98. 	    cin >> N;
  99. 	    for (int i = 0; i < N; i++) {
  100. 	    	string poem;
  101. 	    	cin >> poem;
  102. 	        trieDictionary -> insertWord(poem);
  103. 	    }
  104.  
  105. 	    cin >> Q;
  106. 	    for (int i = 0; i < Q; i++) {
  107. 	        string prefix;
  108. 	        cin >> prefix;
  109. 	        Node* walker = trieDictionary -> buildPossibilities(prefix);
  110. 	        if (walker == NULL) {
  111. 	            cout << -1 << " \n";
  112. 	            continue;
  113. 	        }
  114. 	        cout << walker -> count;
  115. 	        cout << " ";
  116. 	        trieDictionary -> asLeftAsPossible(walker, prefix);
  117. 	        cout << " ";
  118. 	        trieDictionary -> asRightAsPossible(walker, prefix);
  119. 			cout << "\n";
  120. 	    }
  121. 	    return 0;
  122. }
Runtime error #stdin #stdout 0s 4248KB
comments (?)
stdin
copy 
5
adabc
abcd
abcdea
dceba
abcccaa
2
ab
ea
stdout
copy 
Standard output is empty
https://ideone.com/mNdH2J
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!