首页 > 代码库 > （字典树）HDU - 1247 Hat’s Words
（字典树）HDU - 1247 Hat’s Words
原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1247
题意：输出在所给字典中所有的hat‘s word。hat‘s word：是字典中由其他两个单词连接而成的的单词。
分析：现存下所有单词，然后遍历查询。用exist记录当前节点是否组成单词。当遍历某一个单词word时，如果在遍历结束前，在第i个查到当前前缀已经组成了单词，那么再从头遍历检查word.substr(i+1,word.length())【从第1个开到末尾组成的子串】。因为可能存在多个i，所以用res记录可以组合的方法数，最后判断如果res>0，则输出那个word。
因为两个单词检查判断不太一样，可以分两个函数写。
代码：
1 #include <set> 2 #include <map> 3 #include <list> 4 #include <cmath> 5 #include <queue> 6 #include <vector> 7 #include <bitset> 8 #include <string> 9 #include <cctype> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <iostream> 14 #include <algorithm> 15 16 using namespace std; 17 18 typedef long long ll; 19 typedef unsigned long long ull; 20 #define inf (0x3f3f3f3f) 21 #define lnf (0x3f3f3f3f3f3f3f3f) 22 #define eps (1e-8) 23 int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1;} 24 25 //-------------------------- 26 27 struct Trie_node { 28 int cnt; 29 int next[26]; 30 bool exist; 31 }tree[400010]; 32 int nxt; 33 34 int createTrieNode() { 35 memset(&tree[nxt], 0, sizeof(Trie_node)); 36 return nxt++; 37 } 38 39 void Trie_insert(string &word) { 40 int rt=0; 41 int len=word.length(); 42 for(int i=0;i<len;i++){ 43 int id = word[i]-‘a‘; 44 if(!tree[rt].next[id]){ 45 tree[rt].next[id]=createTrieNode(); 46 } 47 rt=tree[rt].next[id]; 48 tree[rt].cnt++; 49 } 50 tree[rt].exist=true; 51 } 52 53 bool Trie_search2(string word){ 54 int rt=0; 55 int len=word.length(); 56 for(int i=0;i<len;i++){ 57 int id=word[i]-‘a‘; 58 if(!tree[rt].next[id])return false; 59 rt=tree[rt].next[id]; 60 } 61 return tree[rt].exist; 62 } 63 64 bool Trie_search1(string &word) { 65 int rt=0; 66 int len=word.length(); 67 int res=0; 68 for(int i=0;i<len;i++){ 69 int id=word[i]-‘a‘; 70 rt=tree[rt].next[id]; 71 if(tree[rt].exist&&Trie_search2(word.substr(i+1,len-i-1)))res++; 72 } 73 return res>0; 74 } 75 76 void init(){ 77 nxt=1; 78 memset(&tree[0],0,sizeof(Trie_node)); 79 } 80 81 string word[50010]; 82 83 void solve() { 84 init(); 85 int n=0; 86 while(cin>>word[n]){ 87 Trie_insert(word[n]); 88 n++; 89 } 90 for(int i=0;i<n;i++){ 91 if(Trie_search1(word[i]))cout<<word[i]<<endl; 92 } 93 94 } 95 96 97 98 99 int main() {100 101 #ifndef ONLINE_JUDGE102 freopen("in.txt", "r", stdin);103 //freopen("out.txt", "w", stdout);104 #endif105 //iostream::sync_with_stdio(false);106 solve();107 return 0;108 }
（字典树）HDU - 1247 Hat’s Words
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。