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\n", query(buf, root));}return 0; }

总结

以上是生活随笔为你收集整理的Trie树统计单词前缀的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。