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

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

【字典树】hdu 1247 Hat’s Words  

2011-12-16 20:26:32|  分类: ACM_数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目链接:
题目大意:
给出一些单词,输出这些单词中,哪些单词是由其他两个单词组合而成,

分析:
My First 字典树 Blood!
字典树,构造出字典树后,搜索即可

代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 50000
using namespace std;

char data[MAXN][50];
int dcont;
const int tk = 26,tb = 'a';//tk,字典树的叉数,tb 开始的字符
int top;//字典树中元素的个数
int tree[MAXN][tk + 1];

void tree_init()
{
        top = 1;
        memset(tree[0],0,sizeof(tree[0]));
}

int search(char *s)
{
        if(*s == 0) return 0;
        for(int rt = 0;rt = tree[rt][*s - tb]; )
                if(*(++s) == 0) return tree[rt][tk];//注意是tk,tk是标示位,有效位为0-25
        return 0;
}

int search2(char *s)//找到第一个包含的单词
{
        int p = 0;
        for(int rt = 0;rt = tree[rt][*(s+p) - tb]; )
        {
                p ++;
                if(*(s + p) == 0) return 0;
                if(tree[rt][tk] == 1)
                {
                        if(search(s + p) == 1) return 1;//找第二个包含的单词注意a ,aa ,aaa 这种情况的数据,
                }
        }
        return 0;
}

void insert(char *s,int rank = 1)
{
        int rt,nxt;
        for(rt = 0; *s ;rt = nxt, ++s )
        {
                nxt = tree[rt][*s - tb];
                if(nxt == 0)
                {
                        tree[rt][*s - tb] = nxt = top;
                        memset(tree[top],0,sizeof(tree[top]));
                        top ++;
                }
        }
        tree[rt][tk] = rank;//tk位标示该单词是否存在
}

void init()
{
        dcont = 0;
        char ts[50];
        tree_init();
        while(scanf("%s",ts) != EOF)
        {
                strcpy(data[dcont++],ts);
                insert(ts,1);
        }
}

void work()
{
        for(int i = 0;i < dcont ; i ++)
                if(search2(data[i])) puts(data[i]);
}

int main()
{
//        freopen("in.txt","r",stdin);
        init();
        work();
        return 0;
}
  评论这张
 
阅读(205)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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