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

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

字典树的常规写法是

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)

空间的字典树。

模板题代码如下：

CPP

/* 省选：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;
}
/*

*/

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

文章操作

相关推荐

评论

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