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
题目大意:给出你很多单词,求哪些单词是由这里其他单词(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;
}
分享到:
相关推荐
hdu 1695 GCD(欧拉函数+容斥原理).docx
acm hdu as easy as a+b
hdu 1166线段树代码
ACM题库,一些题目和答案,以及解题报告,传上来共享
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
杭电OnlineJudge 200-2099的解题报告
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
hdu 1166线段树
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。