字典树模板

P8306 【模板】字典树

//按照前缀进行分类总结
//字符串的总长度是多少，也就最多有多少种前缀
#include <bits/stdc++.h>
using namespace std;
const int M=3e6+5;

char s[M];
int trie[M][65],tag[M],tot;
map<char,int>mp;

void insert(char s[]) {
    int len=strlen(s+1),p=0;
    for(int i=1;i<=len;i++) {
        if(trie[p][mp[s[i]]]==0)trie[p][mp[s[i]]]=++tot;
        p=trie[p][mp[s[i]]];
        tag[p]++;
    }
}

int query(char s[]) {
    int len=strlen(s+1),p=0;
    for(int i=1;i<=len;i++) {
        if(trie[p][mp[s[i]]]==0)return 0;
        p=trie[p][mp[s[i]]];
    }
    return tag[p];
}

void init1() {
    int idx=0;
    for(char i='a';i<='z';i++)mp[i]=++idx;
    for(char i='A';i<='Z';i++)mp[i]=++idx;
    for(char i='0';i<='9';i++)mp[i]=++idx;
}

void init2() {
    for(int i=0;i<=tot;i++)
        for(int j=0;j<=64;j++)
            trie[i][j]=0;
    for(int i=0;i<=tot;i++)tag[i]=0;
    tot=0;
}

int main() {
    init1();
    int TT;cin>>TT;
    while(TT--) {
        int n,m;
        cin>>n>>m;
        init2();
        while(n--) {
            scanf("%s",s+1);
            insert(s);
        }
        while(m--) {
            scanf("%s",s+1);
            cout<<query(s)<<'\n';
        }
    }
    return 0;
}