HDU 5687 字典树入门

news/2024/10/30 13:25:55/

Problem C

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1423    Accepted Submission(s): 426


Problem Description
度熊手上有一本神奇的字典,你可以在它里面做如下三个操作:

  1、insert : 往神奇字典中插入一个单词

  2、delete: 在神奇字典中删除所有前缀等于给定字符串的单词

  3、search: 查询是否在神奇字典中有一个字符串的前缀等于给定的字符串

 

Input
这里仅有一组测试数据。第一行输入一个正整数 N(1N100000),代表度熊对于字典的操作次数,接下来N行,每行包含两个字符串,中间中用空格隔开。第一个字符串代表了相关的操作(包括: insert, delete 或者 search)。第二个字符串代表了相关操作后指定的那个字符串,第二个字符串的长度不会超过30。第二个字符串仅由小写字母组成。

 

Output
对于每一个search 操作,如果在度熊的字典中存在给定的字符串为前缀的单词,则输出Yes 否则输出 No。

 

Sample Input
5 insert hello insert hehe search h delete he search hello

 

Sample Output
Yes No

 

Source
2016"百度之星" - 资格赛(Astar Round1)
算是trie的入门级题目吧,也是第一次做字典树,搞了好久。
一开始每个node分一个bool变量总感觉可以,后发现操作都是对前缀而言,并没有精确到某一个词,所以换成了int方便统计。
例节点root->a->p->p的值为x,就表示app为前缀的词的数量,在insert和delete时维护这个变量、
还有就是指针的操作,又被搞迷糊一直RE,例如 node *p1=new node(),*p2=new node();
p1->child=p2;  这时如果令p2=NULL,则p1->child并不会变为NULL,这时显然的吧,,,,只是p1->child和p2指向了同一处内存而已,内存没有delete,
p1->child也不会受到影响。同理如果delete  p2,则p2指向的内存被释放,p1->child指向的这块也是被释放的内存了。
#include<bits/stdc++.h>
using namespace std;
struct node
{int have;node *child[26];node(){have=0;for(int i=0;i<26;++i) child[i]=NULL;}
};
node *root;
void release(node *p)
{if(p==NULL) return;for(int i=0;i<26;++i){if(p->child[i]!=NULL) release(p->child[i]);}delete p;
}
void Insert(char *s)
{node *p=root;int n1=strlen(s);for(int i=0;i<n1;++i){int t=s[i]-'a';if(p->child[t]==NULL)p->child[t]=new node();p=p->child[t];p->have++;}
}void Delete(char *s)
{node *p=root,*pre=p;int n1=strlen(s),t,num=0;for(int i=0;i<n1;++i){ t=s[i]-'a';if(p->child[t]==NULL) return;pre=p;p=p->child[t];}num=p->have;release(p);pre->child[t]=NULL;p=root;for(int i=0;i<n1-1;++i){p=p->child[s[i]-'a'];p->have-=num;}
}
bool Search(char *s)
{node *p=root;int n1=strlen(s);for(int i=0;i<n1;++i){int t=s[i]-'a';if(p->child[t]==NULL) return 0;p=p->child[t];}if((p->have)<1) return 0;return 1;
}
int main()
{int N,i,j;char s1[25],s2[35];cin>>N;root=new node();while(N--){scanf("%s%s",s1,s2);if(!strcmp(s1,"insert")){Insert(s2) ;}else if(!strcmp(s1,"delete")){Delete(s2);}else if(!strcmp(s1,"search")){Search(s2)?puts("Yes"):puts("No");}}release(root);return 0;
}

 

转载于:https://www.cnblogs.com/zzqc/p/7204863.html


http://www.ppmy.cn/news/209540.html

相关文章

ibm 2011年服务器型号,IBM x 系列服务器CPU型号

94Y6685. 英特尔至强E5-2690 处理器&#xff0c;8核&#xff0c;主频 2.9GHZ,20MB 高速缓存&#xff0c;最大内存速度 1600MHZ,功率为 135w,带风扇 RMB30,631 69Y5331. 英特尔至强E5-2680 处理器&#xff0c;8核&#xff0c;主频 2.7GHZ,20MB 高速缓存&#xff0c;最大内存速度…

5687字典树

动态开点 #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cstdlib> using namespace std; struct node {int val;struct node *next[26]; }*head; void Insert(char *s) {struct node *pphead;for(…

hdu 5687 Problem C

点击打开链接 Problem C Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 2240 Accepted Submission(s): 618 Problem Description 度熊手上有一本神奇的字典&#xff0c;你可以在它里面做如下三个操作&…

hdu 5687

Problem C Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 967 Accepted Submission(s): 300 Problem Description 度熊手上有一本神奇的字典&#xff0c;你可以在它里面做如下三个操作&#xff1a; 1、in…

hdu5687

Problem C Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1543 Accepted Submission(s): 450 Problem Description 度熊手上有一本神奇的字典&#xff0c;你可以在它里面做如下三个操作&#xff1a; 1、i…

【FPGA零基础学习之旅#6】ip核基础知识之计数器

&#x1f389;欢迎来到FPGA专栏~ip核基础知识之计数器 ☆* o(≧▽≦)o *☆嗨~我是小夏与酒&#x1f379; ✨博客主页&#xff1a;小夏与酒的博客 &#x1f388;该系列文章专栏&#xff1a;FPGA学习之旅 文章作者技术和水平有限&#xff0c;如果文中出现错误&#xff0c;希望大家…

Java006——对第一个Java程序HelloWorld的简单介绍

一、HelloWorld.java程序整体认识 public class HelloWorld { //创建一个名字叫HelloWorld的类&#xff08;Java中的类叫class&#xff09;public static void main(String[] args) {//主程序入口&#xff0c;类似C语言main函数System.out.println("He…

苹果呼叫转移设置不了_怎么设置别人电话打不进来

您可以尝试输入【**21*888888#】并按下拨打键&#xff0c;开启本机的呼叫转移功能&#xff0c;在开启之后别人拨打您的电话会转移到888888这个空号&#xff0c;实现别的电话无法打入的效果。以下就是相关的步骤介绍&#xff1a; 1、只需要在安卓或者苹果iOS 11系统的手机的拨号…