字典树。关于字典树，这个博客把这道题讲的很好。点击打开链接
这里这个图很好
#include<cstdio> #include<cstring> const int maxn = 50000 + 5; char words[maxn][100]; struct node { bool is; node *nex[27]; node() { is = false; memset(nex, 0, sizeof(nex)); } }; void build_tree(char *str, node *rt) { int len = strlen(str); node *p = rt; for(int i = 0; i < len; i++) { int pos = str[i] - 'a'; if(p->nex[pos] == NULL) { p->nex[pos] = new node(); } p = p->nex[pos]; } p->is = true; } int search_str(char *str, node *rt) { int top = 0; node *p = rt; int Stack[100]; int len = strlen(str); for(int i = 0; i < len; i++) { int pos = str[i] - 'a'; if(p->nex[pos] != NULL) p = p->nex[pos]; if(p->is == true) Stack[++top] = i; } while(top >= 1) { p = rt; int pos = Stack[top--]; int flag = true; for(int i = pos + 1; i < len; i++) { int t = str[i] - 'a'; if(p->nex[t] != NULL) p = p->nex[t]; else {flag = false; break;} } if(p->is == true && flag) return true; } return false; } int main() { //ofstream fout ("test.out"); //ifstream fin ("test.in"); node *rt = new node(); int cnt = 0; while(scanf("%s", words[cnt]) == 1) { build_tree(words[cnt], rt); cnt++; } for(int i = 0; i < cnt; i++) { if(search_str(words[i], rt)) { printf("%s\n", words[i]); } } return 0; }
