hdu1247
#include<cstdio> #include <iostream> #include <string.h> #include <algorithm> using namespace std; char s[50000][105]; struct tree { tree *next[26]; int v; }; tree root; void build(char*str) { tree *p=&root; tree *q; int len=strlen(str); for(int i=0;i<len;i++) { int id=str[i]-'a'; if(p->next[id]!=NULL) p=p->next[id]; else { q=(tree*) new tree; q->v=-1; for(int j=0;j<26;j++) q->next[j]=NULL; p->next[id]=q; p=p->next[id]; } } p->v=1; } int findd(char *str) { tree *p=&root; int len=strlen(str); for(int i=0;i<len;i++) { int id=str[i]-'a'; p=p->next[id]; if(p==NULL) return -1; } return p->v; } int main() { int cnt=0; for(int i=0;i<26;i++) root.next[i]=NULL; while(scanf("%s",s[cnt])!=EOF) { build(s[cnt]); cnt++; } char s1[100]={'\0'},s2[100]={'\0'}; for(int i=0;i<cnt;i++) { int len=strlen(s[i]); for(int j=1;j<len;j++) { strcpy(s1,s[i]); s1[j]='\0'; strcpy(s2,s[i]+j); if(findd(s1)==1&&findd(s2)==1) { printf("%s\n",s[i]); break; } } } return 0; }
