本文主要是介绍Hat’s Words（hdu 1247）（trie tree），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Hat’s Words（hdu 1247）
一个 “hat’s word”是一个单词可以恰好由字典中其他两个单词联接得到。给出你字典中的单词，你的工作是找出字典中所有的hat’s word。
输入：
每行为一个单词，由小写英文字母组成。所有单词按照字典顺序排列，总数不超过50,000。只有一组测试数据。
输出：
输出为所有的hat’s word，且按照字典顺序输出。
输入样例：
a
ahat
hat
hatword
hziee
word
输出样例：
ahat
hatword
分析：
将每个单词都插入到Trie树里，并按顺序依次判断每个单词是不是hat’s word。判断一个单词是不是hat’s word时，用暴力将这个单词分成前后两部分，判断这两部分是否都出现在Trie树里。
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;char ch[50050][100];struct node
{struct node * next[26];bool value;node(){for(int i = 0; i < 26; i++)next[i] = NULL;value = false;}
}* root;void insert(char s[])
{int k = 0;node *p = root;while(s[k] != '\0'){if( ! p->next[s[k]-'a'])p->next[s[k]-'a'] = new node();p = p->next[s[k]-'a'];k++;}p->value = true;
}bool find(char s[])
{int k = 0;node *p = root;while(s[k] != '\0' && p->next[s[k]-'a']){p = p->next[s[k]-'a'];k++;}if(s[k] == '\0' && p->value)return p->value;return false;
}int main()
{int i = 0, k;root = new node();while(scanf("%s", ch[i]) != EOF){insert(ch[i]);i++;}for(k = 0; k < i; k++){int j;for(j = 1;j < strlen(ch[k]) - 1; j++){char s1[100], s2[100];for(int jj = 0; jj < j; jj++)s1[jj] = ch[k][jj];s1[j] = '\0';strcpy(s2, ch[k] + j);if(find(s1) && find(s2)){cout << ch[k] << "\n";break;}}}return 0;
}这篇关于Hat’s Words（hdu 1247）（trie tree）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
