Fork me on GitHub

前缀树

发表于 | 次阅读
字数统计: 242 | 阅读时长 ≈ 1

前缀树介绍

解析 https://blog.csdn.net/weixin_39778570/article/details/81990417?utm_medium=distribute.pc_relevant.none-task-blog-baidujs-2

简单功能实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;

typedef struct node{
    bool terminal = 0;
    map<char , node*> child;
}node , *tree;

void Insert(tree &t , string s){  //建树
    int len = s.size();
    for(int i = 0 ; i<len ; ++i){
        if(!((t->child).count(s[i]))){
            //cout<<s[i]<<endl;
            tree t1 = new node;
            (t->child)[s[i]] = t1;
        }
        t = (t->child)[s[i]];
    }
    t->terminal = 1;  //表示字符串在这一节点的结束
}

bool Search(tree t , string s){
    int len = s.size();
    for(int i = 0 ; i<len ; ++i){
        if(!(t->child).count(s[i])){
            return false;
        }
        t = t->child[s[i]];
    }
    return t->terminal;
}

int main()
{
    tree t = new node;
    int n;
    cin>>n;
    tree t1 = t;
    for(int i = 0 ; i<n ; ++i){
        string s;
        cin>>s;
        t = t1;
        Insert(t , s);
    }
    t = t1;
    cin>>n;
    for(int i = 0 ; i<n ; ++i){
        string s;
        cin>>s;
        cout<<Search(t , s)<<endl;
    }
}