我最近遇到了这个问题：
给您两个字符串 s1 和 s2，它们完全由小写字母“a”到“r”组成，并且需要处理一系列查询。每个查询提供从“a”到“r”的小写英文字母的子集。对于每个查询，当仅限于查询中的字母时，确定 s1 和 s2 是否相等。s1 和 s2 最多可以包含 10^5 个字符，并且最多有 10^5 个查询。
例如，如果 s1 是“aabcd”，s2 是“caabd”，并且要求您处理子集“ac”的查询，则 s1 变为“aac”，而 s2 变为“caa”。它们不匹配，因此查询将返回 false。
我能够通过执行以下操作在 O(N^2) 时间内解决此问题：对于每个查询，我通过迭代两个字符串（一次一个字符）来检查 s1 和 s2 是否相等，并跳过不相等的字符位于允许的字符子集中，并检查 s1 和 s2 中的“允许”字符是否匹配。如果在某个时刻，字符不匹配，则字符串不相等。否则，当仅限于查询中的字母时，s1 和 s2 相等。每个查询需要 O(N) 时间来处理，并且有 N 个查询，总共需要 O(N^2) 时间。
然而，我被告知有一种方法可以在 O(N) 时间内更快地解决这个问题。有谁知道如何做到这一点？
第一个明显的加速是确保你的集合成员资格测试是 O(1)。为此，有几个选择：
c - 'a'将给出 0 到 17 之间的值）。那么，成员资格的测试基本上就是数组查找的成本（并且您可以通过不进行减法来节省操作 - 而只是使数组更大并直接按字符索引。下一个潜在的加速是认识到任何在两个字符串中出现次数不完全相同的字符将立即成为失败的匹配。您可以使用直方图来计算两个字符串中的所有字符频率，这可以在 O(N) 时间内完成。通过这种方式，如果查询中出现这样的字符，您可以修剪搜索空间，并且可以在恒定时间内对此进行测试。
当然，这对于真正的压力测试没有帮助，因为压力测试将保证所有可能的字母在两个字符串中的频率都匹配。那么，你该怎么办？
那么，您可以扩展上述前提，认识到对于字符串 1 中字符的任何位置x和字符串 2 中该字符的某个位置，这将是有效匹配（即两个字符串中出现的字符数相同，x直到其各自的位置） ，那么直到这些位置的任何其他字符的总数也必须相等。对于任何不正确的字符，它不可能与字符兼容x。
让我们首先从一种称为记忆的技术角度考虑这个问题，您可以利用预先计算或部分计算的信息并从中获得很多信息。所以考虑这样的两个字符串：
a b a a c d e | e a b a c a d
在这里你能做什么有用的事？那么，为什么不存储每个字母的部分计数和：
a b a a c d e | e a b a c a d
----------------------|----------------------
freq(a) = 1 1 2 3 3 3 3 | 0 1 1 2 2 3 3
freq(b) = 0 1 1 1 1 1 1 | 0 0 1 1 1 1 1
freq(c) = 0 0 0 0 1 1 1 | 0 0 0 0 1 1 1
freq(d) = 0 0 0 0 0 1 1 | 0 0 0 0 0 0 1
freq(e) = 0 0 0 0 0 0 1 | 1 1 1 1 1 1 1
这会使用大量内存，但不用担心——我们稍后会处理这个问题。相反，花时间吸收我们实际正在做的事情。
查看上表，我们有两个字符串在这些字符串中每个位置的运行字符计数总计。
"ab"现在让我们通过显示匹配查询和非匹配查询的示例来了解匹配规则是如何工作的"acd"：
为了"ab"：
a b a a c d e | e a b a c a d
----------------------|----------------------
freq(a) = 1 1 2 3 3 3 3 | 0 1 1 2 2 3 3
freq(b) = 0 1 1 1 1 1 1 | 0 0 1 1 1 1 1
^ ^ ^ ^ ^ ^ ^ ^
我们扫描频率数组，直到在查询中找到我们的字母之一。上面我标记的位置^。如果删除所有未标记的列，您将看到剩余的列在两侧都匹配。所以这是一场比赛。
为了"acd"：
a b a a c d e | e a b a c a d
----------------------|----------------------
freq(a) = 1 1 2 3 3 3 3 | 0 1 1 2 2 3 3
freq(c) = 0 0 0 0 1 1 1 | 0 0 0 0 1 1 1
freq(d) = 0 0 0 0 0 1 1 | 0 0 0 0 0 0 1
^ ^ # # ^ ^ ^ # # ^
此处，除标有 的列外，所有列均匹配#。
好吧，您可以看到它是如何工作的，但您可能想知道运行时，因为上面的这些示例似乎比您之前执行的扫描更多！
这就是事情变得有趣的地方，也是我们的字符频率真正发挥作用的地方。
首先，观察我们在那些标记的列上实际执行的操作。对于我们关心的任何一个字符（例如“a”），我们仅查找两个字符串中其计数匹配的位置，然后比较这两列以查看其他值匹配的内容。这为我们提供了与“a”一起使用时有效的所有其他字符的集合。当然，“a”本身也是有效的。
我们的第一个优化是什么？位集——表示有效字符的 18 位值。您现在可以使用它。对于每个字符串中的两列，您为具有匹配计数的字符设置 1，为具有不匹配计数的字符设置 0。如果您以这种方式处理每一对匹配的“a”值，您将得到一堆它们使用的集合。您可以保留一个运行的“主”集来表示这些集的交集 - 您只需将它与您计算的每个中间集相交，这是一个按位与。
当到达两个字符串的末尾时，您已经执行了 O(N) 搜索，并且每次遇到“a”时都检查了 18 行。结果是与“a”一起使用的所有字符的集合。
现在对其他角色重复一次，一次一个。每次都是如上所述的 O(N) 扫描，您最终会得到与您正在处理的字符一起使用的所有其他字符的集合。
处理完所有这些行后，您现在拥有一个包含 18 个值的数组，这些值代表与任何一个字符一起使用的所有字符的集合。该操作花费了 O(18N) 时间和 O(18N) 存储空间。
由于您现在有一个数组，其中每个字符都有与其一起使用的所有可能的字符，因此您只需在查询中查找每个字符，然后将它们的集合相交（再次使用按位与）。需要使用查询中存在的所有字符集进行进一步的交集。这会删除所有不相关的字符。
这将为您留下一个值，对于查询中的所有值，该值表示可以生成匹配字符串的所有值的集合。因此，如果该值等于查询，那么您就有匹配项。否则，你就不会。
这是现在速度很快的部分。它本质上将您的查询测试减少到恒定时间。然而，原来的索引确实消耗了我们大量的内存。对此我们能做些什么呢？
真的有必要为我们的频率数组分配所有存储空间吗？
好吧，实际上，不。它作为一种可视化工具很有用，它以表格形式列出我们的计数，并从概念上解释该方法，但实际上，其中很多值在大多数情况下并不是很有用，而且它确实使该方法看起来有点复杂。
好消息是我们可以在计算字符计数的同时计算主集，而无需存储任何频率数组。请记住，当我们计算计数时，我们使用直方图，它就像在您所说的地方有一个小的 18 值数组count[c] += 1（ifc是一个字符或从该字符派生的索引）一样简单。因此，如果我们执行以下操作，就可以节省大量内存：
处理 character 的所有兼容字符的集合（掩码）c：
将字符掩码初始化c为全 1 ( mask[c] = (1 << 18) - 1) ——这表示所有字符当前都是兼容的。将字符直方图（计数）初始化为全零。
遍历字符串 1 直到到达字符c。x对于一路上遇到的每个字符，增加其在直方图中的计数 ( count[x]++)。
遍历字符串 2 直到到达字符c。x对于一路上遇到的每个字符，减少其在直方图中的计数 ( count[x]--)。
构造一个“好”集，其中当前计数为零的任何字符都具有 1 位，否则为 0 位。将其与当前掩码相交c（使用按位与）：mask[c] &= good
从步骤 2 继续，直到到达两个字符串的末尾。如果您过早到达其中一个字符串的末尾，则字符计数不匹配，因此您将该字符的掩码设置为零：mask[c] = 0
对每个字符从 1 开始重复，直到完成所有字符。
上面，我们基本上具有相同的时间复杂度 O(18N)，除了我们有绝对最小的额外存储空间——每个字符只有一个计数数组和一个掩码数组。
结合上述技术来快速解决看似复杂的组合问题通常称为动态编程。我们将问题简化为一个真值表，表示与任何单个字符一起使用的所有可能的字符。时间复杂度与字符串的长度保持线性关系，并且仅按可能的字符数缩放。
以下是用 C++ 编写的上述算法：https ://godbolt.org/z/PxzYvGs8q