1014 : Trie树

2024-02-16 04:48
文章标签 trie 1014

本文主要是介绍1014 : Trie树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

#1014 : Trie树

时间限制: 10000ms
单点时限: 1000ms
内存限制: 256MB

描述

小Hi和小Ho是一对好朋友,出生在信息化社会的他们对编程产生了莫大的兴趣,他们约定好互相帮助,在编程的学习道路上一同前进。

这一天,他们遇到了一本词典,于是小Hi就向小Ho提出了那个经典的问题:“小Ho,你能不能对于每一个我给出的字符串,都在这个词典里面找到以这个字符串开头的所有单词呢?

身经百战的小Ho答道:“怎么会不能呢!你每给我一个字符串,我就依次遍历词典里的所有单词,检查你给我的字符串是不是这个单词的前缀不就是了?

小Hi笑道:“你啊,还是太年轻了!~假设这本词典里有10万个单词,我询问你一万次,你得要算到哪年哪月去?”

小Ho低头算了一算,看着那一堆堆的0,顿时感觉自己这辈子都要花在上面了...

小Hi看着小Ho的囧样,也是继续笑道:“让我来提高一下你的知识水平吧~你知道树这样一种数据结构么?”

小Ho想了想,说道:“知道~它是一种基础的数据结构,就像这里说的一样!”

小Hi满意的点了点头,说道:“那你知道我怎么样用一棵树来表示整个词典么?”

小Ho摇摇头表示自己不清楚。

提示一:Trie树的建立

“你看,我们现在得到了这样一棵树,那么你看,如果我给你一个字符串ap,你要怎么找到所有以ap开头的单词呢?”小Hi又开始考校小Ho。

“唔...一个个遍历所有的单词?”小Ho还是不忘自己最开始提出来的算法。

“笨!这棵树难道就白构建了!”小Hi教训完小Ho,继续道:“看好了!”

提示二:如何使用Trie树

提示三:在建立Trie树时同时进行统计!

“那么现在!赶紧去用代码实现吧!”小Hi如是说道

输入

输入的第一行为一个正整数n,表示词典的大小,其后n行,每一行一个单词(不保证是英文单词,也有可能是火星文单词哦),单词由不超过10个的小写英文字母组成,可能存在相同的单词,此时应将其视作不同的单词。接下来的一行为一个正整数m,表示小Hi询问的次数,其后m行,每一行一个字符串,该字符串由不超过10个的小写英文字母组成,表示小Hi的一个询问。

在20%的数据中n, m<=10,词典的字母表大小<=2.

在60%的数据中n, m<=1000,词典的字母表大小<=5.

在100%的数据中n, m<=100000,词典的字母表大小<=26.

本题按通过的数据量排名哦~

输出

对于小Hi的每一个询问,输出一个整数Ans,表示词典中以小Hi给出的字符串为前缀的单词的个数。

样例输入
5
babaab
babbbaaaa
abba
aaaaabaa
babaababb
5
babb
baabaaa
bab
bb
bbabbaab
样例输出
1
0
3
0
0

#include<iostream>
#include<cstdlib>
#define MAX 26
using namespace std;typedef struct TrieNode                     
{bool isStr;int count;                         struct TrieNode *next[MAX];            
}Trie;void insert(Trie *root,const char *s)     
{if(root==NULL||*s=='\0')return;int i;Trie *p=root;p->count++;while(*s!='\0'){if(p->next[*s-'a']==NULL)        {Trie *temp=(Trie *)malloc(sizeof(Trie));for(i=0;i<MAX;i++){temp->next[i]=NULL;}temp->isStr=false;temp->count=0;p->next[*s-'a']=temp;p=p->next[*s-'a'];}else{p=p->next[*s-'a'];}s++;p->count++;}p->isStr=true;                       
}int search(Trie *root,const char *s)  
{Trie *p=root;while(p!=NULL&&*s!='\0'){p=p->next[*s-'a'];s++;}if(!p) return 0;else return p->count;     
}void del(Trie *root)                     
{int i;for(i=0;i<MAX;i++){if(root->next[i]!=NULL){del(root->next[i]);}}free(root);
}int main(int argc, char *argv[])
{int i;int n,m;                             char s[100];Trie *root= (Trie *)malloc(sizeof(Trie));for(i=0;i<MAX;i++){root->next[i]=NULL;}root->isStr=false;root->count=0;scanf("%d",&n);getchar();for(i=0;i<n;i++)                 {scanf("%s",s);insert(root,s);}scanf("%d",&m);for(i=0;i<m;i++)                 {scanf("%s",s);printf("%d\n",search(root,s));}printf("\n");del(root);                        
}




这篇关于1014 : Trie树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/713522

相关文章

ural 1014. Product of Digits贪心

1014. Product of Digits Time limit: 1.0 second Memory limit: 64 MB Your task is to find the minimal positive integer number  Q so that the product of digits of  Q is exactly equal to  N. Inpu

Python高效实现Trie(前缀树)及其插入和查找操作

Python高效实现Trie(前缀树)及其插入和查找操作 在Python面试中,考官通常会关注候选人的编程能力、问题解决能力以及对Python语言特性的理解。Trie(前缀树)是一种高效的数据结构,广泛应用于字符串处理、自动补全、拼写检查等场景。本文将详细介绍如何实现一个Trie,并提供插入和查找操作,确保代码实用性强,条理清晰,操作性强。 1. 引言 Trie(前缀树)是一种树形数据结构,

Trie 类型的题目总结

trie字典树可以用来查找单词或者搜索剪枝用。 Implement Trie (Prefix Tree) 实现一个 Trie,包含 insert, search, 和 startsWith 这三个方法。(模板必须记住;没有儿子建立儿子,有儿子走儿子;) class Trie {private class TrieNode {public TrieNode[] children;public b

【Trie树】模板题-POJ-2001

题意: 给你若干个单词,写出能每个单词的最短前缀 也就是说这个前缀能准确代表这个单词,和其他单词 without ambiguity  思路: 建立字典树存下这几个单词,ct 数组记录每个节点的子节点数,显然子树宽度只有1的话,这个单词就被确定了,改造一下我们的 find_word 函数就行啦 哦。。这个结构体要怎么搞还坑了我一下,要向下面那样定义! 代码: #include

Trie树专题

Intro:         为了高效的存储和查找字符串,集合的数据结构。,  板子: /*Trie树 —— 模板题 AcWing 835. Trie字符串统计*/int son[N][26], cnt[N], idx;// 0号点既是根节点,又是空节点// son[][]存储树中每个节点的子节点// cnt[]存储以每个节点结尾的单词数量// 插入一个字符串void insert(

数据结构-非线性结构-树形结构:Trie/字典树/前缀树【专门用于处理字符串类数据】

Trie的代码实现 import java.util.TreeMap;/*** Trie树(前缀树、字典树)** @author whx* @version 2018/9/1*/public class Trie {/*** 节点类** @author whx* @version 2018/9/1*/private class Node{public boolean isWord;publ

1014 Specialized Four-Dig

//水水题#include <iostream>using namespace std;int transfer(int a,int num){int sum=0;int b;while(a){b=a%num;a=a/num;sum+=b;}return sum;}int main(){int decc,shier,liu;for (int i=1000;i<=9999;i++){dec

Leetcode171: Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods. Trie树又被称为字典树、前缀树,是一种用于快速检索的多叉树。Tried树可以利用字符串的公共前缀来节省存储空间。 但如果系统存在大量没有公共前缀的字符串,相应的Trie树将非常消耗内存。 Trie树的基本性质如下: 根节点不包括字符,除根节点外每个节点包括

秋招突击——算法练习——8/26——图论——200-岛屿数量、994-腐烂的橘子、207-课程表、208-实现Trie

文章目录 引言正文200-岛屿数量个人实现 994、腐烂的橘子个人实现参考实现 207、课程表个人实现参考实现 208、实现Trie前缀树个人实现参考实现 总结 引言 正文 200-岛屿数量 题目链接 个人实现 我靠,这道题居然是腾讯一面的类似题,那道题是计算最大的岛屿面积,如果当时没做出来,现在得哭死!好在做出来了!这道题单纯使用回溯实现的,然后修改一下地图的坐标

字典树(trie 树)

Trie树又称字典树,字典查找树。 Trie有三种结构:标准trie 压缩trie 后缀trie。本篇博文主要介绍标准trie 标准 Trie树的结构 : 所有含有公共前缀的字符串将挂在树中同一个结点下。实际上trie简明的存储了存在于串集合中的所有公共前缀。 假如有这样一个字符串集合X{bear,bell,bid,bull,buy,sell,stock,stop}。它的标准Trie树如下图