没有见到过字典树的时候，以为会很神秘。
其实，如果链表学的差不多了，实现字典树那就是手到擒来。
做了几道题，效果还好。。
第一道：
NYOJ 290 动物统计加强版 点击打开链接
典型的字典树。裸的字典树。还是比较好的。不是太坑。算是练手了吧。直接就写了，也不用放内存什么的。但是，最好的还是把内存给放了吧，要不太占内存。
直接代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=26;
struct Node{
int count;
Node *next[N];
}*root;
int MaxConut=-1;
char ans[N];
Node* Build(){//建立以个节点,每个节点都最多有26个子节点,虽然真真的子节点数不确定.
Node* p=(Node*)malloc(sizeof(Node));
for(int i=0;i<N;i++){
p->next[i]=NULL;
}
p->count=0;
return p;
}
void Save(char *s){//保存word
int len=strlen(s);
if(len==0) return ;
Node* p=root;
for(int i=0;i<len;i++){
if(p->next[s[i]-'a']==NULL)
p->next[s[i]-'a']=Build();//不存在的话建立该节点.
p=p->next[s[i]-'a'];
}
p->count++;
if(p->count>=MaxConut) {
MaxConut=p->count;
strcpy(ans,s);
}
}
int main(){
// freopen("Input.txt","r",stdin);
int n;
scanf("%d",&n);
root=Build();
char animal[N];
for(int i=1;i<=n;i++){
scanf("%s",animal);
Save(animal);
}
printf("%s %d\n",ans,MaxConut);
return 0;
}
可以看到，其实，字典树，写起来也就50行的事情。不难。
第二道：
Phone List Hdu 1671
点击打开链接 Poj 3630
点击打开链接 NYOJ 163
点击打开链接
这题就比较坑点了。同样的代码，在Hdu，ML。在Poj TL。在NYOJ上WA。
只能说，数据不同，结果也会有所不同。由此可见，数据的重要性。
这题，也是比较裸的字典树吧。
有两中情况，一，先存了比较短的（也就是前缀）。二，先存了比较长的。这两中各判断一下就可以。
说明一下为什么会出现不同的结果。
Hdu，ML。就是因为自己没有释放内存，导致，无用内存积累，开辟新的内存又过多，导致ML。
Poj，TL。就是因为在动态分配内存的时候，过多的调用各种函数，导致超时。这时候就需要静态的来开辟空间了。
NYOJ，WA。这个是因为，自己在判断两种的时候，有一点小小的错误。
动态：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=10;
struct Node{
bool m;
Node *next[N];
};
Node* Build(){
Node *p=(Node*)malloc(sizeof(Node));
for(int i=0;i<N;i++){
p->next[i]=NULL;
}
p->m=false;
return p;
}
bool Save(char *s,Node *root){
int i,len=strlen(s);
// if(len==0) return false;
Node *p=root;
bool snack=false;
for(i=0;i<len;i++){
if(p->next[s[i]-'0']==NULL){
p->next[s[i]-'0']=Build();
snack=true;//没有开辟过新的空间.
}
else {
if(p->next[s[i]-'0']->m)
return true;
}
p=p->next[s[i]-'0'];
}
if(!snack) return true;
p->m=true;
return false;
}
void del(Node* p){
for(int i=0;i<N;i++){
if(p->next[i]!=NULL)
del(p->next[i]);
delete(p->next[i]);
}
}
int main(){
// freopen("1.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--){
int n;
char number[N];
scanf("%d",&n);
Node *root=Build();
bool flag=false;
for(int i=1;i<=n;i++){
scanf("%s",number);
if(!flag)
flag=Save(number,root);
}
if(flag) printf("NO\n");
else printf("YES\n");
del(root);
}
return 0;
}
静态：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=10;
const int M=1000003;
struct Node{
bool flag;
Node *next[N];
}node[M];
int top;
Node* Build(){
Node *p=&node[top++];
for(int i=0;i<N;i++){
p->next[i]=NULL;
}
p->flag=false;
return p;
}
bool Save(char *s,Node* root){
int len=strlen(s);
if(len==0) return false;
Node *p=root;
bool mark=false;
for(int i=0;i<len;i++){
if(p->next[s[i]-'0']==NULL){
mark=true;
p->next[s[i]-'0']=Build();
}
else if(p->next[s[i]-'0']->flag){
return true;
}
p=p->next[s[i]-'0'];
}
if(!mark) return true;
p->flag=true;
return false;
}
int main(){
// freopen("1.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
char number[N];
bool ans=false;top=0;
Node *root=Build();
for(int i=1;i<=n;i++){
scanf("%s",number);
if(!ans) ans=Save(number,root);
}
if(ans) printf("NO\n");
else printf("YES\n");
}
return 0;
}
很给力的题目。
第三道：
NYOJ 685 查找字符串
点击打开链接
还是裸的字典树。
直接代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=17;
const int M=29;
struct Node{
int count;
Node* next[M];
}*root;
Node* Build(){
Node* p=(Node*)malloc(sizeof(Node));
for(int i=0;i<M;i++){
p->next[i]=NULL;
}
p->count=0;
return p;
}
int find(char x){
if(x>='a'&&x<='z') return x-'a';
else if(x=='@') return 27;
else if(x=='+') return 28;
else return -1;
}
void Save(char *s){
int len=strlen(s);
if(len==0) return ;
Node *p=root;
for(int i=0;i<len;i++){
int k=find(s[i]);
if(p->next[k]==NULL){
p->next[k]=Build();
}
p=p->next[k];
}
p->count++;
}
int search(char *s){
int len=strlen(s);
Node* p=root;
for(int i=0;i<len;i++){
int k=find(s[i]);
if(p->next[k]==NULL)
return 0;
p=p->next[k];
}
return p->count;
}
void del(Node *p){
for(int i=0;i<M;i++){
if(p->next[i]!=NULL)
del(p->next[i]);
delete(p->next[i]);
}
}
int main(){
// freopen("Input.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d%d",&n,&m);
char word[N];
root=Build();
for(int i=1;i<=n;i++){
scanf("%s",word);
Save(word);
}
for(int i=1;i<=m;i++){
scanf("%s",word);
if(strlen(word)>15) printf("0\n");
else printf("%d\n",search(word));
}
del(root);
}
return 0;
}
比较简单。
今天的字典树就先告一段落了。