[技巧] 「禁用哈希表」后也可以写出「线性空间」的字典树！

Felix72 · 2025-12-07 19:03:34 · 算法·理论

这个技巧不是很有用，估计就卡常时会用到，但是很有意思就记录下来了。

字典树的常规写法是 O(n\sum) 空间的，字符集较大时不是很好。

但是七步之内必有解药，使用 \text{unordered\_map} 即可在 O(n) 空间内完成建树。不过这样随机访问的常数有点大，换成手写哈希可能会嫌麻烦。

所以这里推出一种很鸡肋的压位方法，可以在字符集不大于 64 时使得存儿子的空间变为 O(n)，且常数较小。具体地，我们构造一个 \text{ull} 类型数组 tmp，tmp_{i, j} 表示节点 i 是否存在 j 字符的儿子，其中 0 \leq j < 64。再构造 n 个动态数组 son 存储邻接表。插入和访问的操作如下：

• 访问节点 p 的字符 c 对应的儿子时，先用 \text{popcount} 函数求出 c 对应的儿子是第几个儿子，再在 son 里面随机访问即可，复杂度 O(1)；
• 新增儿子时，用同样的方法计算出排名，再用 \text{vector} 的 \text{insert} 函数插入即可。

动态数组的插入常数很小，因此我们在几乎不牺牲时间的情况下实现了不用哈希表的，O(n) 空间的字典树。

模板题代码如下：

/* 省选：2026.3.7 */
/* K_crane x N_cat */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int N = 3000010, L = 3000010;
typedef unsigned long long ull;
int T, n, m; string str[N];

inline int id(char c) {return (('A' <= c && c <= 'Z') ? (c - 'A') : (('a' <= c && c <= 'z') ? (26 + c - 'a') : (52 + c - '0')));}
ull tmp[L]; int cnt[L], idx; vector < int > son[L];
// tmp 表示节点 i 的第 j 个字符是否有对应儿子（压位） 
// cnt 是结束标记，son 是邻接表 

inline void init(int pos)
{
    // 对 cnt 数组做子树和 
    for(int to : son[pos]) init(to), cnt[pos] += cnt[to];
}
inline int get_rank(int p, int c)
{
    // 字符 c 算节点 p 的第几个儿子 
    return __builtin_popcountll(((1ull << c) - 1) & tmp[p]) + 1;
    // 要写 popcountll，popcount 不能数 ull 中 1 的个数 
}

inline void sol()
{
    cin >> n >> m;

    // 多测清空 
    for(int i = 1; i <= idx; ++i) tmp[i] = cnt[i] = 0, son[i].clear();
    idx = 1;

    for(int i = 1; i <= n; ++i)
    {
        cin >> str[i]; int p = 1;
        for(char c : str[i])
        {
            if(!(tmp[p] & (1ull << id(c))))
            {
                tmp[p] |= (1ull << id(c));
                int rk = get_rank(p, id(c));
                ++idx;
                son[p].insert(son[p].begin() + rk - 1, idx);
            }
            p = son[p][get_rank(p, id(c)) - 1];
        }
        ++cnt[p];
    }

    init(1);

    for(int i = 1; i <= m; ++i)
    {
        string t; cin >> t; int p = 1;
        for(char c : t)
        {
            if(tmp[p] & (1ull << id(c)))
                p = son[p][get_rank(p, id(c)) - 1];
            else {p = 0; break;}
        }
        cout << cnt[p] << '\n';
    }
}

int main()
{
//  freopen("text.in", "r", stdin);
//  freopen("prog.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while(T--) sol();
    return 0;
}
/*

*/