hdu5687

news/2024/10/30 15:30:35/

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
度熊手上有一本神奇的字典,你可以在它里面做如下三个操作:

  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




#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
struct Trie
{Trie*next[26];   //子节点 Trie*fa;          //父节点 int flag;  //等否成为前缀 
};
Trie*root;
void init()         //初始化 
{root=new Trie;for(int i=0;i<26;i++)root->next[i]=NULL;root->fa=NULL;root->flag=1;
}
void insert(char*str)         //插入单词 
{int len=strlen(str);Trie*s=root;for(int i=0;i<len;i++){s->flag=1;              //此前flag=1则表示可以成为某个单词的前缀 if(s->next[str[i]-'a'])s=s->next[str[i]-'a'];else{Trie*t=new Trie;for(int j=0;j<26;j++)t->next[j]=NULL;t->fa=s;t->flag=1;s->next[str[i]-'a']=t;s=t;}}s->flag=1;
}
int search(char*str)       //查找 
{int len=strlen(str);Trie*s=root;for(int i=0;i<len;i++){if(s->next[str[i]-'a']&&s->next[str[i]-'a']->flag)   //存在且flag=1 s=s->next[str[i]-'a'];elsereturn 0;}return 1;
}
void del(char*str)           //删除节点 
{int len=strlen(str);Trie*s=root;int cnt=0;for(int i=0;i<len;i++)         //找出存在的能成为这个单词且比他短的前缀的个数 {if(s->flag==1)cnt++;if(s->next[str[i]-'a'])s=s->next[str[i]-'a'];elsereturn;}Trie*ss=root;int x=0;int k;for(k=0;k<len;k++)       //使ss最后落在能成为这个单词的前缀的单词的最后一个字母上 {if(ss->flag==1)x++;if(x>=cnt)break;if(ss->next[str[k]-'a'])ss=ss->next[str[k]-'a'];}for(;k<len;k++)      //从这个字母开始寻找符合str的节点中子节点只有一个的节点并使其flag=0; {if(ss->next[str[k]-'a']){int sum=0;for(int i=0;i<26;i++)if(ss->next[i])sum++;if(sum>1)ss=ss->next[str[k]-'a'];else{ss->flag=0;return;}}}ss=ss->fa;ss->next[str[k-1]-'a']=NULL;return;
}
int main()
{init();int t;cin>>t;char op[10],word[35];while(t--){scanf("%s %s",op,word);if(strcmp(op,"insert")==0){insert(word);}else if(strcmp(op,"search")==0){if(search(word)==0)cout<<"No"<<endl;else cout<<"Yes"<<endl;}else if(strcmp(op,"delete")==0){del(word);}}
}



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

相关文章

【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系统的手机的拨号…

如何转接固定电话(内线)

如何转接固定电话&#xff08;内线&#xff09; 首先&#xff0c;必须是内线电话&#xff0c;只有内线电话才可以转接。如果不是你的电话响&#xff0c;先按*11&#xff0c;进行接听&#xff0c;然后按电话机R键后按分机号挂机后&#xff0c;听到目标话机响铃&#xff0c;挂断自…

智能语音机器人,无人电销时代 科技震撼来袭

马化腾曾在2018中国&#xff08;深圳&#xff09;IT领.袖峰会上表示&#xff0c;数字化转型是一个重大的机遇和挑战。 随着数字化经济的发展&#xff0c;中国的数字媒体进入了一个数据帝国时代。如何管理庞大的数据&#xff0c;建立数据分析和报告&#xff0c;反作用于…

公司电话系统是什么,有什么用?

公司电话系统是专门管理公司内部电话的&#xff0c;主要是为了满足企业通讯需求&#xff0c;解决公司在通讯上的一些问题。目的是提高企业通讯效率&#xff0c;节约通讯费用&#xff0c;降低运营成本。 公司电话系统是通过专业的软件系统将公司电话和计算机连接起来&#xff0c…

电话机器人可以做什么?

电话机器人的认知 在之前呢&#xff0c;其实我和大多数人的认知一样。认为现在的人工智能还很弱&#xff0c;还和网络上戏称为“人工智障”一样。而生活上渐渐地出现了所谓的小爱&#xff0c;SIRI&#xff1b;这些服务型机器人&#xff0c;它们的出现带来不少便利&#xff0c;但…

电话机器人系统成功部署,无限开通电话机器人——2

三、强化外呼和CRM管理 外呼数据的导入&#xff0c;支持格式更全面&#xff0c;包含公司、姓名、号码自启动外呼&#xff0c;设置外呼任务后&#xff0c;会自动在工作时间启动外呼&#xff0c;如中午午休或隔夜后自启动外呼。 通话状态显示&#xff0c;包含有人接听、无人接听…