度熊手上有一本神奇的字典，你可以在它里面做如下三个操作：
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
sol：Trie的基本操作
插入时，记录下单词中每个字符出现的次数；
删除时，先在Trie中统计以该单词作为前缀的单词个数num，如果num>0，则删除这些单词。删除操作具体为，从根出发，每走到一个结点，该结点出现的次数-num，走到尾结点时，该结点被经过的次数清0，同时，该结点下连接的字符全部清0，即清空子结点。
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 #define ll long long 7 const int maxn = 1e6+5; 8 const int inf = 0x3f3f3f3f; 9 struct node 10 { 11 int next[26]; 12 int val; 13 }t[maxn]; 14 char f[20], s[50]; 15 int rt = 1; 16 int num; 17 18 void insert() 19 { 20 int u = 0, v; 21 int len = strlen(s+1); 22 for(int i = 1; i <= len; i++) 23 { 24 v = s[i] - 'a'; 25 if (!t[u].next[v]) 26 t[u].next[v] = rt++; 27 u = t[u].next[v]; 28 t[u].val++;//这个结点经过的次数+1 29 } 30 } 31 32 void del() 33 { 34 int u = 0, v; 35 int len = strlen(s+1); 36 37 for(int i = 1; i <= len; i++) 38 { 39 v = s[i] - 'a'; 40 u = t[u].next[v]; 41 t[u].val -= num;//删除时，每个结点经过的次数-num 42 //可能还有别的单词的长度是小于该前缀的 43 } 44 t[u].val = 0;//标记变量清空 45 46 for(int j = 0; j < 26; j++) 47 //一定要将其子结点全清空 48 t[u].next[j] = 0; 49 } 50 51 int search() 52 { 53 int u = 0, v; 54 int len = strlen(s+1); 55 56 for(int i = 1; i <= len; i++) 57 { 58 v = s[i] - 'a'; 59 if (!t[u].next[v]) return 0; 60 u = t[u].next[v]; 61 //if (t[u].val == 0) return 0; 62 } 63 return t[u].val; 64 } 65 66 int main() 67 { 68 69 int n; 70 cin >> n; 71 memset(t, 0, sizeof(t)); 72 while(n--){ 73 scanf("%s%s", f+1, s+1); 74 if (f[1] == 'i') 75 insert(); 76 else 77 if (f[1] == 'd') 78 { 79 num = search(); //统计前缀，num为以该串作为前缀的单词数 80 if (num != 0) 81 del();//删除这些单词 82 } 83 else { 84 if (search()) cout << "Yes" << endl; 85 else cout << "No" << endl; 86 } 87 } 88 return 0; 89 }