Trie

Trie 是一个用树来存储字符串的结构。

基本操作

  • 插入一个字符串
  • 查找一个字符串是否在树中
  • 维护对应字符串的附加信息(如个数之类的)

模板

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
const int maxnode = maxn * 50;
const int sigma_size = 26;

#define c ((ch)-'a')
int child[maxnode][sigma_size], val[maxnode];
int sz, n;

void insert(string s) {
    int u = 0; // 从根节点 u = 0 开始插入
    for (char ch : s) {
        if(!child[u][c]) { // 如果是空节点
            child[u][c] = ++sz;
        }
        u = child[u][c]; // 沿着树走
    }
    val[u] = 1; // 当前字符串节点对于的信息
}

int finds(string s) {
    int u = 0;
    for (char ch : s) {
        if (!child[u][c]) return 0; // 找失败
        u = child[u][c];
    }
    if (val[u] >= 1) val[u]++;
    return val[u];
}

int main() {
    cin >> n;
    for (int i = 1;i <= n; ++i) {
        string str; cin >> str;
        insert(str);
    }
    cin >> n;
    for (int i = 1;i <= n; ++i) {
        string str; cin >> str;
        int v = finds(str);
        if (v == 0) cout << "WRONG" << endl;
        else if (v >= 3) cout << "REPEAT" << endl;
        else cout << "OK" << endl;
    }
    return 0;
}

基础应用

字符串插入，查找

判断字符串前缀

可以用 \(is\_end[u]\) 节点 \(u\) 是否是末尾， \(haschil[u]\) 节点 \(u\) 下面有没有字符串。如果插入一个单词的过程中，没有其他单词，且插入完成后，后面没有孩子。就可以断定它不是前缀.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int n, ok, child[maxn][10], T, sz, haschild[maxn], is_end[maxn];

#define c (ch-'0')

void insert(string s) {
    int u = 0;
    for (char ch : s) {
        if (!child[u][c]) {
            haschild[u] = 1;
            child[u][c] = ++sz;
        }
        u = child[u][c];
        if (is_end[u]) ok = 0;
    }
    if (haschild[u]) ok = 0;
    is_end[u] = 1;
}

进阶应用

01Trie