trie树练习 Hat’s Words

发布时间:2017-2-27 19:25:35 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"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;  }  

上一篇:LINUX系统服务相关操作
下一篇:Unity3D和网页数据交互的基本原理

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。