LeetCode第 1032 题：字符流(C++)_leetcode 1032

1032. 字符流 - 力扣（LeetCode）

困难题，字典树或者ac自动机，注意是字符流，字符是一个个添加进来的，所以之前的状态也很重要，需要保存前一个字符匹配的结点，当前字符从这个结点开始匹配。

ac自动机

没有优化（实在写不下去了），基本就是模板思路。

数据结构与算法之美：36 | AC自动机：如何用多模式串匹配实现敏感词过滤功能

class StreamChecker {
public:
    struct acNode{
        bool isEnd = false;
        acNode* next[26] = {NULL};
        acNode* fail = NULL; //失败指针
    };
    StreamChecker(vector<string>& words) : root(new acNode()){
        for(const auto& word : words){
            auto p = root;
            for(int i = 0; i < word.size(); ++i){
                int idx = word[i] - 'a';
                if(p->next[idx] == NULL)    p->next[idx] = new acNode();
                p = p->next[idx];
            }
            p->isEnd = true;
        }
        buildFailPoint();//创建失败指针
        beg = root; //检索的起始节点是root
    }

    void buildFailPoint(){
        queue<acNode*> my_q;//BFS
        my_q.push(root);
        while(!my_q.empty()){//层次遍历，root在第一层
            auto p = my_q.front();my_q.pop();
            for(int i = 0; i < 26; ++i){
                auto pc = p->next[i];
                if(pc == NULL)  continue;//不需要fail指针
                if(p == root) pc->fail = root;//pc在第二层，fail指针只能指向root
                else{//
                    auto    q = p->fail;
                    while(q != NULL && q->next[i] == NULL)//p的失败指针在对应字符位置没有值，说明没有匹配到该字符
                        q = q->fail;//再寻找q的失败指针
                    if(q == NULL)   pc->fail = root;//q没有失败指针（默认即为NULL），就只能指向root
                    else pc->fail = q->next[i];
                }
                my_q.push(pc);
            }
        }
    }
    
    bool query(char letter) {
        int idx = letter - 'a';
        while(beg != root && beg->next[idx] == NULL)//失配
            beg = beg->fail;// 失败指针发挥作用的地方
        beg = beg->next[idx];
        if(beg == NULL) beg = root;// 没有匹配成功，从root开始重新匹配
        else{
            auto tmp = beg;
            while(tmp != root){
                if(tmp->isEnd)  return true;
                tmp = tmp->fail;
            }
        }
        return false;
    }
private:
    acNode *root;
    acNode *beg; //检索的起始节点
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

另外这题是没有必要用ac自动机的，我这么用纯粹是自己想练一下手。这个题简单使用字典树或者哈希表或许也能解。

字典树

翻转单词并建立字典树（后缀树），常用技巧了，剩下的都是字典树典型操作了：

class StreamChecker {
public:
    struct TrieNode{
        bool isEnd = false;
        TrieNode* next[26] = {NULL};
    };
    StreamChecker(vector<string>& words) : root(new TrieNode()), s(""){
        for(const auto& word : words){
            auto p = root;
            for(int i = word.size()-1; i >= 0; --i){//逆序
                int idx = word[i] - 'a';
                if(p->next[idx] == NULL)    p->next[idx] = new TrieNode();
                p = p->next[idx];
            }
            p->isEnd = true;
        }
    }
    
    bool query(char letter) {
        s += letter;
        auto p = root;
        for(int i = s.size()-1; i >= 0; --i){
            int idx = s[i] - 'a';
            if(p->next[idx] == NULL)    return false;
            p = p->next[idx];
            if(p->isEnd)    return true;
        }
        return false;
    }
private:
    TrieNode *root;
    string s;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

由于单词的最后一个字符可能是相同的，所以以最后一个字符建立哈希表的思路其实并不好，因为需要使用multimap，匹配的过程虽然思路直接，但是同key的元素过多的时候，还是需要一一对比，至少也需要二分查找。