Problem Description

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

 

Input

这里仅有一组测试数据。第一行输入一个正整数N(1≤N≤100000)，代表度熊对于字典的操作次数，接下来N行，每行包含两个字符串，中间中用空格隔开。第一个字符串代表了相关的操作（包括： insert, delete 或者 search）。第二个字符串代表了相关操作后指定的那个字符串，第二个字符串的长度不会超过30。第二个字符串仅由小写字母组成。

 

Output

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

 

Sample Input

Sample Output

 

Source

 

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #include <cmath>

 #include <cstring>

 #define INF 0x3f3f3f3f

 #define LL long long int

 #define Bits 26

 using namespace std;

 const int MAXN = ;

 int N;

 struct Trie

 {

     Trie *next[Bits];

     int flag;

     inline void init(){

         this->flag = ;

         for(int i = ; i < Bits; i++)

             this->next[i] = NULL;

     }

 };

 Trie *Root = (Trie *)malloc(sizeof(Trie));

 inline void DelTrie(Trie *t)

 {

     if(t == NULL) return;

     for(int i = ; i < Bits; i++){

         if(t->next[i]!=NULL) DelTrie(t->next[i]);

     }free(t);

     return;

 }

 void Create_Trie(char *str, bool isDel)

 {

     int len = strlen(str);

     Trie *p = Root, *temp;

     int Delnum = ;

     for(int i = ; i < len; i++){

         int index = str[i]-'a';

         if(!isDel){

             if(p->next[index] == NULL){

                 temp = (Trie *)malloc(sizeof(Trie));

                 temp->init();

                 p->next[index] = temp;

                 p = p->next[index];

             }

             else{p->next[index]->flag+=; p=p->next[index];}

         }

         else{

             if(p->next[index] != NULL){

                 Delnum = p->next[index]->flag;

                 p = p->next[index];

             }else return;

         }

     }

     if(isDel){

         p = Root;

         for(int i = ; i < len; i++){

             int index = str[i]-'a';

             if(p->next[index] == NULL) return;

             if(i==len-){

                 DelTrie(p->next[index]);

                 p->next[index] = NULL;

                 return;

             }

             p->next[index]->flag-=Delnum;

             p = p->next[index];

         }

     }

 }

 bool Find_Trie(char *str)

 {

     int len = strlen(str);

     Trie *p = Root;

     for(int i = ; i < len; i++){

         int index = str[i]-'a';

         if(p->next[index] != NULL && p->next[index]->flag > )

             p=p->next[index];

         else return false;

     }return true;

 }

 int main()

 {

     Root->init();

     scanf("%d", &N);

     char str[MAXN], command[];

     while(N--){

         scanf("%s", command);

         if(strcmp(command, "insert")==){

             scanf("%s", str);

             Create_Trie(str, false);

         }

         else if(strcmp(command, "delete")==){

             //puts("zjj");

             scanf("%s", str);

             Create_Trie(str, true);

         }

         else{

             scanf("%s", str);

             if(Find_Trie(str)) puts("Yes");

             else puts("No");

         }

     }DelTrie(Root);

     return ;

 }