注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1671  

2012-09-24 22:45:43|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=1671
题意:给n个字符串,看是否存在某个字符串是另一个的前缀
数据很大,所以用字典树咯~
要注意的是,因为字典树是动态分配的内存,而且这题是有多组测试数据,所以一定要注意用完要释放内存,不然会超内存……

/*
* fudq.cpp
*
* Created on: 2012-09-24
*/
#include<algorithm>
#include<stdio.h>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<iostream>
using namespace std;
struct node
{
bool num; //记录该节点是否有子树
node *child[11];
};
node *p,*t;

char str[10010][12];

void Build(char str[],node *p)
{
int i,j;
for(i=0;i<(int)strlen(str);i++)
{
if(p->child[str[i]-'0']==NULL)
{
t=new node;
t->num=false;
for(j=0;j<10;j++)
t->child[j]=NULL;
p->child[str[i]-'0']=t;
p->num=true;
}
p=p->child[str[i]-'0'];
}
}

bool Find(char str[],node *p)
{
int i,len;
len=(int)strlen(str);
for(i=0;i<len;i++)
{
if(p->child[str[i]-'0']!=NULL)
{
p=p->child[str[i]-'0'];
if(i==len-1 && p->num==true)
return true;
if(p->num==false)
break;
}
else
return false;
}
return false;
}

void freedom(struct node *p)//从根结点开始,递归free
{
int i=0;
for(i=0;i<10;i++)
if(p->child[i]!=NULL)
freedom(p->child[i]);
free(p);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
#endif
int n,t,i,flag;
scanf("%d",&t);
while(t--)
{
node *root=new node;
for(i=0;i<10;i++)
root->child[i]=NULL;
root->num=false;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s",str[i]);
Build(str[i],root);
}
for(i=0,flag=1;i<n;i++)
if(Find(str[i],root))
break;
if(i==n)
printf("YES\n");
else
printf("NO\n");
freedom(root);//一定要记得释放内存
}
return 0;
}


  评论这张
 
阅读(269)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018