#include <bits/stdc++.h>
using namespace std;
class Trie {
private:
static const int chars = 26;
Trie* child[chars];
bool isLeaf{};
public:
Trie() {
memset(child, 0, sizeof(child));
}
~Trie() {
for (int i = 0; i < chars; i++) {
if (child[i]) {
delete child[i];
}
}
}
void insert(const string& s, int idx = 0) {
if (idx == s.length()) {
isLeaf = true;
} else {
int cur = s[idx] - 'a';
if (child[cur] == nullptr) {
child[cur] = new Trie();
}
child[cur]->insert(s, idx + 1);
}
}
bool wordExists(const string& s, int idx = 0) const {
if (idx == s.size()) return isLeaf;
int cur = s[idx] - 'a';
if (!child[cur]) return false;
return child[cur]->wordExists(s, idx + 1);
}
bool prefixExists(const string& s, int idx = 0) const {
if (idx == s.size()) return true;
int cur = s[idx] - 'a';
if (!child[cur]) return false;
return child[cur]->prefixExists(s, idx + 1);
}
bool SuffixExists(const string& s ) {
for(int i = 0; i < s.length();i++){
if(wordExists(s.substr(i))){
return true;
}
}
return false;
}
//Problem 1:
void getAllstrings(vector<string>& res, string s = "") {
if (isLeaf) {
res.push_back(s);
}
for (int i = 0; i < 26; i++) {
if (child[i]) {
child[i]->getAllstrings(res, s + char(i + 'a'));
}
}
}
//Problem 2:
void autoComplete(string s){
vector<string>allWords;
getAllstrings(allWords);
for(auto word: allWords){
if(word.substr(0, s.length()) == s){
cout<<word<<endl;
}
}
}
//Problem 3 :
bool findModifiedWord(string s) {
for (int i = 0; i < s.length(); i++) {
char original = s[i];
for (char j = 'a'; j <= 'z'; j++) {
if (j != original) {
s[i] = j;
if (wordExists(s)) {
return true;
}
}
}
s[i] = original;
}
return false;
}
};
int main() {
string s; cin >> s;
Trie tree;
tree.insert("abcd");
tree.insert("ab");
tree.insert("abx");
tree.insert("abyz");
tree.insert("xyz");
tree.insert("a");
tree.insert("bcd");
vector<string> res;
tree.getAllstrings(res);
cout <<"all strings in the trie\n";
for(auto s: res){
cout<<s<<endl;
}
cout <<"--------------------------------\n";
cout <<"auto complete of ab\n";
tree.autoComplete("ab");
cout <<"--------------------------------\n";
cout << boolalpha <<tree.findModifiedWord("bcy") <<endl;
cout << boolalpha <<tree.findModifiedWord("abyx") <<endl;
cout << boolalpha <<tree.findModifiedWord("manar") <<endl;
return 0;
}