Trie树傻瓜式入门 + 板子+ 经典例题_字典树板子题

• 前言，本人初学算法，很多东西学的很浅，具体原理请看各位大佬的blog，大佬勿喷

1、什么是Trie树

在计算机科学中，Trie树，称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也即是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常呗搜索引擎系统用于文本词频统计。优点是：最大限度的减少无所谓的字符串比较，查询效率比哈希表高。核心思想是空间换时间。

基本性质

• 1.根节点不包括字符，根节点外每一个节点都包括一个字符。
• 2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
• 3.每个节点的所有子节点包括的字符都不相同。

Trie树的构建

Trie树是一颗存储多个字符串的树。相邻节点间的边代表一个字符，这样数的每条分支代表一个子串，而树的叶子结点则代表完整的字符串。和普通属不同的地方是：相同的字符串前缀共享同一条分支。举一个例子，字典内容如下：
to, te, A, tea, ted, ten, in, inn
具体如下：

Trie的构建不难，把每个字符串依次的插入到Trie中，插入前先看前缀是否存在，如果存在，就共享即可，否则创建对应的节点和边

1、Insert

• 1、首先依次的插入字符串的各个字符，从根节点开始查找
• 2、将字符转化成序列号即 ：s[i] - 'a'
• 3、如果发现该节点的next中没有该序列号，创建新的即可，否则往前走
• 4、重复步骤2,3

2、query

• 1、从更节点开始查找依次的每个字符
• 2、如果发现该节点的next数组中的对应序列号没有赋值，没有次字符串，直接return即可，否则往前继续查找
• 3、找完，返回该节点的 cnt即可

下面是hihoCode上的板子题，可以参考下

题目链接

模板如下

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 10;
char S[maxn];

struct Trie{
    int next[26];
    int cnt;
    void init() {
        cnt = 0;
        memset(next, -1, sizeof next);
    }
}T[maxn];
int le;

void Insert(string s) {
    int p = 0;
    for (int i = 0; i < s.size(); i++) {
        int r = s[i] - 'a';
        if(T[p].next[r] == -1) {
            T[le].init();
            T[p].next[r] = le++;
        }
        p = T[p].next[r];
        T[p].cnt++;

    }
}

void query(string s) {
    int p = 0;
    for (int i = 0; i < s.size(); i++) {
        int r = s[i] - 'a';
        if(T[p].next[r] == -1) {
            cout<<0<<endl;
            return ;
        }
        p = T[p].next[r];
    }
    cout<<T[p].cnt<<endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    int n;cin>>n;
    T[0].init();
    le = 1;
    for (int i = 0; i < n; i++) {
        string s;cin>>s;
        Insert(s);
    }
    int m;cin>>m;
    while (m--) {
        string s;cin>>s;
        query(s);
    }
    return 0;
}
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

其他参考例题如下
HUD 1251 统计难题

参考代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 10;
char S[maxn];

struct Trie{
    int next[27];
    int cnt;
    void init() {
        cnt = 0;
        memset(next, -1, sizeof next);
    }
}T[maxn];
int le;

void Insert(string s) {
    int p = 0;
    for (int i = 0; i < s.size(); i++) {
        int r = s[i] - 'a';
        if(T[p].next[r] == -1) {
            T[le].init();
            T[p].next[r] = le++;
        }
        p = T[p].next[r];
        T[p].cnt++;
    }
}

void query(string s) {
    int p = 0;
    for (int i = 0; i < s.size(); i++) {
        int r = s[i] - 'a';
        if(T[p].next[r] == -1) {
            cout<<0<<endl;
            return ;
        }
        p = T[p].next[r];
    }
    cout<<T[p].cnt<<endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    T[0].init();
    le = 1;
    string s;
    while (getline(cin,s)) {
        if(s.size() == 0) break;
        Insert(s);
    }
    while (getline(cin,s)) {
        query(s);
    }
    return 0;
}
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

HDU 1075 What Are You Talking About

在根节点设上一个标志即可

参考代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 10;

struct Trie {
    int next[26];
    int cnt;
    bool isfail;
    string ss;
    void init() {
        isfail = false;
        cnt = 0;
        memset(next, -1, sizeof next);
    }
}T[maxn];
int le;

void Insert(string s,string t) {
    int p = 0;
    for (int i = 0; i < s.size(); i++) {
        int r = s[i] - 'a';
        if(T[p].next[r] == -1) {
            T[le].init();
            T[p].next[r] = le++;
        }
        p = T[p].next[r];
        T[p].cnt++;
    }
    T[p].ss = t;
    T[p].isfail = true;
}

string query(string s) {
    int p = 0;
    for (int i = 0; i < s.size(); i++) {
        int r = s[i] - 'a';
        if(T[p].next[r] == -1) {
            return s;
        }
        p = T[p].next[r];
    }
    if(T[p].isfail) {
        return T[p].ss;
    } else return s;
}


int main() {
    T[0].init();
    le = 1;
    string s;cin>>s;
    while (cin>>s,s != "END") {
        string t;cin>>t;
        Insert(t,s);
    }
    cin>>s;
    getchar();
    while (getline(cin,s)) {
        if(s == "END") break;
        string t;
        for (int i = 0; i < s.size();i++) {
            if(islower(s[i])) {
                t += s[i];
            } else {
                cout<<query(t);
                cout<<s[i];
                t.clear();
            }
        }
        cout<<endl;
    }
}
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75