a ahat hat hatword hziee word
ahat hatword
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int MAX = 30; struct trie{ bool point; //单词的结尾标记 trie *next[MAX]; }; trie *root=new trie; int k=0,slen,k1,k2; char s1[MAX],s2[MAX]; char str[50005][MAX],s[MAX]; void createTrie(char *s){ trie *p=root, *q; int len=strlen(s),pos; for(int i=0;i<len;i++){ pos=s[i]-'a'; if(p->next[pos]==NULL){ q=new trie; q->point=false; for(int j=0;j<MAX;j++) q->next[j]=NULL; p->next[pos]=q; p=p->next[pos]; } else{ p=p->next[pos]; } } p->point=true; } bool findTrie(char *s){ trie *p=root; int len=strlen(s),pos; for(int i=0;i<len;i++){ pos=s[i]-'a'; if(p->next[pos]==NULL) return false; p=p->next[pos]; } return p->point; } void delTrie(trie *Root){ for(int i=0;i<MAX;i++){ if(Root->next[i]!=NULL) delTrie(Root->next[i]); } free(Root); } int main(){ freopen("liuchu.txt","r",stdin); for(int i=0;i<MAX;i++) root->next[i]=NULL; while(scanf("%s",s)!=EOF){ slen=strlen(s); for(int i=0;i<slen;i++) str[k][i]=s[i]; k++; createTrie(s); } for(int i=0;i<k;i++){ slen=strlen(str[i]); k1=0; for(int j=0;j<slen-1;j++){ k2=0; s1[k1++]=str[i][j]; for(int h=j+1;h<slen;h++) s2[k2++]=str[i][h]; s2[k2]='\0'; if(findTrie(s1)&&findTrie(s2)){ printf("%s\n",str[i]); break; } } memset(s1,'\0',sizeof(s1)); memset(s2,'\0',sizeof(s2)); } delTrie(root); return 0; }
原文:http://blog.csdn.net/jhgkjhg_ugtdk77/article/details/44628731