Hat’s Words hdu1247 字典树+搜索
先把单词用字典树存储，再依次对每个单词枚举拆分点，看拆分后的两个单词是否都有。
#include<iostream>#include<cstdio>#include<cstring>using namespace std;struct node{bool isTail;node *next[26];}memory[1000000],*root;int cur;char word[50005][15];node *build_node(){node *p=&memory[cur++];for(int i=0;i<26;i++)p->next[i]=NULL;p->isTail=false;return p;}void insert_tree(char *s){int len=strlen(s);node *p=root;for(int i=0;i<len;i++){if(p->next[s[i]-'a']==NULL)p->next[s[i]-'a']=build_node();p=p->next[s[i]-'a'];}p->isTail=true;}bool query(char *s,int len,int cnt)//cnt起标记作用，记录是否已分成两个单词{node *p=root;for(int i=0;i<len;i++){p=p->next[s[i]-'a'];if(p==NULL)return false;if(cnt==1&&p->isTail)if(i<len-1&&query(&s[i+1],len-i-1,2))return true;}if(cnt==2&&p->isTail)return true;return false;}int main(){int i=0;cur=0;root=build_node();while(~scanf("%s",word[i]))insert_tree(word[i++]);for(int j=0;j<i;j++)if(query(word[j],strlen(word[j]),1))printf("%s\n",word[j]);return 0;}