Trie树模板

#include<bits/stdc++.h>
using namespace std;
struct Trie
{
    int word[100020<<2][26];
    int ex[100020<<2];
    int sz;
    Trie()
    {
        sz=1;
        memset(word,0,sizeof(word));
        memset(ex,0,sizeof(ex));
    }
    void insert(char *s)
    {
        int u=0;
        int c;
        int len=strlen(s);
        for(int i=0;i<len;i++)
        {
            c=s[i]-'a';
            if(!word[u][c])
                word[u][c]=sz++;
            u=word[u][c];
            ex[u]++;
        }
    }
    int search(char *s)
    {
        int u=0;
        int c;
        int len=strlen(s);
        for(int i=0;i<len;i++)
        {
            c=s[i]-'a';
            if(word[u][c])
                u=word[u][c];
            else
                return 0;
        }
        return ex[u];
    }
}w;
int main()
{
    int n,m;
    char s[20];
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s);
        w.insert(s);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",s);
        printf("%d\n",w.search(s));
    }
    return 0;
}