更确切地说，我正在寻找一种算法，该算法将接受两个字符串集合，并返回第一个集合中的所有元素，其中包含第二个集合的所有元素。
例如，如果我有["猫"、"狗"、"男孩"]，它会返回，说"男孩想要一只猫和一只狗"，但不是，例如，"狗是个好男孩。">
我找到了Aho-Corasick算法，但这似乎更适合"至少一个匹配"而不是"每个匹配"的解决方案。
我不确定问题的具体内容，但假设您有
collection1 : ['this is a good boy',' this is a bad boy',....]
和
collection2: ['this', 'is a', 'good', 'boy']
它应该只返回CCD_ 3。
同样，我不确定这种算法的内存和速度要求，但我会创建一个后缀树来验证元素的存在：
psuedo代码
for elm1 in collection1:
sTree = suffix_tree(elm)
valid = false
for elm2 in collection2:
valid = valid & search_in_suffix(elm2)
if valid:
return elm1
return 'NOT_FOUND'
你可以在这里阅读更多关于后缀树的信息。请记住，这也取决于您的数据集，如果您有非常大的字符串，后缀树可能很快，但创建它会花费大量内存。
如果我们稍微修改一下Aho-Corasick自动机，它就可以在这里工作。
-
让我们为第二个字符串集合构建Aho-Corasick自动机。
-
如果自动机中的一个字符串是另一个字符串的前缀，我们可以删除它。它不会改变答案。
-
让我们只使用初始边遍历自动机(这样它是一棵树)，并预先计算一个节点，该节点是给定节点的祖先，并且对应于每个节点集合中某个字符串的末尾(我将其表示为
anc_end。它是唯一的，因为没有任何字符串是任何其他字符串的前缀，如上所示)。我们可以使用深度优先搜索在线性时间内完成(参数是当前节点和最后一个节点，该节点对应于我们在从根到该节点的路径上看到的某个字符串的末尾(如果没有这样的节点，则为-1))。 -
我们可以遍历自动机，就像我们通常对第一个集合的每个字符串所做的那样。我们需要在每个步骤中设置
was[anc_end[v]] = true，其中v是当前节点。完成后，我们只需要检查与第二个集合中某个字符串末尾对应的所有节点的was是否为true。 -
我们快到了。我们将使用"带版本的数组"结构(其理念是保留一对(值、时间戳)，而不仅仅是值，并在进入下一个字符串时增加计时器)，而不是为新集合的每个字符串初始化
was数组，并计算可见的"结束"节点的数量(我们需要将第一个集合中的每个字符串的计数器重置为零)。
此解决方案的输入大小是线性的，因此在时间复杂性方面是最优的(它还使用了线性空间量)。