trie树练习 Hat’s Words

发布时间:2014-10-22 13:33:54编辑 分享查询网我要评论
本篇文章主要介绍了"trie树练习 Hat’s Words",主要涉及到trie树练习 Hat’s Words方面的内容,对于trie树练习 Hat’s Words感兴趣的同学可以参考一下。

Hat’s Words Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 2174    Accepted Submission(s): 791 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 #include<stdio.h> #include<string.h> #include<malloc.h>  struct node { int flag; struct node *next[26]; }; struct node *root; char s[50001][21];  struct node *chuangjian()  { int i; struct node *p; p=(struct node*)malloc(sizeof(struct node)); p->flag=0; for(i=0;i<26;i++) p->next[i]=NULL; return p;  }  void insert(char *s)  { int i; struct node *p; p=(struct node*)malloc(sizeof(struct node)); p->flag=0; p=root; int len=strlen(s); for(i=0;i<len;i++) { if(p->next[s[i]-'a']==NULL) { p->next[s[i]-'a']=chuangjian(); } p=p->next[s[i]-'a']; } p->flag=1;  }  int  search(char *s)  { int i,n; n=strlen(s); struct node *p=root; for(i=0;i<n;i++) { if(p->next[s[i]-'a']==NULL) return 0; else p=p->next[s[i]-'a']; } return p->flag;  }  int main()  { int n,i,k,m,j; char str1[21],str2[21]; root =(struct node*)malloc(sizeof(struct node));      for(i=0;i<26;i++)    root->next[i]=NULL; k=1; while(scanf("%s",s[k])!=EOF) { insert(s[k]); k++; } for(i=1;i<k;i++) { n=strlen(s[i]); for(j=1;j<n;j++) { for(m=0;m<j;m++)//一点点分来测试 str1[m]=s[i][m]; str1[m]='\0';//一定要加上,不然WA if(search(str1)) { int p; for(p=j;p<n;p++) str2[p-j]=s[i][p]; str2[p-j]='\0'; if(search(str2)) { printf("%s\n",s[i]); break; } } } } free(root); return 0;  }