我必须为 C++ 中的应用程序编写一个程序，该程序生成需要存储以供进一步处理的 n 位二进制字符串。
问题1）但是每当生成一个新字符串时，都需要检查它是否已经存在于数据库中。如果是，则不应添加。
我可以做的一种可能的方法是维护一个用于查找的哈希表（例如 STL 映射），其中键是二进制字符串的十进制值。但问题是 n 可能非常大，以至于存储它的十进制值是不可行的。有时 n 可以大到 200+ 。
此外，有时 n 位字符串的位是未指定的。例如：- 如果 n = 4，则字符串的格式可能为 01xx。其中低两位未指定。在这种情况下， 01xx 实际上表示 4 个完全指定的 4 位字符串 - 0100,0101,0110,0111。因此，如果 01xx 在数据库中并且生成了 0110，则不应将 0110 存储在数据库中。
你能建议什么可能是检查这一点的有效方法吗？
有时我能想到的是：-
1) 查找整个数据库的字符串，将新生成的字符串与数据库中的字符串一一进行比较。这是一种简单的方法，复杂度为 O(mn)，其中 m 是当前数据库中的字符串数。
2）将字符串存储在二叉决策树类型结构中。在这种类型的方法中，查找将是对数的？
3）对于字符串中的每个位位置 - 我将字符串存储在指定其值的位置。例如：- 对于 n = 4，如果数据库包含：- 01xx 和 1xx1，则此信息可以存储为：-
0 - 1xx1
1 -
2 - 01xx
3 - 01xx,1xx1
0 表示设置了 LSB。3 表示设置了 MSB。因此，如果生成了一个新字符串 0101，我可以在 2 或 3 中搜索它。这种方法在内存使用上似乎很昂贵。
你能建议一些有效的方法来进行这个字符串搜索吗？
问题 2）同样就 C++ 实现而言，存储这些 n 位字符串的有效方法可能是什么？应该注意的是，大多数时候 n 位字符串中的大多数位是未指定的。因此，与其在内存中保留与 n 成比例的空间，不如仅存储指定的位更有意义。
也就是说，n 可能是 10。但生成的字符串可能类似于：- 1x1xxxxxxx。在这种情况下，存储类似 {(9,1),(7,1)} 的内容更有意义。那么我应该将字符串存储为 2-tuples 的向量吗？在这种情况下，存储这些字符串的数据库的好方法是什么？