Problem C
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 232 Accepted Submission(s): 82
Problem Description
度熊手上有一本神奇的字典,你可以在它里面做如下三个操作:
1、insert : 往神奇字典中插入一个单词
2、delete: 在神奇字典中删除所有前缀等于给定字符串的单词
3、search: 查询是否在神奇字典中有一个字符串的前缀等于给定的字符串
1、insert : 往神奇字典中插入一个单词
2、delete: 在神奇字典中删除所有前缀等于给定字符串的单词
3、search: 查询是否在神奇字典中有一个字符串的前缀等于给定的字符串
Input
这里仅有一组测试数据。第一行输入一个正整数N(1≤N≤100000),代表度熊对于字典的操作次数,接下来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
字典树添加,删除,查询操作。
删除前缀的时候记得把这个点指向的下一个节点的next数组清空,这样就不用递归删除后面的字符串了。
/* *********************************************** Author :guanjun Created Time :2016/5/14 16:17:31 File Name :baidu1c.cpp ************************************************ */ #include <iostream> #include <cstring> #include <cstdlib> #include <stdio.h> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <iomanip> #include <list> #include <deque> #include <stack> #define ull unsigned long long #define ll long long #define mod 90001 #define INF 0x3f3f3f3f #define maxn 10010 #define cle(a) memset(a,0,sizeof(a)) const ull inf = 1LL << 61; const double eps=1e-5; using namespace std; struct node { int next[27]; int v; void init(){ v=0; memset(next,-1,sizeof(next)); } }; node L[1200500]; int tot=0; void add(char s[],int len){ int now=0; for(int i=0;i<len;i++){ int t=s[i]-'a'; int next=L[now].next[t]; if(next==-1){ next=++tot; L[next].init(); L[now].next[t]=next; } now=next; L[now].v=1; } } int query(char s[],int len){ int now=0; for(int i=0;i<len;i++){ int t=s[i]-'a'; int next=L[now].next[t]; if(next==-1)return 0; now=next; } return L[now].v; } void _(char s[],int len,int cnt){ int now=0; for(int i=0;i<len;i++){ int t=s[i]-'a'; int next=L[now].next[t]; if(next==-1)return ; if(i==len-1)L[now].v=0; now=next; //L[now].v-=cnt; } //L[now].v=0; for(int i=0;i<26;i++)L[now].next[i]=-1; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif //freopen("out.txt","w",stdout); int n; char t[100],s[100]; while(cin>>n){ L[0].init(); for(int i=1;i<=n;i++){ scanf("%s %s",s,t); int len=strlen(t); if(s[0]=='i')add(t,len); else if(s[0]=='s'){ if(query(t,len)>0)puts("Yes"); else puts("No"); } else if(s[0]=='d'){ int cnt=query(t,len); if(cnt) _(t,len,cnt); } } } return 0; }