Hat’s Words（字典树）

题意：问给定的单词中，，输出可以由另外两个单词拼成的单词，按照字典序输出。分析：先用字典树处理所有单词，然后对单词进行枚举，每个单词分成两部分来查找。题目链接：?pid=1247代码清单：#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;}

青春一经典当即永不再赎