Trie树统计单词前缀

输入

输入的第一行为一个正整数n。表示词典的大小,其后n行,每一行一个单词(不保证是英文单词,也有可能是火星文单词哦)。单词由不超过10个的小写英文字母组成,可能存在同样的单词。此时应将其视作不同的单词。接下来的一行为一个正整数m。表示小Hi询问的次数,其后m行。每一行一个字符串。该字符串由不超过10个的小写英文字母组成,表示小Hi的一个询问。

输出

对于小Hi的每个询问。输出一个整数Ans,表示词典中以小Hi给出的字符串为前缀的单词的个数。

例子输入
5
babaab
babbbaaaa
abba
aaaaabaa
babaababb
5
babb
baabaaa
bab
bb
bbabbaab
例子输出
1
0
3
0
0


#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int N, M;
char buf[12];
struct  Node {
    Node *next[26];
    int num;
};

Node *CreatNode() {
    Node *p = (Node *)malloc(sizeof(Node));
    p->num = 0;
    memset(p->next, 0, sizeof(p->next));
    return p;
}

void Insert(char *str, Node *p) {
    int id;
    for( ; *str; ++str) {
        id = *str - 'a';
        if(p->next[id] == NULL)
            p->next[id] = CreatNode();
        p = p->next[id];
        ++p->num;
    }
}

int query(char *str, Node *p) {
    int id;
    for( ; *str; ++str) {
        id = *str - 'a';
        p = p->next[id];
        if(p == NULL)
            return 0;
    }
    return p->num;
}

int main() {
    int i, j;   
    Node *root = CreatNode();
    scanf("%d", &N);
    while(N--) {
        scanf("%s", buf);
        Insert(buf, root);
    }
    scanf("%d", &M);
    while(M--) {
        scanf("%s", buf);
        printf("%d
", query(buf, root));
    }
    return 0;
}


原文地址:https://www.cnblogs.com/mfmdaoyou/p/6714358.html