Problem C

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1007    Accepted Submission(s): 321 Problem Description 度熊手上有一本神奇的字典，你可以在它里面做如下三个操作：   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 <iostream> #include <cstdio> #include <cstring> #include <cstdlib> using namespace std; const int maxn = 30; struct Trie{ int cnt; Trie *next[maxn]; Trie(){ cnt = 0; memset(next,0,sizeof(next)); } }; Trie *root; void Insert(char *word) { Trie *tem = root; while(*word != '\0') { int x = *word - 'a'; if(tem->next[x] == NULL) tem->next[x] = new Trie; tem = tem->next[x]; tem->cnt++; word++; } } int Search(char *word) { Trie *tem = root; for(int i=0;word[i]!='\0';i++) { int x = word[i]-'a'; if(tem->next[x] == NULL) return 0; tem = tem->next[x]; } return tem->cnt; } void Delete(char *word,int t) { Trie *tem = root; for(int i=0;word[i]!='\0';i++) { int x = word[i]-'a'; tem = tem->next[x]; (tem->cnt)-=t; } for(int i=0;i<maxn;i++) tem->next[i] = NULL; } int main() { int n; char str1[50]; char str2[50]; while(scanf("%d",&n)!=EOF) { root = new Trie; while(n--) { scanf("%s %s",str1,str2); if(str1[0]=='i') Insert(str2); else if(str1[0] == 's') { if(Search(str2)) printf("Yes\n"); else printf("No\n"); } else { int t = Search(str2); if(t) Delete(str2,t); } } } return 0; }