首页 > HDOJ解题报告 > HDU1247 Hat’s Words 字典树

HDU1247 Hat’s Words 字典树

HDU1247 Hat’s Words http://acm.hdu.edu.cn/showproblem.php?pid=1247 字典树问题

字典树应用,先插入所有单词,然后暴力拆分每个单词,看拆分后的两个单词是否都在字典树中出现,如果出现,那么这个单词符合要求,这时候break一下,不要再找了。因为,abcd可以由a和bcd组成,如果还有ab和cd,那么前面输出了后面就不用输出了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
//===============================================
// Name        : HDU1247
// Author      : 代码疯子
// Keyword     : Keyword Tree
// Copyright   : http://www.programlife.net
// Description : Hat’s Words
//===============================================
 
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
 
#define MAXNUM 50010
#define MAXLEN 110
 
char dic[MAXNUM][MAXLEN];
 
typedef struct TagNode
{
	int len;
	TagNode *next[26];
	TagNode()
	{
		len = 0;
		for(int i = 0; i < 26; ++i)
		{
			next[i] = NULL;
		}
	}
}Node;
 
Node root;
 
void TreeCreate(char *w)
{
	int i, len = strlen(w);
	Node *p = &root;
 
	for(i = 0; i < len; ++i)
	{
		if(p->next[w[i]-'a'] == NULL)
		{
			p->next[w[i]-'a'] = new Node();
		}
		p = p->next[w[i]-'a'];
	}
	p->len = len;
}
 
bool TreeQuery(char *w)
{
	int i, len = strlen(w);
	Node *p = &root;
 
	for(i = 0; i < len; ++i)
	{
		if(p->next[w[i]-'a'] == NULL)
		{
			return false;
		}
		p = p->next[w[i]-'a'];
	}
	if(p->len == len)
	{
		return true;
	}
	return false;
}
 
int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
 
	int i = 0, n = 0, len, j;
	int idxa, idxb;
	char a[MAXLEN], b[MAXLEN];
	while(EOF != scanf("%s", dic[i]))
	{
		TreeCreate(dic[i]);
		++i;
	}
	n = i;
	for(i = 0; i < n; ++i)
	{
		len = strlen(dic[i]);
		idxa = idxb = 0;
		for(j = 1; j < len; ++j)
		{
			a[idxa] = dic[i][idxa];
			a[++idxa] = '\0';
			for(idxb = j; idxb < len; ++idxb)
			{
				b[idxb - j] = dic[i][idxb];
			}
			b[idxb - j] = '\0';
			//printf("a: %s\nb: %s\n", a, b);
			if(TreeQuery(a) && TreeQuery(b))
			{
				puts(dic[i]);
				//发现单词后可以跳出循环,否则有可能多输出
				//abcd可以是a+bcd,ab+cd只需要输出一次即可
				break;
			}
		}
	}
 
	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> HDU1247 Hat’s Words 字典树
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



分类: HDOJ解题报告 标签: , , ,
  1. StarQoQ
    2012年4月13日18:42 | #1

    假如说数据规模扩大。求O(N)算法。

    [回复]

  1. 本文目前尚无任何 trackbacks 和 pingbacks.