C++代码

#include<iostream>
using namespace std;
const int N = 1000010;
int n, m;
int son[N][26], idx;
char str[N];
int cnt[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]) break;
        p = son[p][u];
        // cout << "i:" << i << "\tcnt[p]" << cnt[p] << endl;
        //如果存在以当前字母为结尾的str，结果加上这些str的个数
        if(cnt[p]) res += cnt[p];
    }
    return res;
}


int main(){
    cin >> n >> m;
    for(int i = 0; i < n; ++i){
        cin >> str;
        insert(str);
    }
    while(m--){
        cin >> str;
        int res = query(str);
        cout << res << endl;
    }
    return 0;
}