题目描述

按下述要求实现 StreamChecker 类：

• StreamChecker(words)：构造函数，用给定的字词初始化数据结构。
• query(letter)：如果存在某些 k >= 1，可以用查询的最后 k 个字符（按从旧到新顺序，包括刚刚查询的字母）拼写出给定字词表中的某一字词时，返回 true。否则，返回 false。

样例

StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // 初始化字典
streamChecker.query('a');          // 返回 false
streamChecker.query('b');          // 返回 false
streamChecker.query('c');          // 返回 false
streamChecker.query('d');          // 返回 true，因为 'cd' 在字词表中
streamChecker.query('e');          // 返回 false
streamChecker.query('f');          // 返回 true，因为 'f' 在字词表中
streamChecker.query('g');          // 返回 false
streamChecker.query('h');          // 返回 false
streamChecker.query('i');          // 返回 false
streamChecker.query('j');          // 返回 false
streamChecker.query('k');          // 返回 false
streamChecker.query('l');          // 返回 true，因为 'kl' 在字词表中。

注意

• 1 <= words.length <= 2000
• 1 <= words[i].length <= 2000
• 字词只包含小写英文字母。
• 待查项只包含小写英文字母。
• 待查项最多 40000 个。

算法

(AC 自动机) $O(N + Q)$

1. AC 自动机模板题，这里只简要说明一下 AC 自动机的思想。
2. 首先根据所有的模式串构建 Trie （字典）树，然后通过宽度优先遍历在 Trie 树上构建失败指针，即如果当前边匹配失败，该回到哪里重新匹配。这里的思想类似于 KMP 的思想。
3. 这里需要注意的是，在宽度优先遍历的过程中，需要将 Trie 树中，标记为是单词终点的结点通过失败指针进行继承。

时间复杂度

• 假设 N 为字典树中的结点个数，Q 为总的询问长度，时间复杂度为 $O(N + Q)$。

空间复杂度

• 需要存储字典树，故空间复杂度为 $O(N)$。

C++ 代码

struct Node {
    Node *nxt[26], *fail;
    bool is_word;
    Node() {
        memset(nxt, NULL, sizeof(nxt));
        fail = NULL;
        is_word = false;
    }
};

class StreamChecker {
public:
    Node *root, *now;

    StreamChecker(vector<string>& words) {
        root = new Node();
        for (auto &word : words)
            insert(word);

        build();
        now = root;
    }

    void insert(string &word) {
        Node *p = root;
        for (auto &c : word) {
            if (p -> nxt[c - 'a'] == NULL)
                p -> nxt[c - 'a'] = new Node();
            p = p -> nxt[c - 'a'];
        }
        p -> is_word = true;
    }

    void build() {
        queue<Node*> q;
        q.push(root);
        while (!q.empty()) {
            Node *sta = q.front();
            q.pop();
            for (int i = 0; i < 26; i++)
                if (sta -> nxt[i] != NULL) {
                    Node *f = sta -> fail;
                    while (f != NULL && f -> nxt[i] == NULL)
                        f = f -> fail;

                    if (f != NULL) {
                        sta -> nxt[i] -> fail = f -> nxt[i];
                        // 通过失败指针进行继承
                        sta -> nxt[i] -> is_word |= f -> nxt[i] -> is_word;
                    }
                    else
                        sta -> nxt[i] -> fail = root;
                    q.push(sta -> nxt[i]);
                }
        }
        root -> fail = root;
    }

    bool query(char letter) {
        while (now != root && now -> nxt[letter - 'a'] == NULL)
            now = now -> fail;
        if (now -> nxt[letter - 'a'])
            now = now -> nxt[letter - 'a'];

        return now -> is_word;
    }
};

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