Trie字典树【模板】

hexuchen · 2025-02-22 10:47:48 · 算法·理论

int trie[M][110],ans[M],num=0;
int get_num(char c){
    if('a'<=c && 'z'>=c){
        return c-'a'+1;
    }
    if('A'<=c && 'Z'>=c){
        return 27+c-'A';
    }
    if('0'<=c && '9'>=c){
        return 53+c-'0';
    }
}
void insert(string str){
    int v=0,len=str.size();
    for(int i=0;i<len;i++){
        int c=get_num(str[i]);
        if(!trie[v][c]){
            trie[v][c]=++num;
        }
        v=trie[v][c];
        ans[v]++;
    }
}
int find(string str){
    int v=0,len=str.size();
    for(int i=0;i<len;i++){
        int c=get_num(str[i]);
        if(!trie[v][c]){
            return 0;
        }
        v=trie[v][c];
    }
    return ans[v];
}