字典树（Trie 树）

1. 题目描述#

给定 $n$ 个模式串 $s_1, s_2, \dots, s_n$ 和 $q$ 次询问，每次询问给定一个文本串 $t_i$ ，请回答 $s_1 \sim s_n$ 中有多少个字符串 $s_j$ 满足 $t_i$ 是 $s_j$ 的前缀。

一个字符串 $t$ 是 $s$ 的前缀当且仅当从 $s$ 的末尾删去若干个（可以为 0 个）连续的字符后与 $t$ 相同。

输入的字符串大小敏感。例如，字符串 Fusu 和字符串 fusu 不同。

2. 解析#

对于每一个模式字符串，从第一个字符到最后一个字符建立一棵树，并给路径上的每一个标记点加上 $1$ 。输入检查字符串的时候，顺着树上的匹配路径往下走，一直走到不能再走，如果前面没有匹配的字符串了，说明答案就是 $0$ 。如果结束为止在树的某个节点上，答案就是这个点的标记数目。

3. 代码#

1
#include <bits/stdc++.h>
2
using namespace std;
3
int q,n,m;
4
struct Node{
5
    vector <Node> children;
6
    char val;
7
    int cnt;
8
};
9
int main(){
10
    cin>>q;
11
    while(q--){
12
        cin>>n>>m;
13
        Node formatStr;
14
        for(int i=1;i<=n;i++){
15
            string s;
16
            cin>>s;
17
            // ptr to root
18
            Node *ptr=&formatStr;
19
            for(auto c:s){
20
                bool flag=1;
21
                for(auto &child:ptr->children){
22
                    if(child.val==c){
23
                        child.cnt++;
24
                        ptr=&child;
25
                        flag=0;
26
                        break;
27
                    }
28
                }
29
                if(flag){
30
                    // 说明没有现成的节点
31
                    Node newNode;
32
                    newNode.val=c;
33
                    newNode.cnt=1;
34
                    ptr->children.push_back(newNode);
35
                    ptr=&ptr->children.back();
36
                }
37
            }
38
        }
39
        for(int i=1;i<=m;i++){
40
            string s;
41
            cin>>s;
42
            Node *ptr=&formatStr;
43
            bool flag=1;
44
            int findCnt=0;
45
            for(auto c:s){
46
                for(auto &child:ptr->children){
47
                    if(child.val==c){
48
                        findCnt++;
49
                        ptr=&child;
50
                        flag=0;
51
                        break;
52
                    }
53
                }
54
                if(flag){
55
                    // 说明路走不通了。
56
                    break;
57
                }
58
            }
59
            if(findCnt==s.size()){
60
                cout<<ptr->cnt<<endl;
61
            }else{
62
                cout<<0<<endl;
63
            }
64
        }
65
    }
66
    return 0;
67
}

然而，这样的代码的运行速度不太理想，我们可以进一步优化。

考虑在查找子节点时降到 $log(n)$ 的复杂度，用 $set$ 存子节点，就能便捷地进行二分查找。

1
struct Node{
2
    set <Node> children;
3
    char val;
4
    int cnt;
5
    // 重定义小于号
6
    bool operator < (const Node &rhs) const{
7
        return val<rhs.val;
8
    }
9
};

1. 题目描述#

2. 解析#

3. 代码#

支持与分享

评论区

目录