hdu 5687 裸字典树

news/2024/10/30 13:36:21/

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

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

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

3、search: 查询是否在神奇字典中有一个字符串的前缀等于给定的字符串
Input
这里仅有一组测试数据。第一行输入一个正整数N(1≤N≤100000)N(1≤N≤100000),代表度熊对于字典的操作次数,接下来NN行,每行包含两个字符串,中间中用空格隔开。第一个字符串代表了相关的操作(包括: 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

#include <bits/stdc++.h>
using namespace std;const int MAXN = 3000005;
const int CASE_SIZE = 26;
struct Trie
{int child[MAXN][CASE_SIZE],value[MAXN],trieN,root;void init(){trieN=root=0;value[root]=0;memset(child[root],-1,sizeof(child[root]));}int newnode(){trieN++;value[trieN]=0;memset(child[trieN],-1,sizeof(child[trieN]));return trieN;}void insert(char *s){int x=root;for(int i=0;s[i];i++){int d=s[i]-'a';if(child[x][d]==-1)child[x][d]=newnode();x=child[x][d];value[x]++;}}void del(char *s){int x=root;for(int i=0;s[i];i++){int d=s[i]-'a';if(child[x][d]==-1) {return ;}x=child[x][d];}int res=value[x];x=root;for(int i=0;s[i];i++){int d=s[i]-'a';if(child[x][d]==-1) {return ;}int pre=x;x=child[x][d];value[x]-=res;if(value[x]==0) child[pre][d]=-1;}}int search(char *s){int x=root;for(int i=0;s[i];i++){int d=s[i]-'a';if(child[x][d]==-1)return 0;x=child[x][d];} if(value[x]) return 1;return 0;}
}trie;char s[30];
char str[30];
int main()
{int n;scanf("%d",&n);trie.init();while(n--){scanf("%s",str);scanf("%s",s);if(str[0]=='i') trie.insert(s);if(str[0]=='d') trie.del(s);if(str[0]=='s') if(trie.search(s)) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
}

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

相关文章

HDU 5687 字典树入门

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 度熊手上有一本神奇的字典&#xff0c;你可以在它里面做如下三个操作&#xff1a; 1、inse…

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…