字典树 不念不忘少年蓝@ 2022-07-12 05:51 213阅读 0赞 #### Problem Description #### 遇到单词不认识怎么办? 查字典啊,已知字典中有n个单词,假设单词都是由小写字母组成。现有m个不认识的单词,询问这m个单词是否出现在字典中。 #### Input #### 含有多组测试用例。 第一行输入n,m (n>=0&&n<=100000&&m>=0&&m<=100000)分别是字典中存在的n个单词和要查询的m个单词. 紧跟着n行,代表字典中存在的单词。 然后m行,要查询的m个单词 n=0&&m=0 程序结束 数据保证所有的单词都是有小写字母组成,并且长度不超过10 #### Output #### 若存在则输出Yes,不存在输出No . #### Example Input #### 3 2 aab aa ad ac ad 0 0 #### Example Output #### No Yes #include<stdio.h> #include<string.h> #include<stdlib.h> #define maxc 26 #define maxn 1000000 typedef struct node { int cnt; struct node * next[maxc]; }trietree; trietree trie[maxn]; int top; trietree * create () { int i; trietree * t=&trie[top++]; t->cnt=0; for(i=0;i<maxc;i++) { t->next[i]=NULL; } return t; } trietree * init() { top=0; return (create()); } void insert(trietree * tree,char str[]) { int i,id; trietree * p=tree; for(i=0;str[i];i++) { id=str[i]-'a'; if(!p->next[id]) { p->next[id]=create(); } p=p->next[id]; } p->cnt++; } int find (trietree * tree, char str[]) { int i,id; trietree * p=tree; for(i=0;str[i];i++) { id=str[i]-'a'; if(!p->next[id]) { return 0; } p=p->next[id]; } return 1; } int main() { int n,m,flag; char str[16]; trietree * tree; while(scanf("%d%d",&n,&m),n||m) { tree=init(); while(n--) { scanf("%s",str); insert(tree,str); } while(m--) { flag=0; scanf("%s",str); flag=find(tree,str); if(flag) { printf("Yes\n"); } else { printf("No\n"); } } } return 0; }
相关 字典树 字典树 Time Limit: 1000ms Memory limit: 65536K 有疑问?点这里^\_^ 题目描述 遇到单词不认识怎么办? 查字 ゞ 浴缸里的玫瑰/ 2022年08月18日 02:28/ 0 赞/ 180 阅读
相关 字典树 字典树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它 你的名字/ 2022年08月02日 14:59/ 0 赞/ 170 阅读
相关 字典树 Trie,又称字典树,前缀树(prefix tree),是一种树形结构,用于保存大量的字符串。 它的优点是:利用字符串的公共前缀来节约存储空间。查找、插入复杂度为O(n),n 电玩女神/ 2022年08月01日 00:08/ 0 赞/ 167 阅读
相关 字典树 Problem H: 位运算的游戏 Time Limit: 2 Sec Memory Limit: 128 MB Submit: 4 Solved: 2 电玩女神/ 2022年07月15日 10:16/ 0 赞/ 160 阅读
相关 字典树 Problem Description 遇到单词不认识怎么办? 查字典啊,已知字典中有n个单词,假设单词都是由小写字母组成。现有m个不认识的单词,询问这m个单词是否出现在 不念不忘少年蓝@/ 2022年07月12日 05:51/ 0 赞/ 214 阅读
相关 字典树 一、引入 [点击打开链接][Link 1] 字典是干啥的?查找字的。 字典树自然也是起查找作用的。查找的是啥?单词。 看以下几个题: 1、给出n个单词和m个询问 今天药忘吃喽~/ 2022年06月16日 08:21/ 0 赞/ 230 阅读
相关 字典树 题目链接:[点击打开链接][Link 1] 代码: include<iostream> include<cstring> using namespa 不念不忘少年蓝@/ 2022年05月30日 05:46/ 0 赞/ 190 阅读
相关 字典树 1 定义 键树又称数字查找树,它是一棵度大于2的树,树中的每个节点值含有组成关键字的符号。例如,若关键字是数值,则节点中只包含一个数位。若关键字是单词,则节点中只包含一个 r囧r小猫/ 2022年04月10日 01:47/ 0 赞/ 261 阅读
相关 字典树 字典树是一种以树这种结构为基础建立的算法 ,那么字典树到底有哪些典型的应用呢? 1.字典树在串的快速检索中的应用。 给出N个单词组成的熟词表,以及一篇全用小写英文 绝地灬酷狼/ 2022年03月19日 04:20/ 0 赞/ 256 阅读
相关 字典树 字典树 前言 利用指针实现 用数组实现 前言 介绍 字典树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用 男娘i/ 2021年11月09日 15:52/ 0 赞/ 295 阅读
还没有评论,来说两句吧...