第一次接觸字典樹的實現，先看到了一個指針實現的模板，覺得很好理解，用著也方便，先收集過來 :)

//字典樹用來查詢有公共前綴的單詞有多少個，插入和查詢的時間復雜度均為O（n)

#include<iostream>
#include<cstring>
#define N 300 //有N個單詞
#define M 1000000//有M次查詢
#define kind 26//26個英文字母
using namespace std;
struct Treenode
{
    int count;
    Treenode *next[kind];
    Treenode(){
        for(int i=0; i<kind; i++)
            next[i]=NULL;
        count=1;
    }
};
void insert(Treenode *&root, char *word)
{
    int i=0,j,l=strlen(word),branch;
    Treenode *location=root;
    if(location==NULL){
        location=new Treenode();
        root=location;
    }

    for(i=0; i<l; i++){
        branch=word[i]-'a';
        if(location->next[branch])
            location->next[branch]->count++;
        else
            location->next[branch]=new Treenode();
        location=location->next[branch];
    }
}
int search(Treenode *&root, char *word)
{
    int i, ans=0, l=strlen(word),branch;
    Treenode *location=root;
    if(location==NULL) return 0;
    for(i=0; i<l; i++){
        branch=word[i]-'a';
        if(!location->next[branch])
            return 0;

        location=location->next[branch];
        ans=location->count;
    }
    return ans;
}

int main()
{
    int i,j,n,m;
    char word[50];
    Treenode *root=NULL;
    scanf("%d", &n);
    for(i=0; i<n; i++){
        scanf("%s",word);
        insert(root, word);
    }
    scanf("%d",&m);
    for(i=0; i<m; i++){
        scanf("%s",word);
        printf("%d\n",search(root, word));
    }

    return 0;
}