当前位置：网站首页>字典树笔记（自用）

字典树笔记（自用）

2022-07-29 14:23:00 【阐上】

字典树，顾名思义跟字典有关

建树，每个结点连接其他点的时候，这个连接有字典的性质。

插入insert

二进制字典树

int tr[N * 31][2], tdx;
void insert(int x) {
    
    int p = 0;
    for (int j = 30; j >= 0; j--) {
    
        int u = (x >> j & 1);
        if (!tr[p][u])tr[p][u] = ++tdx;
        p = tr[p][u];
    }
}

字母、有限数字字典树

int tr[N * 26][26], tdx;
void insert(int x, string & s) {
    
    int p = 0;
    for (int i = 0; i < s.size(); i++) {
    
        int u = s[i] - 'a';
        if (!tr[p][u])tr[p][u] = ++tdx;
        p = tr[p][u];
    }
    //cnt[p]++ 记录该位置有一个串
}

第一维的大小取决于给定字母、数字个数

dfs遍历

//step是传入的深度，配合获取信息
int dfs(int x, int step) {
    
    int l = tr[x][0], r = tr[x][1];
    if (!l && !r)return 0;
    else if (!l) return dfs(r, step - 1);
    else if (!r)return dfs(l, step - 1);
    else {
    
        return min(dfs(l, step - 1), dfs(r, step - 1)) + (1 << step);
    }
}

int find(int x) {
    
    int p = 0, res = 0;
    for (int j = 31; j >= 0; j--) {
    
        int u = x >> j & 1;
        if (son[p][u ^ 1]) {
    
            res += 1 << j;
            p = son[p][u ^ 1];
        }
        else p = son[p][u];
    }
    return res;
}