题解 | 【模板】Trie 字典树

字典树算法讲解可以看其他题解 这里给出一版比较简单的代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const int N=1e6+1;
char s[N];
int ch[N][70],cnt[N],idx;
void insert(string s){
    int p=0;
    for(int i=0;s[i];i++){
        int j;
        j=s[i]-'A';
        if(!ch[p][j]){
            ch[p][j]=++idx;
        }
        p=ch[p][j];
        cnt[p]++;
    }
    //cnt[p]++;
}
int query(string s){
    int p=0;
    for(int i=0;s[i];i++){
        int j=s[i]-'A';
        if(!ch[p][j]) return 0;
        p=ch[p][j];
    }
    return cnt[p];
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,q;
    cin >> n >> q;
    for(int i=0;i<n;i++){
        string s;
        cin >> s;
        insert(s);
    }
    for(int i=0;i<q;i++){
        string x;
        cin >> x;
        cout << query(x) << '\n';
    }
}