算法题：HDU 1247 Hat’s Words（字典树）

算法题：HDU 1247 Hat’s Words（字典树）2014-03-17 csdn博客 shuangde800链接：

http://acm.hdu.edu.cn/showproblem.php？pid=1247

题目大意：

按照字典序给出多个单词，可以发现里面有些单词是由字典中其它的两个单词组成的。按顺序输出所有符合这个条件的单词。

分析与总结：

用字典树存下所有的单词，然后对所有单词一一枚举，对每个单词，又进行“拆分”，拆分可能有多种情况，所以枚举单词拆分的中点，在字典序中查找拆分后的两部分是否存在，存在即输出。

代码：

#include<iostream>#include<cstdio>#include<cstring>#include<cctype>using namespace std; const int MAXN = 2000000;const int KIND = 26; struct node{bool isword;node *next[KIND];void init（）{isword=false;memset（next, 0, sizeof（next））;}}HEAP[MAXN]; int cntNode,pos;char word[50005][50]; inline node* newNode（）{HEAP[cntNode].init（）;return &HEAP[cntNode++];} void insert（node *root, char *str）{int cnt=0;for（char *p=str; *p; ++p）{int ch=*p-"a";if（root->next[ch]==NULL）{root->next[ch]=newNode（）;}root = root->next[ch];}root->isword = true;} bool search（node *root, char *str）{for（char *p=str; *p; ++p）{int ch=*p-"a";if（root->next[ch]==NULL）return false;root=root->next[ch];}return root->isword;} int main（）{cntNode=0; pos=0;node *root=newNode（）;char str[100];while（gets（word[pos]））{insert（root, word[pos++]）;}for（int i=0; i<pos; ++i）{if（word[i][0]==0 || strlen（word[i]）==1） continue;memset（str, 0, sizeof（str））;for（int j=0; j<strlen（word[i]）-1; ++j）{str[j]=word[i][j];if（search（root,str） && search（root,word[i]+j+1））{puts（word[i]）;break;}}}return 0;}