aho - corasick

string str;string s[MAX];int n,len,exist[MAX];

struct trie{

  trie *next[280];
  trie *suff;
  trie *output;
  int vis;
  int pt;
  vector<trie *>vec;
  trie(){
    for(int i = 0;i<270;i++){

        next[i] = NULL;
    }
    vec.clear();
    suff = NULL;
    output = NULL;
    pt = 0;vis = 0;
  }


  ~trie() {
        for (int i=0; i<270; i++) {
            if (next[i] != NULL && next[i] != this)
            {
                delete next[i];
            }
        }
    }
}*root;

void Insert(string t,int pos){
    trie *curr = root;
    for(int i = 0;i<(int)t.length();i++){

        int id = t[i] - '0' + 10;
        if(curr->next[id]==NULL){

            curr->next[id] = new trie();
        }
        curr = curr->next[id];

    }
}

void failure(){
    queue<trie *>q;
    q.push(root);
    while(!q.empty()){
        trie *curr = q.front();
        q.pop();
        for(int c = 0;c<270;c++){
            int id = c;
            if(curr->next[id]){

                if(curr==root){

                    curr->next[id]->suff = root;
                }
                else {
                    trie *tmp = curr;
                    while(tmp->suff!=NULL){

                        if(tmp->suff->next[id]){

                            curr->next[id]->suff = tmp->suff->next[id];
                            curr->next[id]->suff->vec.pb(curr->next[id]);
                            break;
                        }
                        tmp = tmp->suff;
                    }
                    if(tmp->suff==NULL)curr->next[id]->suff = root;

                }

                q.push(curr->next[id]);

            }
        }
    }
}

void dfs(trie *curr){

    if(curr->vis||curr==root||!curr)return ;
    curr->vis = 1;
    for(int i = 0;i<(int)curr->vec.size();i++){

        dfs(curr->vec[i]);
        if(curr->vec[i])
        curr->pt+=curr->vec[i]->pt;
    }


}

void Search(){
    int indx = 0;
    trie *curr = root;
    while(indx<len){
        int id = str[indx] - '0' + 10;
        while(curr!=root&&curr->next[id]==NULL)curr = curr->suff;
        if(curr->next[id]){
            curr = curr->next[id];
            curr->pt++;
        }

        indx++;
    }
}


int main()
{
   /// booster()
    ///read("input.txt");


    root = new trie();


    cin>>n;
    for(int i = 0;i<n;i++){

        cin>>s[i];
        Insert(s[i],i);
    }
//        printf("%s\n",str);
//        for(int i = 0;i<n;i++)printf("%s\n",s[i]);
    failure();
    int w;
    cin>>w;
    for(int i = 0;i<w;i++)
    {
        cin>>str;
        len = str.length();
        Search();
    }

    for(int i = 0;i<n;i++){

        int len2 = s[i].length();
        trie *curr = root;
        for(int j = 0;j<len2;j++){
            int id = s[i][j] - '0' +10;
            if(curr->next[id])
            curr = curr->next[id];

        }
        trie *cur = curr;
        if(curr){

            dfs(curr);
            exist[i]+=cur->pt;
        }

    }


    for(int i = 0;i<n;i++){
        cout<<exist[i]<<endl;
    }

    delete root;



    return 0;
}