模板来源:HKer_YM的博客
1.指针建树

struct node {
    node* child[MAXN];
    int flag;
    node() {
        memset(child, NULL, sizeof(child));
        flag = 1;
    }
};

void insert(char *str, node* root) {
    int len = strlen(str);
    node* tmp = root, *q;
    for(int i = 0; i <len; i++) {
        int id = str[i] - 'a';
        if(tmp->child[id] == NULL) {
            q = new node();
            tmp->child[id] = q;
            tmp = tmp->child[id];
        } else {
            tmp = tmp->child[id];
            ++(tmp->flag);
        }
    }
}
int query(char *str, node* root) {
    int len = strlen(str);
    node* tmp = root;
    for(int i = 0; i < len; i++) {
        int id = str[i] - 'a';
        tmp = tmp->child[id];
        if(tmp == NULL) return 0;
    }
    return tmp->flag;
}

2.数组建树

void insert(int val) {
    int len = strlen(s);
    int rt = root;
    for(int i = 0; i < len; i++) {
        int id = s[i] - 'a';
        if(tree[rt][id] == 0) {
            tree[rt][id] = ++cnt;
        }
        rt = tree[rt][id];
    }
    ans[rt] = val;
}
int query() {
    int len = strlen(s);
    int rt = root;
    for(int i = 0; i < len; i++) {
        int id = s[i] - 'a';
        if(tree[rt][id] == 0) return -1;
        rt = tree[rt][id];
    }
    return (ans[rt] == 0 ? -1 : ans[rt]);
}