根据一系列集合检查子集的有效算法

Question

我通读了一些关于确定一个集合是否A是另一个集合的子集的帖子B。但我发现很难确定使用什么算法。以下是问题的概述：

• 我有一个A在程序开始时收到的字符串数组。对该结构知之甚少。数组中的每个字符串可以任意长，条目数不限。尽管通常可以假设数组中的条目数不会太大（< 100）。
• 然后我遍历长度为的对象列表n。
• 每个n对象也将有一个字符串数组B，即会有n B数组。一旦程序运行，Bs 将是固定的，即它们在运行时不会改变。
• 我想确定每个对象是否A是B.

现在，我想到了哈希表。然而，在我看来，它们只有在只有一个B和很多As 时才会有效。然后我可以为我的哈希表创建一个哈希表B并检查每个对象的每个字符串数组。但事实并非如此，因为A除了n Bs只有一个。什么是有效的算法来做到这一点？

例子：

A:  ["A", "G", "T"]
B1: ["C", "G"]
B2: ["K", "A", "U", "T", "G"]
.
.
.
Bn: ["T", "I", "G", "O", "L"]

这A是 的子集，B2但不是B1，而不是Bn。

Answer 1

如您A事先所知，您可以设计一个无冲突哈希函数来对 的所有元素进行哈希处理A。

然后在搜索步骤中仅对哈希进行操作，而不对字符串进行操作。对于 B 的每个元素，计算其哈希值，然后使用它来查找 A 的元素。如果找到元素，则意味着哈希值匹配；如果找到，则表明哈希值匹配。那么您还需要比较字符串以检测其是否为真值或只是意外匹配。

计算匹配的数量。当该数字等于 A 的大小时，停止并返回正结果。如果 B 的所有元素都已处理完毕，并且匹配的数量小于 A 的大小，则返回负结果。