Compound Words
--------------------------------------------------------------------------------
Time limit: 1sec. Submitted: 102
Memory limit: 32M Accepted: 26
Source : Waterloo ACM Programming Contest Sep 28, 1996
--------------------------------------------------------------------------------
You are to find all the two-word compound words in a dictionary. A two-word compound word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.
Input
Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 120,000 words.
Output
Your output should contain all the compound words, one per line, in alphabetical order.
Sample Input
a
alien
born
less
lien
never
nevertheless
new
newborn
the
zebra
Sample Output
alien
newborn
题目大意就是先输入单词，输入结束后输出词典中所有的合成词．
我写了一个，用哈希表写的，time limited，晕了，想请教下大家有什么更好的方法没，谢谢！
以下是我的代码，已经超时...
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define PRIME 25013
typedef struct NODE
{
int name;
struct NODE *next;
}Word;
bool tag[PRIME];
char s[120000][40];
Word a[PRIME];
int hash(char *p)
{
unsigned int h=0, g;
for(; *p; ++p)
{
h = (h<<4) + *p;
if((g = (h & 0xf0000000)))
{
h = h ^ (g >> 24);
h = h ^ g;
}
}
return h % PRIME;
}
bool search(int inpos,char temp[])
{
if(tag[inpos]==false)
return false;
else
{
Word *point=a+inpos;
while(point)
{
if(strcmp(s[point->name],temp)==0)
return true;
else point=point->next;
}
return false;
}
}
int main()
{
int i=0,j,k,pos,len;
char temp[40];
while(scanf("%s",s[i])!=EOF)
{
pos=hash(s[i]);
if(tag[pos]==false)
{
tag[pos]=true;
a[pos].name=i;
a[pos].next=NULL;
}
else
{
Word *ptr=(Word *)malloc(sizeof(Word));
ptr->next=NULL;
ptr->name=i;
Word *q=a+pos;/*可能有问题*/
while(q->next)
q=q->next;
q->next=ptr;
}
i++;
}
for(k=0;k<i;k++)
{
len=strlen(s[k]);
for(j=1;j<len-1;j++)
{
memccpy(temp,s[k],'\0',j);
*(temp+j)='\0';
if(search(hash(temp),temp))
{
sprintf(temp,"%s",s[k]+j);
if(search(hash(temp),temp))
{
printf("%s\n",s[k]);
break;
}
}
}
}
return 0;
}
已修改为可ac的代码．
[此贴子已经被作者于2006-12-1 23:45:43编辑过]
