hdu 1247 Hat’s Words(字典树)

简介:

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1247

分析:这道题可以使用stl中的map直接来解决,也可以使用字典树来解决,当然字典树的效率会更高

(1)stl解法不做过多的解释,这里有网上一个stl解法的链接  http://hi.baidu.com/mingyiyiyi_3/item/25835459866641494eff20f5

(2)字典树解法,字典树 (详细看链接解释)

定义一个字典树结构体

typedef struct Trie
{
    bool flag;//从根到此是否为一个单词
    Trie *next[MAXNUM];
}Trie;

字典树的插入操作
void insert(char *word)
{
    Trie *tem = root;
    while(*word!='\0')
    {
        if(tem->next[*word-'a']==NULL)
        {
            Trie *cur = (Trie *)malloc(sizeof(Trie));
            for(int i=0;i<MAXNUM;i++)
            cur->next[i]=NULL;
            cur->flag=false;
            tem->next[*word-'a']=cur;
        }
        tem = tem->next[*word-'a'];
        word++;
    }
    tem->flag=true;
}

以上两段代码是字典树的核心,要先弄懂。然后针对本题,flag是标志从根到当前位置是否可以组成一个单词,是为true,否为false。然后搜索每个单词是否有两个单词组成,这时就要把每个单词拆分,一个长度为n的单词可以拆分为n-1组组合,然后枚举判断是否在该字典树集合内。

 

复制代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXNUM 26
using namespace std;

//单词
char words[50005][100];
//定义字典树
typedef struct Trie
{
    bool flag;//从根到此是否为一个单词
    Trie *next[MAXNUM];
}Trie;

Trie *root;

void init()
{
    root = (Trie *)malloc(sizeof(Trie));
    root->flag=false;
    for(int i=0;i<MAXNUM;i++)
    root->next[i]=NULL;
}

void insert(char *word)
{
    Trie *tem = root;
    while(*word!='\0')
    {
        if(tem->next[*word-'a']==NULL)
        {
            Trie *cur = (Trie *)malloc(sizeof(Trie));
            for(int i=0;i<MAXNUM;i++)
            cur->next[i]=NULL;
            cur->flag=false;
            tem->next[*word-'a']=cur;
        }
        tem = tem->next[*word-'a'];
        word++;
    }
    tem->flag=true;
}

bool search(char *word)
{
    Trie *tem = root;
    for(int i=0;word[i]!='\0';i++)
    {
        if(tem==NULL||tem->next[word[i]-'a']==NULL)
        return false;
        tem=tem->next[word[i]-'a'];
    }
    return tem->flag;
}


int main()
{
    init();
    int t=0;
    char w[100];
    while(scanf("%s",words[t])!=EOF)
    {

        insert(words[t]);
        t++;
    }
    for(int i=0;i<t;i++)
    {
        memset(w,'\0',sizeof(w));
        for(int j=0;words[i][j]!='\0';j++)
        {
            *(w+j)=*(words[i]+j);
            if(search(w)&&search((words[i]+j+1)))
            {
                printf("%s\n",words[i]);
                break;
            }
        }

    }
    return 0;
}
复制代码
相关文章
|
5月前
【洛谷 P2249】【深基13.例1】查找(向量+lower_bound)
**深基13.例1**是关于查找的编程题,要求在单调不减的整数序列中,对每个查询\( q \)返回其首次出现的位置或输出\-1。输入包含序列大小\( n \),查询次数\( m \),以及序列和查询列表。使用`lower_bound`进行二分查找,找到第一个大于等于目标值的元素位置,若找不到或找到的值不等于目标值,则返回\-1。提供的AC代码中,优化了输入读取,并利用`std::vector`和`std::lower_bound`实现了高效解决方案。
36 0
|
算法
light oj 1255 - Substring Frequency (KMP)
输入两个字符串,计算二串在一串中出现的次数。 裸裸的KMP,参考刘汝佳《算法竞赛入门经典训练指南》 P212 或数据结构。
27 1
|
算法 Python
LeetCode 1160. 拼写单词 Find Words That Can Be Formed by Characters
LeetCode 1160. 拼写单词 Find Words That Can Be Formed by Characters
LeetCode 1160. 拼写单词 Find Words That Can Be Formed by Characters
[HDU7073] Integers Have Friends 2.0 -随机大法好
题意: 找到最大的一个集合,使得集合内所有元素 % m(>=2) 问最大的集合大小
94 0
[HDU7073] Integers Have Friends 2.0 -随机大法好
|
存储 Python
[Leetcode][python]N-Queens/N-Queens II/N皇后/N皇后 II
N-Queens 题目大意 经典的八皇后问题的一般情况 注意点: 皇后用"Q"表示,空白用"."表示 解题思路 回溯法,位运算等,见总结
119 0
转:肉饼的自白:You&#39;ve got to find what you love
《You've got to find what you love》是乔布斯2005年在斯坦福大学毕业典礼上的演讲,当我第一次看到这个演讲视频的时候,被彻底震住了。回顾自己跌跌撞撞的人生道路,就是一个不断寻找然后坚持自己钟爱事业的过程。
1374 0
|
Java
2017 Multi-University Training Contest - Team 1 1002&&HDU 6034 Balala Power!【字符串,贪心+排序】
Balala Power! Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 2668    Accepted Submission(s...
1275 0