字典树

字典树

#include<bits/stdc++.h>
using namespace std;
int cnt = 0;
struct node{
    int num;
    int data[27];
    void init(){
        for(int i = 0;i<26;i++){
            data[i]= -1;
        }
        num = 0;
    }
}tree[1010];

void buildtree(string s){
    int p = 0;
    for(int i = 0;i<s.length();i++){
        int x = s[i]-'a';
        if(tree[p].data[x]==-1){
            tree[p].data[x] = ++cnt;
            tree[cnt].init();
        }
        p = tree[p].data[x];
        tree[p].num++;
    }
}

int quest(string s){
    int p=0;
    for(int i = 0;i<s.length();i++){
        int x = s[i]-'a';
        if(tree[p].data[x]==-1){
            return 0;
        }
        p = tree[p].data[x];
    }
    return tree[p].num;
}

int main(){
    tree[cnt].init();
    int t;
    cin>>t;
    while(t--){
        string ss;
        cin>>ss;
        buildtree(ss);
    }
    cin>>t;
    while(t--){
        string ss;
        cin>>ss;
        cout<<quest(ss)<<endl;
    }
    return 0;
}