题目描述

给定N个字符串S1,S2…SN，接下来进行M次询问，每次询问给定一个字符串T，求S1～SN中有多少个字符串是T的前缀。

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

输入格式

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

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

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

输出格式

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

每个答案占一行。

输入样例：

3 2
ab
bc
abc
abc
efg

输出样例：

2
0

主要考点

Trie树

C ++ 代码

#include <iostream>

using namespace std;
const int N = 1000010;

int son[N][26], cnt[N], idx;
char s[N], q[N];

void insert(char str[]){
    int p = 0;
    for(int i = 0; str[i]; i ++){
        int u = str[i] - 'a';
        if(!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++;;
}

int  query(char str[]){
    int p = 0, res = 0;
    for(int i = 0; str[i]; i ++){
        int u = str[i] - 'a';
        if(!son[p][u]) return res;
        p = son[p][u];
        res += cnt[p];
    }
    return res;
}

int main(){
    int m, n;
    cin >> n >> m;
    for(int i = 0; i < n; i ++){
        scanf("%s", s);
        insert(s);
    }

    while(m --){
        scanf("%s", q);
        cout << query(q) << endl;
    }

    return 0;
}