Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2391????Accepted Submission(s): 873
?
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.?
Output Your output should contain all the hat’s words, one per line, in alphabetical order.a ahat hat hatword hziee wordSample Output
ahat hatword?
#include <iostream> #include <stdio.h> #include <cstring> #include <string> using namespace std; char sh[50005][20]; struct node { bool flag; node *next[26]; }; node *root, memory[5000005]; int cnt = 0; node *create() { node *p = &memory[cnt++]; int i; for(i = 0; i < 26; i++) { p->next[i] = NULL; } p->flag = false; return p; } void insert(char *s) { node *p = root; int i, k; for(i = 0; s[i]; i++) { k = s[i] - 'a'; if(p->next[k] == NULL) { p->next[k] = create(); } p = p->next[k]; } p->flag = true; } bool search(char *s) { int i, j, k; bool tar; for(i = 0; s[i]; i++) { node *p = root; for(j = 0; j < i; j++) { k = s[j] - 'a'; p = p->next[k]; } if(p->flag == 1) { node *q = root; tar = true; for(j = i; s[j]; j++) { k = s[j] - 'a'; if(q->next[k] == NULL) { tar = false; break; } q = q->next[k]; } if(q->flag == 1 && tar) { return true; } } } return false; } int main() { int i, n; root = create(); i = 0; while(scanf("%s", sh[i]) != EOF) { insert(sh[i]); i++; } n = i; for(i = 0; i < n; i++) { if(search(sh[i])) { printf("%s\n", sh[i]); } } return 0; }