字典树（Trie树)

飞熊 • 2023年4月9日下午9:18 • 技术随笔 • 阅读 76

🍔Trie树🍔

用处：高效地存储字符串集合的数据结构

概述：就是一个树状结构的存储方式，使用二维数组来存储，其中包含了父结点和子结点，从上向下开始遍历，看是否能够找到对应的结点，从而判断能否找到对应的字符串

存储方法（注意标记结束结点）

图像来源：AcWing 835. Trie字符串统计 – AcWing

下面的结点都是新开辟的结点，u代表字母，来确定结点的具体位置

不知道为什么，这个题在y总的课里面是基础算法，但是在洛谷上却是普及+的

那么下面就先给出两道简单的（可以作为模板使用）

回归正题

题目1

[NOI2000]单词查找树 (nowcoder.com)

代码

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int son[N][26],cnt[N],idx;
void insert(string s)
{
    int p=0;
    for(int i=0;i<s.size();i++)
    {
        int u=s[i]-'A';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;
}
int main()
{
    string s;
    while(cin>>s)
    {
        insert(s);
    }
    cout<<idx+1<<endl;
    return 0;
}

⭐while(cin>>s)

边输入边循环，直到输入到结束符EOF为止

题目2

835. Trie字符串统计 – AcWing题库

代码

#include <iostream>

using namespace std;

const int N = 100010;

int son[N][26], cnt[N], idx;
char str[N];

void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

int query(char *str)//str[]
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        char op[2];
        scanf("%s%s", op, str);
        if (*op == 'I') insert(str);//op[0]
        else printf("%d\n", query(str));
    }

    return 0;
}