hdu 1427 Hat’s Words(字典树+分段判断)_C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > hdu 1427 Hat’s Words(字典树+分段判断)

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

 2011/10/6 8:12:30  gzhu_101majia  http://gzhu-101majia.iteye.com  我要评论(0)
  • 摘要:Hat’sWordsTimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):2391AcceptedSubmission(s):873ProblemDescriptionAhat’swordisawordinthedictionarythatistheconcatenationofexactlytwootherwordsinthedictionary
  • 标签:

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的映射来做的,那个代码很短,也还好吧。 链接:http://acm.hdu.edu.cn/showproblem.php?pid=1247 代码:
#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;
}
  • 相关文章
发表评论
用户名: 匿名