I'm looking for a data structure / algorithm to store an unordered set S
of binary strings of a fixed length n
(i.e. all matching the following regular expression: [01]{n}
).
Insertion and lookup ("Is element x
in the S
?") should maximally take polynomial time to |S|
.
The space complexity should be logarithmic to |S|
for large sets. In other words, the space should not be exponential to n
if for example 2^n / 2
random and unique strings are inserted, but polynomial to n
.
Is such a thing known to exist?