1032. Stream of Characters

trie
因为是最后k个字母，所以是suffix tree

class StreamChecker {
public:
    StreamChecker(vector<string>& words) : root(new TrieNode) {
        for (const auto &w : words) {
            add(w);
        }
    }

    bool query(char letter) {
        data += letter;
        return search(data);
    }

    struct TrieNode {
        TrieNode *children[26] = {nullptr};
        bool isEnd = false;
    };

    void add(const string &s) {
        auto p = root;
        for (auto rit = rbegin(s); rit != rend(s); ++rit) {
            int k = *rit - 'a';
            if (!p->children[k]) {
                p->children[k] = new TrieNode;
            }
            p = p->children[k];
        }
        p->isEnd = true;
    }

    bool search(const string &s) {
        auto p = root;
        for (auto rit = rbegin(s); rit != rend(s); ++rit) {
            int k = *rit - 'a';
            if (p->isEnd) return true;
            if (!p->children[k]) return false;
            p = p->children[k];
        }
        return p->isEnd;
    }

    string data;
    TrieNode *root;
};

/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker* obj = new StreamChecker(words);
 * bool param_1 = obj->query(letter);
 */