LOOKUP (Trie)

/// --- from trieboi with love ---
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define task "LOOKUP"
using namespace std;
using ll = long long;
using ld = long double;

const int N = 3e4 + 2;
int n, q;
const int Inf = 1e7;

struct Trie{
    Trie *child[27];
    vector<int> take;
    int endhere;
    Trie() {for(int i = 0; i < 27; ++i)child[i] = NULL;endhere = Inf;}
    void Add(int id, string &s, int &v){
        if(id == s.size()){
            endhere = min(endhere, v);
            take.push_back(v);
            return;
        }
        if(!child[s[id] - 'a'])
            child[s[id] - 'a'] = new Trie;
        child[s[id] - 'a'] -> Add(id + 1, s, v);
        take.push_back(v);
    }
    int first(int id, string &s){
        if(id == s.size()){
            return endhere;
        }
        if(!child[s[id] - 'a'])
            return Inf;
        return child[s[id] - 'a'] -> first(id + 1, s);
    }
    int count(int id, string &s, int &first){
        int ans = upper_bound(take.begin(), take.end(), first) - take.begin();
        if(id == s.size())
            return ans;
        if(!child[s[id] - 'a'])
            return ans;
        return child[s[id] - 'a'] -> count(id + 1, s, first) + ans;
    }
};

Trie beg;

void Read(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        string s;
        cin >> s;
        beg.Add(0, s, i);
    }
    cin >> q;
}

void Solve(){
    string s;
    cin >> s;
    int first = beg.first(0, s);
    //cerr << "first: " << first << "\n";
    cout << beg.count(0, s, first)<< "\n";
}

int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0); if(fopen(task".INP", "r"))
    freopen(task".INP", "r", stdin),
    freopen(task".OUT", "w", stdout);
    Read();
    while(q--)
        Solve();
}