Fireworks Rise

主题

00:00:00
Fireworks Rise2023-07-172026-03-05树论数据结构
1088
4.8m
0

一、简单介绍 字典树 ​

  • Trie 树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

  • 它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

二、代码实现 ​

I.字符串转数函数 ​

为了更好地储存字符，我们需要将其转换为数字存入数组里。

这里想必不必多说，能学到这的大佬都会......

注意：此处按题目需求而变化。

代码如下（示例）：

cpp
int getnum(char x){     //字符转数
    if(x>='A'&&x<='Z')
        return x-'A';      //处理大写字母
    else if(x>='a'&&x<='z')
        return x-'a'+26;       //处理小写字母
    else return x-'0'+52;      //处理数字
}

II.插入函数 ​

调入 f 数组，用于标记字符路径是否访问过，如未标记，则需再创建一个基于此字符节点上的子字符节点。

fp,tmp ：当前字符串从头到以当前节点（即以 tmp 对应的字符结尾 序号为 p 的节点）结尾的前缀是否存在过。

cnti ：前缀为该字符串 root 到 i 的子串的次数。

cnt2i ：整个字符串出现的次数。

上插入自定义函数（insert）：

cpp
void insert(string s) {  //插入字符串
	int p=0;
	for(int i=0;i<s.size();i++) {
		int tmp=getnum(s[i]);
		if(!f[p][tmp]) f[p][tmp]=++idx;  //如果不存在则插入
		p=f[p][tmp];      //继续往下查找
		cnt[p]++;       //打标记1
	}
	cnt2[p]++;      //打标记2
}

III.查询函数 ​

经过插入字符串后，便可依次查询字符串，走到对应的点输出维护的值，如以前没有插入过，则直接 return0; 否则查询到字符串尾，返回 cntp ，即该字符串整体与前面字符串的公共前缀的个数，如需记录有插入的字符串中与该字符串完全相同的个数。

cpp
int qurey(string s) {    //查找函数
	int p=0;
	for(int i=0;i<s.size();i++) {
		int tmp=getnum(s[i]);
		if(!f[p][tmp])
			return 0;     //不存在，直接退出返回
		p=f[p][tmp];       //存在继续往下走
	}
	return cnt[p];     //返回次数
}

IV.删除函数 ​

走到字符串对应的点后，用该点维护的值减掉它两个子树维护的值，就可以得到所有字符串 s 的值的和，称为 v，再从这个点走回根，沿途将维护的值减少 v 即可。

cpp
void del(string s){
    int p=0;
    for(int i=0;i<s.size();i++){
        int tmp=s[i]-'0';
        if(!f[p][tmp])
            return;
        p=f[p][tmp];
    }
    int v=cnt[p],vls=0,vrs=0;
    if(f[p][0]) vls=cnt[f[p][0]];
    if(f[p][1]) vrs=cnt[f[p][1]];
    v-=vls+vrs;          //根据前缀和做差 答案等于s这个点减左右子树两个点之和
    if(v==0)  return;
    p=0;
    for(int i=0;i<s.size();i++){
        int tmp=s[i]-'0';
        p=f[p][tmp];
        cnt[p]-=v;
    }
}

IIV.完整代码 ​

Code ​

cpp
#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10;
const int M=100;
int t,n,q,f[N][M],cnt[N],idx;
string s;
int getnum(char x){
    if(x>='A'&&x<='Z')
        return x-'A';
    else if(x>='a'&&x<='z')
        return x-'a'+26;
    else return x-'0'+52;
} 
void reset_() {
	for(int i=0;i<idx;i++) {
		cnt[i]=0;
		for(int j=0;j<M;j++)
			f[i][j]=0;
	}
}
void insert(string s) {
	int p=0;
	for(int i=0;i<s.size();i++) {
		int tmp=getnum(s[i]);
		if(!f[p][tmp]) f[p][tmp]=++idx;
		p=f[p][tmp];
		cnt[p]++;
	}
}
void qurey(string s) {
	int p=0;
	for(int i=0;i<s.size();i++) {
		int tmp=getnum(s[i]);
		if(!f[p][tmp]) {
			printf("0\n");
			return ;
		}
		p=f[p][tmp];
	}
	printf("%d\n",cnt[p]);
	return;
}
int main() {
	scanf("%d",&t);
	while(t--) {
		reset_();
		idx=0;
		scanf("%d%d",&n,&q);
		for(int i=1;i<=n;i++) {
			cin>>s;
			insert(s);
		}
		for(int i=1;i<=q;i++) {
			cin>>s;
			qurey(s);
		}
	}
    return 0;
}

总结 ​

用途： ​

蒟蒻自我总结，可以忽略

有三大种 ：

  • 一、查询字符串是否出现过。

  • 二、寻找该字符串的公共前缀。

  • 三、用于进行 xor（异或）运算。

这是一种时间效率上比较高的树形结构。

题库 ​

刚刚入门可以先浅浅练练，建议可以参考一下我的题单 洛谷【并查集】 ID：970993

最近更新