给定 N 个字符串 S₁,S₂…S_N，接下来进行 M 次询问，每次询问给定一个字符串 T，求 S₁∼S_N 中有多少个字符串是 T 的前缀。

输入字符串的总长度不超过 10⁶，仅包含小写字母。

输入格式
第一行输入两个整数 N，M。

接下来 N 行每行输入一个字符串 S_i。

接下来 M 行每行一个字符串 T 用以询问。

输出格式
对于每个询问，输出一个整数表示答案。

每个答案占一行。

输入样例：

3 2
ab
bc
abc
abc
efg

输出样例：

2
0

参考答案

#include<bits/stdc++.h>
#define N 1000010
using namespace std;

typedef struct Node{
    int tail=0; //字符串结尾
    vector<Node*> next;
    vector<int> cnt;
    Node(){
        next.assign(26, NULL);
        cnt.assign(26, 0);
    }
};

Node *root = new Node();
int n,m;

void insert(string s){
    Node* p=root;
    for(int i=0;i<s.size();i++){
        int ch = s[i]-'a';
        if(!p->next[ch]) p->next[ch]=new Node();
        p->cnt[ch]++;
        p = p->next[ch];
    }
    p->tail++;
}

int search(string s){
    Node *p = root;
    int ans = 0;
    for(int i=0;i<s.size();i++){
        int ch = s[i]-'a';
        ans += p->tail;
        if(!p->next[ch]) return ans;
        p = p->next[ch];
    }
    ans += p->tail;
    return ans;
}

int main(){
    cin>>n>>m;
    string s;
    for(int i=0;i<n;i++){
        cin>>s;
        insert(s);
    }
    for(int i=0;i<m;i++){
        cin>>s;
        int res = search(s);
        cout<<res<<endl;
    }
    return 0;
}