hdu 1247 字典树以及map+string 2种做法

Hat’s WordsTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3847    Accepted Submission(s): 1456


Problem DescriptionInputOutputSample InputSample OutputAuthorRecommend#include<stdio.h>#include<string.h>#include<malloc.h>struct haha{ int cnt; struct haha *next[26];}q,temp;char str[50010][100];struct haha *root;struct haha *creat(){ int i; struct haha *p; p=(struct haha *)malloc(sizeof(struct haha)); p->cnt=0; for(i=0;i<26;i++) { p->next[i]=NULL; } return p;}void insert(char *s){ int d,i,pos; struct haha *p=root; d=strlen(s); for(i=0;i<d;i++) { pos=s[i]-'a'; if(p->next[pos]==NULL) { p->next[pos]=creat(); p=p->next[pos]; } else p=p->next[pos]; } p->cnt=1;}int find2(char *s){ int i,pos,d; struct haha *p; p=root; d=strlen(s);// printf("d=%d \n",d); for(i=0;i<d;i++) { pos=s[i]-'a'; if(p->next[pos]!=NULL) { p=p->next[pos]; } else return 0; } if(p->cnt==1) return 1; return 0;}int find1(char *s){ int i,pos,d; struct haha *p; p=root; d=strlen(s);// printf("d1=%d\n",d); for(i=0;i<d;i++) { pos=s[i]-'a'; if(p->next[pos]!=NULL) { if(p->cnt==1) {if(find2(s+i)) return 1;} p=p->next[pos]; } else return 0; } return 0;}int main(){ int i,count=0,t=6; root=creat(); while(scanf("%s",str[count])!=EOF)// while(t--) { // scanf("%s",str[count]); insert(str[count]); count++; } for(i=0;i<count;i++) { if(find1(str[i])) puts(str[i]); } return 0;}#include <iostream>#include <string>#include <map>using namespace std;map <string, int> m_v;string str[50006];int main() { int k(-1); while(cin >> str[++k]) { m_v[str[k]] = 1; } for(int i = 0; i <= k; i++) { int e = str[i].size()-1; for(int j = 1; j < e; j++) { string s1(str[i], 0, j); string s2(str[i], j); if(m_v[s1] == 1 && m_v[s2] == 1) { cout << str[i] << endl; break; } } } return 0;}