fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. char ans[33];
  4. struct trie {
  5. 	trie *next[26];
  6. 	bool leaf;
  7. 	trie() {
  8. 		memset(next, 0, sizeof next);
  9. 		leaf = 0;
  10. 	}
  11. 	void add(char *s) {
  12. 		if (*s == 0) {
  13. 			leaf = 1;
  14. 			return;
  15. 		}
  16. 		int c = *s - 'a';
  17. 		if (!next[c])
  18. 			next[c] = new trie();
  19. 		next[c]->add(s + 1);
  20. 	}
  21. 	int solve(char *s, bool f) {
  22. 		if (f) {
  23. 			int i;
  24. 			for (i = 0; i < 26 && next[i] == 0; ++i)
  25. 				;
  26. 			if (i == 26)
  27. 				return 0;
  28. 			if (leaf)
  29. 				return 0;
  30. 			next[i]->solve(s, 1);
  31. 			cout << char(i + 'a');
  32. 			return 0;
  33. 		}
  34. 		if (*s == 0) {
  35. 			int i;
  36. 			for (i = 0; i < 26 && next[i] == 0; ++i)
  37. 				;
  38. 			if (i == 26) {
  39. 				return -1;
  40. 			}
  41. 			next[i]->solve(s, 1);
  42. 			cout << char(i + 'a');
  43. 			return 0;
  44. 		}
  45. 		int c = *s - 'a', ret = -1, i;
  46. 		if (next[c] != 0)
  47. 			ret = next[c]->solve(s + 1, 0);
  48. 		if (ret == 0) {
  49. 			cout << *s;
  50. 			return 0;
  51. 		}
  52. 		for (i = 0; i < 26; ++i) {
  53. 			if (i != c && next[i])
  54. 				break;
  55. 		}
  56. 		if (i == 26)
  57. 			return leaf ? 0 : -1;
  58. 		ret = next[i]->solve(s, 1);
  59. 		if (ret == -1)
  60. 			return -1;
  61. 		cout << char(i + 'a');
  62. 		return 0;
  63. 	}
  64. };
  65. int main(int argc, char **argv) {
  66. #ifndef ONLINE_JUDGE
  67. 	freopen("a.in", "r", stdin);
  68. #endif
  69. 	char s[33];
  70. 	trie root;
  71. 	while (1) {
  72. 		gets(s);
  73. 		int ln = strlen(s);
  74. 		if (!ln)
  75. 			break;
  76. 		reverse(s, s + ln);
  77. 		root.add(s);
  78. 	}
  79. 	while (cin >> s) {
  80. 		int ln = strlen(s);
  81. 		reverse(s, s + ln);
  82. 		root.solve(s, 0);
  83. 		cout << endl;
  84. 	}
  85. 	return 0;
  86. }
  87.  
Success #stdin #stdout 0s 3144KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SVZAbO
language:
C++ (gcc 8.3)
created:
9 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!