#include <iostream>
#include <string>
#include <vector>

using std::string;
using std::vector;

using std::cout; using std::endl;

class WordFilter {
public:
    WordFilter(vector<string>& words) {
        root = new TrieNode();
        for (int i = 0; i < words.size(); i++) {
            string word = words[i];
            int n = word.size();
            for (int j = 0; j < n; j++) {
                string suffix = word.substr(j, n - j);
                insert(suffix + "{" + word, i);
            }
        }
    }

    ~WordFilter() {
        delete root;
    }

    int f(string prefix, string suffix) {
        return find(suffix + "{" + prefix);
    }

private:
    class TrieNode {
    public:
        int index;
        bool is_word;
        vector<TrieNode*> child;

        TrieNode() : index(-1), is_word(false), child(vector<TrieNode*>(27, nullptr)) {}

        ~TrieNode() {
            for (TrieNode* p : child)
                if (p)
                    delete p;
        }
    };

    TrieNode* root;

    void insert(string word, int index) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->child[c - 'a']) node->child[c - 'a'] = new TrieNode();
            node = node->child[c - 'a'];
            node->index = std::max(node->index, index);
        }
        node->is_word = true;
    }

    int find(string word) {
        TrieNode* node = root;
        for (char c : word) {
            node = node->child[c - 'a'];
            if (!node) return -1;
        }
        return node->index;
    }
};

// magic character '{', '{' = 'z' + 1

int main() {
    vector<string> words = {"apple", "abble", "epulo"};
    WordFilter* wf = new WordFilter(words);

    cout << "actual: " << wf->f("a", "e") << ", expected: " << 1 << endl;
    cout << "actual: " << wf->f("a", "ple") << ", expected: " << 0 << endl;
    cout << "actual: " << wf->f("ep", "pulo") << ", expected: " << 2 << endl;
    cout << "actual: " << wf->f("a", "b") << ", expected: " << -1 << endl;

    delete wf;
    return 0;
}