HDU 5687 字典树入门

Problem C

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

Problem Description

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

  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

 

Source

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

算是trie的入门级题目吧，也是第一次做字典树，搞了好久。

一开始每个node分一个bool变量总感觉可以，后发现操作都是对前缀而言，并没有精确到某一个词，所以换成了int方便统计。

例节点root->a->p->p的值为x,就表示app为前缀的词的数量，在insert和delete时维护这个变量、

还有就是指针的操作，又被搞迷糊一直RE，例如 node *p1=new node(),*p2=new node();

p1->child=p2;  这时如果令p2=NULL，则p1->child并不会变为NULL，这时显然的吧，，，，只是p1->child和p2指向了同一处内存而已，内存没有delete,

p1->child也不会受到影响。同理如果delete  p2,则p2指向的内存被释放，p1->child指向的这块也是被释放的内存了。

#include<bits/stdc++.h>
using namespace std;
struct node
{int have;node *child[26];node(){have=0;for(int i=0;i<26;++i) child[i]=NULL;}
};
node *root;
void release(node *p)
{if(p==NULL) return;for(int i=0;i<26;++i){if(p->child[i]!=NULL) release(p->child[i]);}delete p;
}
void Insert(char *s)
{node *p=root;int n1=strlen(s);for(int i=0;i<n1;++i){int t=s[i]-'a';if(p->child[t]==NULL)p->child[t]=new node();p=p->child[t];p->have++;}
}void Delete(char *s)
{node *p=root,*pre=p;int n1=strlen(s),t,num=0;for(int i=0;i<n1;++i){ t=s[i]-'a';if(p->child[t]==NULL) return;pre=p;p=p->child[t];}num=p->have;release(p);pre->child[t]=NULL;p=root;for(int i=0;i<n1-1;++i){p=p->child[s[i]-'a'];p->have-=num;}
}
bool Search(char *s)
{node *p=root;int n1=strlen(s);for(int i=0;i<n1;++i){int t=s[i]-'a';if(p->child[t]==NULL) return 0;p=p->child[t];}if((p->have)<1) return 0;return 1;
}
int main()
{int N,i,j;char s1[25],s2[35];cin>>N;root=new node();while(N--){scanf("%s%s",s1,s2);if(!strcmp(s1,"insert")){Insert(s2) ;}else if(!strcmp(s1,"delete")){Delete(s2);}else if(!strcmp(s1,"search")){Search(s2)?puts("Yes"):puts("No");}}release(root);return 0;
}