Trie树-字典树笔记

Trie树-字典树笔记

Trie树（字典树）是一种用于存储字符串的高效数据结构，特别适用于处理大量字符串的前缀匹配和查找问题。通过将字符串的公共前缀合并存储，Trie树能够在较低的时间复杂度内完成字符串的插入和查找操作。本文将详细介绍Trie树的基本原理，并通过代码示例展示其具体实现方法。

Trie树是一种高效的存储字符串的数据结构，它将多个字符串的前缀合并在一条边上，每次插入时，都判断当前的树上有无能够重合的前缀，如果没有就单独增加一个节点。通过合并前缀，可以做到快速查找已经优化空间的操作。

下面是使用数组模拟实现Trie树的部分代码：

我们首先定义一个二维数组来构造一个树结构

int tree[N][M];//N表示该树最多有几个节点，M表示每个节点最多伸出多少个枝，即最多有多少个儿子
int idx;//定义编号指针
int cnt[N];//定义计数数组，表示第N个节点到根节点的路径构成的字符串被插入了多少次

转换字符操作：将字符转换为整数，作为树的枝（以字母和数字为例）

int trans(char x) {
    if (x >= 'A' && x <= 'Z') return x - 'A';//映射大写字母到 0~25
    if (x >= 'a' && x <= 'z') return x - 'a' + 26;//映射小写字母到 26~51
    if (x >= '0' && x <= '9') return x - '0' + 52;//映射数字到 52~61
}

插入字符串操作：

void insert(char str[]) {//插入str这个字符串
    int p = 0, len = strlen(str);//从根节点出发
    for (int i = 0; i < len; i++) {//遍历字符串
        int c = trans(str[i]);//转换字符映射到整数
        if (!tree[p][c])//如果当前节点不存在 c 这个儿子（树枝）
            tree[p][c] = ++idx;//创建这个枝，然后给予编号
        p = tree[p][c];//走到这个节点
        cnt[p]++;//当前p节点到根节点的路径构成的字符串被插入次数加1
    }
}

查找字符串操作：（也可以查找前缀）

int find(char str[]) {
    int p = 0, len = strlen(str);//从根节点开始查找
    for (int i = 0; i < len; i++) {
        int c = trans(str[i]);
        if (!tree[p][c])//如果当前节点不存在 c 这个儿子
            return 0;//返回0，没有找到匹配的浅醉
        p = tree[p][c];//存在 c 这个儿子，那么就走到 c 这个儿子节点上
    }
    return cnt[p];//遍历完需要查找的字符串，返回最后一个字符对应的插入的次数
}

以洛谷P8306为例：

#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
int n, q, idx;
char s[3000010];
int tree[3000010][65], cnt[3000010];
int trans(char x) {
    if (x >= 'A' && x <= 'Z') return x - 'A';
    if (x >= 'a' && x <= 'z') return x - 'a' + 26;
    if (x >= '0' && x <= '9') return x - '0' + 52;
}
void insert(char str[]) {
    int p = 0, len = strlen(str);
    for (int i = 0; i < len; i++) {
        int c = trans(str[i]);
        if (!tree[p][c])
            tree[p][c] = ++idx;
        p = tree[p][c];
        cnt[p]++;
    }
}
int find(char str[]) {
    int p = 0, len = strlen(str);
    for (int i = 0; i < len; i++) {
        int c = trans(str[i]);
        if (!tree[p][c])
            return 0;
        p = tree[p][c];
    }
    return cnt[p];
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
    
        for (int i = 0; i <= idx; i++)
            for (int j = 0; j <= 64; j++)
                tree[i][j] = 0;
        for (int i = 0; i <= idx; i++)
            cnt[i] == 0;
        idx = 0;//做完一轮测试后，重新初始化tree
        
        scanf("%d %d", &n, &q);
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            insert(s);
        }
        for (int i = 0; i < q; i++) {
            scanf("%s", s);
            printf("%d\n", find(s));
        }
    }
    return 0;
}