【HDU】1247 - Hat’s Words（字典树）
【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): 13369 Accepted Submission(s): 4777
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
wordSample Output
ahat
hatwordAuthor
戴帽子的
记得以前好像用map + string做过吧？这次拿字典树拆也可以的。
本来还怕会超时，结果31ms就完了。
就是把每个单词暴力拆开，然后在字典树上查就行了。
代码如下：（注意strncpy的用法，不会自动在字符串后面加 ' \0 ' 的）
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define idx(x) (x-'a')
struct Trie
{
Trie *next[26];
bool word;
void clear()
{
for (int i = 0 ; i < 26 ; i++)
next[i] = NULL;
word = false;
}
}tree[100000];
int ant;
void insert(char *s)
{
int l = strlen(s);
Trie *p = &tree[0] , *q;
for (int i = 0 ; i < l ; i++)
{
int id = idx(s[i]);
if (p->next[id] == NULL)
{
q = &tree[ant++];
q->clear();
p->next[id] = q;
}
p = p->next[id];
}
p->word = true;
}
bool find(char *s)
{
int l = strlen(s);
Trie *p = &tree[0];
for (int i = 0 ; i < l ; i++)
{
int id = idx(s[i]);
if (p->next[id] == NULL) //没有这个单词
return false;
p = p->next[id];
}
if (p->word)
return true;
return false; //如果有些单词只是 "路过" 也不算
}
int main()
{
ant = 1;
tree[0].clear();
char str[50011][30];
int num = 0;
while (~scanf ("%s",str[num++]))
insert(str[num-1]);
for (int i = 0 ; i < num ; i++) //从第一个单词开始拆
{
int l = strlen(str[i]);
for (int j = 1 ; j < l ; j++)
{
char a[30];
strncpy(a,str[i],j);
a[j] = '\0'; //strncpy函数不添加'\0'
char b[30];
strcpy(b,str[i]+j);
if (find(a) && find(b))
{
printf ("%s\n",str[i]);
break; //输出完此轮不用再搜了
}
}
}
return 0;
}腾讯云开发者
