首页 > 代码库 > 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(字典树)