1、insert : 往神奇字典中插入一个单词2、delete: 在神奇字典中删除所有前缀等于给定字符串的单词3、search: 查询是否在神奇字典中有一个字符串的前缀等于给定的字符串

5
insert hello
insert hehe
search h
delete he
search hello

Yes
No

①insert:插入操作,插入输入的字符串s;

②search:查询操作,问是否存在以字符串s作为前缀的字符串

③delete:删除操作,删除以字符串s作为前缀的所有字符串(包括前缀本身)

之前因为就有字典树模板,但是没有删除操作这一块,所以裸敲删除操作就可以AC

在删除操作时,要注意,我是通过初始化前缀字符串s的最后一个字母结点来达到删除的功能,但第一次忘了去更新前驱节点的值导致WA了一发

为了便于理解,放一组测试数据

INPUT

4

insert hello

search h

detele hell

search h

OUTPUT

Yes

No

题目链接→HDU 5687 Problem C

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define exp 1e-10
using namespace std;
const int N = 35;
const int M = 26;
const int inf = 100000000;
const int mod = 2009;
struct tree
{int a[M],t;
}s[1000005];
char ch[N];
int p;
void init(int x)
{s[x].t=0;memset(s[x].a,-1,sizeof(s[x].a));
}
void buildtree()
{int i,k=0;for(i=0;ch[i]!='\0';i++){if(s[k].a[ch[i]-'a']==-1){s[k].a[ch[i]-'a']=p;init(p++);}k=s[k].a[ch[i]-'a'];s[k].t++;}    
}
void query()
{int i,k=0;for(i=0;ch[i]!='\0';i++){if(s[k].a[ch[i]-'a']==-1){puts("No");return ;}k=s[k].a[ch[i]-'a'];}if(s[k].t)puts("Yes");elseputs("No");
}
void deletetree()
{int i,k=0,z;for(i=0;ch[i]!='\0';i++){if(s[k].a[ch[i]-'a']==-1)return ;k=s[k].a[ch[i]-'a'];}z=s[k].t;for(k=i=0;ch[i]!='\0';i++){k=s[k].a[ch[i]-'a'];s[k].t-=z;}init(k);
}
char x[10];
int main()
{int n,m,i;while(~scanf("%d",&n)){p=0;init(p++);for(i=0;i<n;i++){scanf("%s%s",x,ch);if(x[0]=='i')buildtree();else if(x[0]=='s')query();elsedeletetree();}}return 0;
}

菜鸟成长记