Hat’s Words
Time Limit:1000MSMemory Limit:32768KB64bit IO Format:%I64d & %I64u
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
aahathathatwordhzieeword
Sample Output
ahathatword
字典树，找出符合由另外两个单词组合成的单词，调试记得用Ctrl+Z，看注释。
#include<iostream>#include<cstring>#include<string>#include<cstdio>#include<stack>using namespace std;const int MAXN = 50000 + 50;struct tree{tree *child[26];int isend;tree(){for (int i = 0; i < 26; i++)child[i] = NULL;isend = 0;}};void insert(char *str, tree *p){for (int i = 0; str[i]; i++){int num = str[i] – 'a';if (p->child[num] == NULL)p->child[num] = new tree();p = p->child[num];}p->isend = 1;//单词结束位置isend置为1}bool find(char *str, tree *root){int i;tree *p = root;for (i = 0; str[i]; i++){int num = str[i] – 'a';// if (p->child[num]==NULL)//这句在本题没什么意义，因为找的都是字典树中的单词// return false;p = p->child[num];if (p->isend && str[i])//出现单词前面一段是另一个单词的情况，判断后面一段是不是字典树中的单词，，是就返回true{int ok = 1;tree *q = root;for (int j = i+1; str[j]; j++){int num = str[j] – 'a';if (q->child[num] == NULL) //不符合，滚粗{ok = 0;break;}q = q->child[num];}if (q->isend && ok) //一定要判断最后一个字母是不是字典树中一个单词的结束。return true;}}return false;}char str[MAXN][20];int main(){int cnt = 0;tree *root = new tree();while (scanf("%s",str[cnt])!=EOF){insert(str[cnt], root);cnt++;}for (int i = 0; i < cnt; i++){if (find(str[i], root))cout << str[i] << endl;}}
再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。
