ACM: 强化训练-百度之星-Problem C-字典树

Problem C

Time Limit:1000MS     Memory Limit:131072KB     64bit IO Format:%I64d & %I64u

Description

度熊手上有一本神奇的字典，你可以在它里面做如下三个操作：

1、insert : 往神奇字典中插入一个单词

2、delete: 在神奇字典中删除所有前缀等于给定字符串的单词

3、search: 查询是否在神奇字典中有一个字符串的前缀等于给定的字符串

Input

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

Output

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

Sample Input

5insert helloinsert hehesearch hdelete hesearch hello  

Sample Output

YesNo 中文题。。。明显字典树。。。 

#include"iostream"
#include"cstdio"
#include"cstring"
#include"algorithm"
#include"cmath"
using namespace std;
#define MX 11111
#define memset(x,y) memset(x,y,sizeof(x))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1struct node {
int v;
int next[27];
void init() {
v=0;
memset(next,-1);
}
} dir[1200500];
int tot=0;void BuildTrie(char p[]) {
int len=strlen(p);
int now=0;
for(int i=0; i<len; i++) {
int t=p[i]-'a';
if(dir[now].next[t]==-1) {
tot++;
dir[tot].init();
dir[now].next[t]=tot;
}
now=dir[now].next[t];
dir[now].v++;  //记路达到该节点的次数
}
}int Query(char p[]) {
int len=strlen(p);
int now=0;
for(int i=0; i<len; i++) {
int t=p[i]-'a';
if(dir[now].next[t]==-1)return 0;
now=dir[now].next[t];
if(dir[now].v<=0) return 0;
}
return 1;
}/*/
删除函数有几个要注意的地方：
1.删除要把所有的以s为前缀的尾巴全部去掉；
2.不仅仅要把后面所有的节点都删除，还要把那些以p为前缀的长字符串的前缀也要去掉相印个数。
/*/
void Delete(char p[]) {
int now=0;
int len=strlen(p);
for(int i=0; i<len; i++) {
int t=p[i]-'a';
if(dir[now].next[t]==-1)return ;
now=dir[now].next[t];
}
int d=dir[now].v;//记录要删除的节点最后的次数，前面每一个节点都要去掉这个此时
dir[now].init();//清除尾节点后面所有的节点
now=0;
for(int i=0; i<len; i++) {
int t=p[i]-'a';
now=dir[now].next[t];
dir[now].v-=d;
if(dir[now].v<0)dir[now].v=0;//判断，不能为负数
}
}int main() {
int T;
scanf("%d",&T);
char op[10],s[40];
memset(op,0);
memset(s,0);
dir[0].init();//【这里忘记清空根节点。WA哭了。。。】
while(T--) {
scanf("%s %s",op,s);
if(op[0]=='i')BuildTrie(s);
else if(op[0]=='s') {
int ok=Query(s);
if(ok>0)printf("Yes\n");
else printf("No\n");
} else if(op[0]=='d') {
int del=Query(s);
if(del) Delete(s);
}
}
return 0;
}