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
度熊手上有一本神奇的字典，你可以在它里面做如下三个操作：
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
#include <stdio.h>
#include <string.h>typedef struct node{int num;node *next[30];node(){ memset(next,0,sizeof(next));num=0;}
}Trie;
char dir[32],s[32];
void insert(node *root,char *s){node *p=root;for(int i=0;s[i];i++){int x=s[i]-'a';if(p->next[x]==NULL)p->next[x]=new node;p=p->next[x];p->num++;}
}
int search(node *root,char *s){node *p=root;for(int i=0;s[i];i++){int x=s[i]-'a';if(p->next[x]==NULL)return 0;p=p->next[x];}return p->num;
}
void Delete(node *root,char *s,int cnt){node *p=root;for(int i=0;s[i];i++){int x=s[i]-'a';p=p->next[x];p->num-=cnt;}for(int i=0;i<30;i++)p->next[i]=0;
}
int main(){int n;scanf("%d",&n);Trie *root=new node;while(n--){scanf("%s %s",dir,s);if(dir[0]=='i'){insert(root,s);}else if(dir[0]=='s'){int ans=search(root,s);if(ans)printf("Yes\n");elseprintf("No\n");}else{int cnt=search(root,s);if(cnt)Delete(root,s,cnt);}}
}
