#include <bits/stdc++.h>
using namespace std;

class Trie {
private:
    static const int chars = 26;
    Trie* child[chars];
    bool isLeaf{};

public:
    vector<string>allwords;
    Trie() {
        memset(child, 0, sizeof(child));
    }
    ~Trie() {
        for (int i = 0; i < chars; i++) {
            if (child[i]) {
                delete child[i];
            }
        }
    }
    //Problem 1 : a
    void insert(string s) {
        Trie* current = this;
        for (char c : s) {
            int index = c - 'a';
            if (!current->child[index]) {
                current->child[index] = new Trie();
            }
            current = current->child[index];
        }
        allwords.push_back(s);
        current->isLeaf = true;
    }
    //Problem 1 : b
    bool word_exists(string s) {
        Trie* current = this;
        for (char c : s) {
            int index = c - 'a';
            if (!current->child[index]) {
                return false;
            }
            current = current->child[index];
        }
        return current->isLeaf;
    }
    //Problem 2 : minimal prefix
    string first_word_prefix(const string &str){
        vector<string>all;
        Trie* current = this;
        string prefix = "";
        for (char c : str) {
            int index = c - 'a';
            if (!current->child[index]) break; 
            prefix += c;
            current = current->child[index];
            if (current->isLeaf) all.push_back(prefix);
        }
        if(all.empty()){
            return str;
        }
        return *min_element(all.begin(), all.end());
    }
    //Problem 3 : Is suffix
    void SuffixExists(const string& s) {
        for(auto word : allwords){
            vector<string>allsuffixes;
            for(int i = 0; i <(int) word.size(); i++){
                allsuffixes.push_back(word.substr(i));
            }
            for(auto w: allsuffixes){
                if(w == s){
                    cout << "yes it is found \n";
                    return;
                }
            }
        }
        cout << "No suffix found" << endl;
    }
};

//Problem 4 and 5:
class Trie3 {
private:
    //static const int size =256;
    unordered_map<string, Trie3*> child;
    bool isLeaf;

public:
    Trie3() : isLeaf(false) {}

    ~Trie3() {
        for (auto &entry : child) {
            delete entry.second;
        }
    }

    void insert(const vector<string>& path) {
        Trie3* current = this;
        for (const auto& word : path) {
            if (current->child.find(word) == current->child.end()) {
                current->child[word] = new Trie3();
            }
            current = current->child[word];
        }
        current->isLeaf = true; 
    }

    bool subpath_exists(const vector<string>& path) {
        Trie3* current = this;
        for (const auto& word : path) {
            if (current->child.find(word) == current->child.end()) {
                //first change than insert
                return false;
            }
            current = current->child[word];
        }
        //second change than insert
        return true;  
    }
};
int main() {
    string s;cin >> s;
    Trie trie;
    trie.insert("hello");
    trie.insert("manar");
    trie.insert("man");
    trie.insert("elhabbal");
    trie.insert("xyz");
    trie.insert("xyzea");
    trie.insert("a");
    trie.insert("bc");

    trie.SuffixExists("habbal");
    trie.SuffixExists("nar");
    trie.SuffixExists("lo");
    trie.SuffixExists("gold");
    cout <<"--------------------------------\n";
    cout << trie.first_word_prefix("x")<<endl;
    cout << trie.first_word_prefix("xyzabc")<<endl;
    cout << trie.first_word_prefix("manarelhabbal")<<endl;
    cout <<"--------------------------------\n";
    Trie3 trie3;
    vector<string> path1 = {"home","software","eclipse"};
    vector<string> path2 = {"home","software","eclipse","bin"};
    vector<string> path3 = {"home","installed","gnu"};
    vector<string> path4 = {"user","mostafa","temp"};
    trie3.insert(path1);
    trie3.insert(path2);
    trie3.insert(path3);
    trie3.insert(path4);
    vector<string>f1={"user","mostafa","temp"};
    vector<string>f2={"user","mostafa"};
    vector<string>f3={"user","mos"};
    vector<string>f4={"user","mostafa","private"};
    cout << trie3.subpath_exists(f1) << endl;
    cout << trie3.subpath_exists(f2) << endl;
    cout << trie3.subpath_exists(f3) << endl;
    cout << trie3.subpath_exists(f4) << endl;
    cout <<"--------------------------------\n";
    return 0;
}