Hat’s Words

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13752????Accepted Submission(s): 4919

Problem Description A hat’s word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.
You are to find all the hat’s words in a dictionary.

?

Input Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 50,000 words.
Only one case.

?

Output Your output should contain all the hat’s words, one per line, in alphabetical order.

?

Sample Input a ahat hat hatword hziee word

?

Sample Output ahat hatword

?

Author 戴帽子的 解析：字典樹。 #include <cstdio> #include <cstring>char s[50005][50];struct Node{Node* pt[26];bool isEnd; };Node* root; Node memory[100000]; int allo;void trie_init() {memset(memory, 0, sizeof(memory));allo = 0;root = &memory[allo++]; }void trie_insert(char str[]) {Node *p = root;for(int i = 0; str[i] != '\0'; ++i){int id = str[i]-'a';if(p->pt[id] == NULL){p->pt[id] = &memory[allo++];}p = p->pt[id];}p->isEnd = true; }bool trie_find(char str[]) {Node *p = root;for(int i = 0; str[i] != '\0'; ++i){int id = str[i]-'a';if(p->pt[id] == NULL){return false;}p = p->pt[id];}return p->isEnd; }void getans(char str[]) {Node* p = root;for(int i = 0; str[i] != '\0'; ++i){int id = str[i]-'a';if(p->pt[id] == NULL){return;}else{if(p->pt[id]->isEnd && str[i+1] != '\0'){bool ok = trie_find(str+i+1);if(ok){printf("%s\n", str);return;}}}p = p->pt[id];} }void solve(int n) {trie_init();for(int i = 0; i < n; ++i){trie_insert(s[i]);}for(int i = 0; i < n; ++i){getans(s[i]);} }int main() {int n = 0;while(gets(s[n])){++n;}solve(n);return 0; }

　　

轉載于:https://www.cnblogs.com/inmoonlight/p/5921071.html

總結

以上是生活随笔為你收集整理的HDU 1247 Hat’s Words的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。