确定位置

• 查表：以h对应的uint32数为下标，构建数组，通过查表方式得到，但h最大为$2^{31}$，直接构建数组不现实
• 哈希：再增加一层映射，$f(g(h)) \rightarrow 0\sim 31$，即找到一个hash函数$g$，先将$h$映射到$0 \sim 31$，再通过查表$0\sim 31 \rightarrow 0\sim 31$，但一般哈希会涉及到取余操作，还要考虑不要有碰撞

德布鲁因序列（De Bruijn sequence）

wiki上的定义如下，

In combinatorial mathematics, a de Bruijn sequence of order $n$ on a size-$k$ alphabet) A is a cyclic sequence in which every possible length-$n$ string#Formal_theory) on $A$ occurs exactly once as a substring (i.e., as a contiguous subsequence). Such a sequence is denoted by $B(k, n)$ and has length $k^n$, which is also the number of distinct strings of length $n$ on $A$.

——from wiki De Bruijn sequence

德布鲁因序列的使用

h与德布鲁因序列相乘，相当于左移操作，把某位置的子串移到了最左端，再将该子串右移至最右，即仅保留该子串，可知道该子串是什么，因为序列中每个子串的位置都是唯一的，根据映射关系可知道该子串的位置，相当于知道了h。为此需要建立 子串与位置 对应关系的检索表。

0%