字典树trie

dw_dz · 2025-05-12 22:19:44 · 算法·理论

字典树

字典树,顾名思义就是像字典一样的树,用于存储,查找字符串. 存储:

void insert(string s) {
    int p=0;
    for(char c:s) {
        int i=c-'a';
        if(!tr[p][i]) tr[p][i]=++tot;
        p=tr[p][i];
    }num[p]++;
}

查询:

int ask(string s) {
    int res=0,p=0;
    for(char c:s) {
        int i=c-'a';
        if(!tr[p][i]) return res;
        p=tr[p][i];res+=num[p];
    }return res;
}