首页 > 代码库 > hdu 1247 Hat’s Words(字典树)
hdu 1247 Hat’s Words(字典树)
题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1247
题意:给你一系列字符串问你哪些字符串可以由已知的两个字符串组成,输出该字符串。
还是一道字典树,稍微涉及到一些搜索依旧简单。
#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int M = 5e4 + 10;char s[M][100];struct TnT { TnT *next[27]; int v; TnT():v(0) { memset(next , 0 , sizeof(next)); }};void build(TnT *root , char s[]) { int len = strlen(s); TnT *p = root; for(int i = 0 ; i < len ; i++) { int id = s[i] - ‘a‘; if(p->next[id] == NULL) { p->next[id] = new TnT; } p = p->next[id]; } p->v = 1;}int find(TnT *root , char s[] , int st , int flag) { int len = strlen(s); TnT *p = root; int temp = 0; for(int i = st ; i < len ; i++) { int id = s[i] - ‘a‘; if(p->next[id] == NULL) { temp = 1; break; } if(p->next[id]->v == 1 && flag == 0 && i != len - 1) { int gg = find(root , s , i + 1 , flag + 1); if(gg == 1) { return 1; } } p = p->next[id]; } if(temp == 1) { return 0; } else { if(flag == 1 && p->v == 1) { return 1; } else { return 0; } }}void de(TnT *root) { if(root == NULL) { return ; } else { for(int i = 0 ; i < 26 ; i++) { de(root->next[i]); } } delete root;}int main(){ int count = 0; TnT *root = new TnT; while(scanf("%s" , s[count]) != EOF) { build(root , s[count++]); } for(int i = 0 ; i < count ; i++) { int gg = find(root , s[i] , 0 , 0); if(gg) { printf("%s\n" , s[i]); } } return 0;}
hdu 1247 Hat’s Words(字典树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。