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.
InputStandard 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. OutputYour output should contain all the hat’s words, one per line, in alphabetical order.Sample Inputaahathathatwordhzieeword
Sample Output
ahathatword 题目大意 ：给你很多字符串，然后让你找出作为连接字符串连接的字符串有哪些。 题目分析 ：很典型的一道字典树的题目，但还是不要轻易的套用公式，我们要清楚我们动作的每一步，因为我们要理解字典树的到底是怎样 的一种模型，这样才能变通。字典树的优点在于可以储存大量的字符，查询速度快。我们这道题就是要求我们求一个字符串拆分来是否还能在 所有字符串中找到一样的。 题目收获 ：算是初步了解该数据结构吧！ AC代码：
#include#include #include #include #include const int LEN = 26;using namespace std;char s[50000][50];typedef struct tire{ bool isword; struct tire *next[LEN];}tire;void insert(tire *root,char *word){ tire *p = root, *q; while (*word!='\0') { if (p->next[*word - 'a'] == NULL) { q = (tire*)malloc(sizeof(tire)); for (int i = 0; i < LEN; i++) q->next[i] = NULL; q->isword = false; p->next[*word - 'a'] = q; } p = p->next[*word - 'a']; word++; } p->isword = true;}bool search(tire *root, char *word){ tire *p = root; for (int i = 0; i < word[i] != '\0'; i++) { if (p == NULL || p->next[word[i] - 'a'] == NULL) return false; p = p->next[word[i] - 'a']; } return p->isword;}int main(){ //freopen("text.txt", "r", stdin); char str[50]; tire *root = (tire*)malloc(sizeof(tire)); for (int i = 0; i < LEN; i++) root->next[i] = NULL; root->isword = false; int time = 0; while (scanf("%s",str)!=EOF) { strcpy(s[time++], str); insert(root, str); } for (int i = 0; i < time; i++) { int len = strlen(s[i]); for (int j = 1; j < len - 1; j++) { char temp1[50] = "\0"; char temp2[50] = "\0"; strncpy(temp1, s[i], j); strncpy(temp2, s[i] + j, len - j); if (search(root, temp1) && search(root, temp2)) { printf("%s\n", s[i]); break; } } } return 0;}