Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

输入

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.

输出

对于每个提问,给出以该字符串为前缀的单词的数量.

样例输入

banana
band
bee
absolute
acm

ba
b
band
abc

样例输出

2
3
1
0

题解

所以，所谓的字典树就是把一个字符串都存进一棵树，每个节点都放一个字符。所以，对于每个节点至多会有 26个子节点。
然后我们可以在节点上存一点别的玩意，来满足题目想要的效果。
比如说， end 表示这是最后一个字符，那么从根节点到这个节点所经过的字符就正好构成了这个
词。
count 表示这个字符在同样的位置出现了多少次。
etc.

代码

#include<bits/stdc++.h>
#include <stdio.h>
struct node {
    bool end;
    node * children[26];
    int count = 0;
    ~node() {
        for (int i = 25; i >= 0; i--)
        {
            if(this->children[i] != NULL) {
                this->children[i]->~node();
                delete this->children[i];
            }
        }
    }
    node() {
        end = false;
        for(int i = 0; i < 26; i++)
            children[i] = NULL;
    }
};
node * root;
/**
 * 插入一个新的字符串
 * @param str 字符串数组
 * @param len 字符串长度
 **/
void insert(char* str, int len) {
    if(!root) {
        root = new node;
    }
    node *location = root;
    for(int i = 0; i < len; i++) {
        if(str[i] == 0 || str[i] == '\n') continue;
        int id = str[i] - 'a';
        if(location->children[id] == NULL) {
            location->children[id] = new node;
        }
        location = location->children[id];
        location->count++;
    }
    location->end = true;
}
/**
 * 查找指定字符串在树中的长度
 * @param str 字符串数组
 * @param len 字符串长度
 **/
int search(char * str, int len) {
    node * location = root;
    for (int i = 0; i < len; i++)
    {
        int id = str[i] - 'a';
        if(location->children[id] == NULL)
            return 0;
        location = location->children[id];
    }
    return location->count;
}
char str[20];
int main() {
    while (1)
    {
        fgets(str, 15, stdin);
        int len = strlen(str);
        if(len == 1) {
            break;
        }
        insert(str, len);
    }
    while (~scanf("%s", str))
    {
        int len = strlen(str);
        if(len == 0) {
            break;
        }
        printf("%d\n", search(str, len));
    }
    
}