Problem C

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 2697 Accepted Submission(s): 743

Problem Description

度熊手上有一本神奇的字典，你可以在它里面做如下三个操作：
  1、insert : 往神奇字典中插入一个单词
  2、delete: 在神奇字典中删除所有前缀等于给定字符串的单词
  3、search: 查询是否在神奇字典中有一个字符串的前缀等于给定的字符串

Input

这里仅有一组测试数据。第一行输入一个正整数

Output

对于每一个search 操作，如果在度熊的字典中存在给定的字符串为前缀的单词，则输出Yes 否则输出 No。

Sample Input

5 insert hello insert hehe search h delete he search hello

Sample Output

Yes No

Source

2016"百度之星" - 资格赛（Astar Round1）

解题思路：

输入查询都是字典树基本操作，这里的字典树的删除是一种标记删除而不是物理删除（非最后节点）。

但是这里的标记删除要注意的是不能直接取消标记或标记为 0 ，而是要根据要删除的字符串在字典中出现的次数，然后根据这个次数去更新路径上的点的标记。如果是删除字符的最后节点则进行物理删除。

例如说：字典里是 zzaizjja，zzaizjj，要删除 zzaizjja，如果单纯把路径 zzaizjja 上的节点都更新为0，则它的子串也 out 了，所以正确的更新是：路径上的点减去zzaizjja出现的次数。

AC Code：

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <algorithm>
  4 #include <cmath>
  5 #include <cstring>
  6 #define INF 0x3f3f3f3f
  7 #define LL long long int
  8 #define Bits 26
  9 using namespace std;
 10 const int MAXN = 33;
 11 int N;
 12 struct Trie
 13 {
 14     Trie *next[Bits];
 15     int flag;
 16     inline void init(){
 17         this->flag = 1;
 18         for(int i = 0; i < Bits; i++)
 19             this->next[i] = NULL;
 20     }
 21 };
 22 Trie *Root = (Trie *)malloc(sizeof(Trie));
 23 inline void DelTrie(Trie *t)
 24 {
 25     if(t == NULL) return;
 26     for(int i = 0; i < Bits; i++){
 27         if(t->next[i]!=NULL) DelTrie(t->next[i]);
 28     }free(t);
 29     return;
 30 }
 31 
 32 void Create_Trie(char *str, bool isDel)
 33 {
 34     int len = strlen(str);
 35     Trie *p = Root, *temp;
 36     int Delnum = 0;
 37     for(int i = 0; i < len; i++){
 38         int index = str[i]-'a';
 39         if(!isDel){
 40             if(p->next[index] == NULL){
 41                 temp = (Trie *)malloc(sizeof(Trie));
 42                 temp->init();
 43                 p->next[index] = temp;
 44                 p = p->next[index];
 45             }
 46             else{p->next[index]->flag+=1; p=p->next[index];}
 47         }
 48         else{
 49             if(p->next[index] != NULL){
 50                 Delnum = p->next[index]->flag;
 51                 p = p->next[index];
 52             }else return;
 53         }
 54     }
 55     if(isDel){
 56         p = Root;
 57         for(int i = 0; i < len; i++){
 58             int index = str[i]-'a';
 59             if(p->next[index] == NULL) return;
 60             if(i==len-1){
 61                 DelTrie(p->next[index]);
 62                 p->next[index] = NULL;
 63                 return;
 64             }
 65             p->next[index]->flag-=Delnum;
 66             p = p->next[index];
 67         }
 68     }
 69 }
 70 
 71 
 72 bool Find_Trie(char *str)
 73 {
 74     int len = strlen(str);
 75     Trie *p = Root;
 76     for(int i = 0; i < len; i++){
 77         int index = str[i]-'a';
 78         if(p->next[index] != NULL && p->next[index]->flag > 0)
 79             p=p->next[index];
 80         else return false;
 81     }return true;
 82 }
 83 
 84 int main()
 85 {
 86     Root->init();
 87     scanf("%d", &N);
 88     char str[MAXN], command[10];
 89     while(N--){
 90         scanf("%s", command);
 91         if(strcmp(command, "insert")==0){
 92             scanf("%s", str);
 93             Create_Trie(str, false);
 94         }
 95         else if(strcmp(command, "delete")==0){
 96             //puts("zjj");
 97             scanf("%s", str);
 98             Create_Trie(str, true);
 99         }
100         else{
101             scanf("%s", str);
102             if(Find_Trie(str)) puts("Yes");
103             else puts("No");
104         }
105     }DelTrie(Root);
106     return 0;
107 }