`

hdu 1247 Hat’s Words(字典树+分段判断)

阅读更多

Hat’s Words

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2391    Accepted Submission(s): 873

Problem Description
A hat’s word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.
You are to find all the hat’s words in a dictionary.

 

Input
Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 50,000 words.
Only one case.

 

Output
Your output should contain all the hat’s words, one per line, in alphabetical order.
Sample Input
a ahat hat hatword hziee word
Sample Output
ahat hatword
 
          题目大意:给出你很多单词,求哪些单词是由这里其他单词(2个)连接组成的,注意!2个相同的单词连接也可以的!
       又是字典树,不过要操作一下指针链表。方法是:将每一个单词分成两部分,分成两部分有len-1种方法,对每次情况进行枚举判断,判断是否组成已有的单词。这题也可以用stl的映射来做的,那个代码很短,也还好吧。
代码:
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <string>
using namespace std;

char sh[50005][20];

struct node
{
    bool flag;
    node *next[26];
};

node *root, memory[5000005];
int cnt = 0;

node *create()
{
    node *p = &memory[cnt++];
    int i;
    for(i = 0; i < 26; i++)
    {
        p->next[i] = NULL;
    }
    p->flag = false;
    return p;
}

void insert(char *s)
{
    node *p = root;
    int i, k;
    for(i = 0; s[i]; i++)
    {
        k = s[i] - 'a';
        if(p->next[k] == NULL)
        {
            p->next[k] = create();
        }
        p = p->next[k];
    }
    p->flag = true;
}

bool search(char *s)
{
    int i, j, k;
    bool tar;
    for(i = 0; s[i]; i++)
    {
        node *p = root;
        for(j = 0; j < i; j++)
        {
            k = s[j] - 'a';
            p = p->next[k];
        }
        if(p->flag == 1)
        {
            node *q = root;
            tar = true;
            for(j = i; s[j]; j++)
            {
                k = s[j] - 'a';
                if(q->next[k] == NULL)
                {
                    tar = false;
                    break;
                }
                q = q->next[k];
            }
            if(q->flag == 1 && tar)
            {
                return true;
            }
        }
    }

    return false;
}

int main()
{
    int i, n;
    root = create();
    i = 0;
    while(scanf("%s", sh[i]) != EOF)
    {
        insert(sh[i]);
        i++;
    }
    n = i;
    for(i = 0; i < n; i++)
    {
        if(search(sh[i]))
        {
            printf("%s\n", sh[i]);
        }
    }

    return 0;
}
0
4
分享到:
评论

相关推荐

    ACM hdu 线段树题目+源代码

    ACM hdu 线段树题目+源代码 线段树是一种非常重要的数据结构,它广泛应用于算法竞赛和实际编程中。今天,我们将通过 ACM hdu 的几个题目来学习和掌握线段树的基本概念和应用。 线段树的基本概念 线段树是一种...

    hdu 1695 GCD(欧拉函数+容斥原理).docx

    "hdu 1695 GCD(欧拉函数+容斥原理)" 题目大意是:给定 a, b, c, d, k,找到一队 x, y,满足 g(x, y) = k,且 x ∈ [1, b], y ∈ [1, d],问有多少对符合要求的 (x, y)。 思路是:gcd(x, y) == k 解释 x, y 都能...

    HDU+2000-2099+解题报告

    HDU(杭州电子科技大学)在线评测系统是许多编程竞赛爱好者和学习者经常访问的平台,它提供了大量的算法题目供用户练习和挑战。这个压缩包文件“HDU 2000-2099 解题报告”显然包含了在这个题号范围内的一些问题、...

    HDU+2000-2099+解题报告.zip

    《杭电OnlineJudge 2000-2099解题报告》是针对杭州电子科技大学(HDU)在线评测系统(OnlineJudge)中2000至2099题目的详细解答集锦,主要涵盖了算法分析、编程技巧以及问题解决策略等内容。这份解题报告以CHM...

    hdu acm1166线段树

    hdu 1166线段树代码

    HDU ACM as easy as a+b

    - **条件判断**:使用 `if` 条件语句来控制程序流程,例如 `if(a&gt;a[i+1])`。 - **数据交换**:通过中间变量 `t` 实现两个变量值的交换,如 `t=a; a=a[i+1]; a[i+1]=t;`。 #### 算法知识点 - **排序算法**:代码中...

    hdu 300+ AC 代码

    HDU 300+ AC 代码集合是一个包含超过300个已通过验证的算法解决方案的资源,这些代码主要用于解决各类计算机编程竞赛中的问题。这些竞赛通常由杭州电子科技大学(HDU)主办,旨在提升参赛者的算法设计、编程和问题...

    hdu.rar_hdu

    3. **数据结构**:数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图(邻接矩阵、邻接表、最小生成树、拓扑排序等)。 4. **字符串处理**:KMP算法、Manacher's Algorithm、Rabin-Karp算法等。 5. **...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    HDU刷题地图+精选详细笔记

    本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!

    vc2019中 源文件<bits/stdc++.h>无法打开

    在VC2019中,当你遇到"源文件&lt;bits/stdc++.h&gt;无法打开"的问题时,这通常意味着你试图在你的C++项目中使用一个预编译头文件,但是这个文件在标准库中并不存在。`&lt;bits/stdc++.h&gt;`是GCC编译器中的一个非标准头文件,它...

    HDU题目java实现

    8. **图论与树**:HDU题目中可能涉及图的遍历(深度优先搜索DFS、广度优先搜索BFS)、树的遍历(前序、中序、后序)以及最小生成树、最短路径等算法。 9. **动态规划**:这是一种优化策略,通过构建状态转移方程来...

    二叉搜索树练习 HDU3791

    总结来说,"二叉搜索树练习 HDU3791"是一道关于二叉搜索树操作的编程题,可能需要实现插入、删除、查找等基本操作,并通过分析`Main.java`源码来理解和解决问题。同时,可能需要借助各种工具进行调试和测试,以确保...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    解题代码 hdu1241

    DFS是一种用于遍历或搜索树或图的算法。在这个过程中,算法从根节点开始探索尽可能深的子节点路径。当到达最深的叶子节点时,它会回溯到最近的一个未完成探索的节点,并继续进行探索。 **实现方法:** DFS通常有两...

    ACM HDU

    【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...

    HDU1059的代码

    HDU1059的代码

Global site tag (gtag.js) - Google Analytics