首页 > 其他分享 >字典树

字典树

时间:2024-04-21 15:11:25浏览次数:25  
标签:里查 int char && 3000005 字典

字典树所有功能
1、在字典里查一个串
2、在字典里查含有该前缀的串的个数
3、

//放外面就是查整体
//放里头就是查外面 

#include<bits/stdc++.h>
using namespace std;
int T,q,n,t[3000005][65],cnt[3000005],idx;
char s[3000005];
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 insert(char str[]){
    int p=0,len=strlen(str);
    for(int i=0;i<len;i++){
        int c=getnum(str[i]);
        if(!t[p][c])
            t[p][c]=++idx;
        p=t[p][c];
        cnt[p]++;
		//放外面就是搜整体
		//放里头就是查前缀
    }
    //cnt[p]++;
    
}
int find(char str[]){
    int p=0,len=strlen(str);
    for(int i=0;i<len;i++){
        int c=getnum(str[i]);
        if(!t[p][c])
            return 0;
        p=t[p][c];
    }
    return cnt[p];
}



int main(){
    scanf("%d",&T);
    while(T--){
        for(int i=0;i<=idx;i++)
            for(int j=0;j<=122;j++)
                t[i][j]=0;
        for(int i=0;i<=idx;i++)
            cnt[i]=0;
        idx=0;
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++){
            scanf("%s",s);
            insert(s);
        }
        for(int i=1;i<=q;i++){
            scanf("%s",s);
            printf("%d\n",find(s));
        }
    }




//int n;
//	scanf("%d",&n); // getchar();
//	while(n--){
//		char op[2];
//		scanf("%s%s",op,s);
//		if(*op=='I') insert(s);
//		else cout<<find(s)<<endl;
//	}

    return 0;
}

标签:里查,int,char,&&,3000005,字典
From: https://www.cnblogs.com/yzzyang/p/18148965

相关文章

  • 字典树
    简介字典树是一种用来维护多个字符串的前缀的数据结构,时空复杂度均为\(O(\sum|S|)\)。字典树是一颗外向树(边从父亲连向儿子),每条边的边权都为一个字符,一个结点对应的字符串为从根节点到当前结点的边的字符组成的字符串。比如,当\(N=5\),\(S_1,S_2,\dots,S_5\)分别为ak、aoi、......
  • 异常捕获列表字典推导式
    【一】什么是异常异常是程序运行时可能发生的错误或意外情况。在Python中,异常是一种对象,表示程序执行期间发生的错误。当出现异常时,程序的正常流程会被中断,而是跳转到异常处理流程。【二】异常分类在Python中,异常分为两类:内建异常(Built-inExceptions):由Python内部定义的......
  • python-字典的学习
    '''在Python中,字典字是一系列键—值对值。每个键都与一个值相关联,你可以使用键来访问与之相关联的值。与键相关联的值可以是数字、字符串、列表乃至字典。事实上,可将任何Python对象用作字典中的值。在Python中,字典用放在花括号{}中的一系列键—值对表示'''customer={'name......
  • 针对列表中的字典去重
    背景:我有一个列表,列表中存储的子元素是字典,字典中存在多个键值对,其中id是绝对不相同的,但其他键值对可能和另外的子元素重复,现在要去除重复的子元素#原始列表original_list=[{"id":1,"name":"Alice","age":20},{"id":2,"name":"Bob","age&q......
  • python基础-数据类型、字典、集合、文件操作(打开、关闭、读写、追加等)
    前言!!!注意:本系列所写的文章全部是学习笔记,来自于观看视频的笔记记录,防止丢失。观看的视频笔记来自于:哔哩哔哩武沛齐老师的视频:​​2022Python的web开发(完整版)入门全套教程,零基础入门到项目实战​数据结构数据类型字符串列表元组集合字典整型布尔None浮点型字节类......
  • 文档操作&异常捕获&列表、字典推导式
    【零】文档操作【1】读和写(覆盖写和追加写)#r(read):只读模式#将数据一次性全部读出#w(write):只写模式#如果文件存在则打开文件,并将文件内荣清空然后写入新的内容#如果文件不存在则新建文件,并写入新的内容#a(append):追加写模式#如果文件存在则打开文件,而......
  • 第 9 场 小白入门赛 字典树考试
    题目:4.字典树考试【算法赛】-蓝桥云课(lanqiao.cn)思路:我们可以先抛开题目,想一下一个二进制数是111111111 --->9个1,题目说(Ai&Aj)所以两个1一个组合,我们用最笨的方式取枚举----->是8+7+6+5+.......+1是36两两一组,想想X个1如何算呢?是不是应......
  • Linux架构28 ansible流程控制, 条件判断(主机,是否安装,系统版本), 循环语句(安装启动
    Ansible流程控制一、playbook条件语句不管是shell还是各大变成语言中,流程控制,条件判断这些都是必不可少的,在我们使用Ansible的过程中,条件判断的使用频率极其高。例如:1.我们使用不同的系统的时候,可以通过判断系统来对软件包进行安装。2.在nfs和rsync安装过程中,客户端服务器......
  • 列表、字典推导式
    列表推导式固定语法:[表达式foriinlist/dict...判断语句][if语句foriinlist/dict...][字符串处理foriinlist/dict...]name_list=['a','b']name_new=['nb_'+iforiinname_list]print(name_new)字典推导式固定语法:[key:value......
  • day02元组-集合-字典
    元组 概念元组:由一系列变量组成的不可变序列容器序列:支持索引和切片不可变:1.没有增删改的方法2.所有的操作都不会直接作用于原数据 定义<spanstyle="font-size:16px;"data-mce-style="font-size:16px;">元组tuple()#1.定义多......