从两个字符串中删除一个字符子集后检查两个字符串是否相等

Question

我最近遇到了这个问题：

给定两个字符串，s1 和 s2，完全由小写字母 'a' 到 'r' 组成，需要处理一系列查询。每个查询都提供从 'a' 到 'r' 的小写英文字母子集。对于每个查询，确定 s1 和 s2 在仅限于查询中的字母时是否相等。 s1 和 s2 最多可以包含 10^5 个字符，并且最多有 10^5 个查询。

例如，如果 s1 是“aabcd”，s2 是“caabd”，并且要求您处理子集“ac”的查询，则 s1 变为“aac”，而 s2 变为“咔嚓”。这些不匹配，因此查询将 return false。

通过执行以下操作，我能够在 O(N^2) 时间内解决此问题：对于每个查询，我检查 s1 和 s2 是否相等，方法是遍历两个字符串，一次一个字符，跳过不在允许字符子集中的字符，并检查 s1 和 s2 中的“允许”字符是否匹配。如果在某个时候，字符不匹配，则字符串不相等。否则，当仅限于查询中的字母时，s1 和 s2 是相等的。每个查询需要 O(N) 时间来处理，并且有 N 个查询，总共 O(N^2) 时间。

但是，有人告诉我有一种方法可以在 O(N) 中更快地解决这个问题。有谁知道如何做到这一点？

Answer 1

第一个明显的加速是确保您的集合成员测试是 O(1)。为此，有几个选项：

将每个字母表示为一个位——现在每个字符都是一个 18 位值，只设置了一位。允许的字符集现在是一个掩码，将这些位组合在一起，您可以使用 bitwise-AND;
或者，您可以有一个 18 值数组并按字符对其进行索引（c - 'a' 将给出 0 到 17 之间的值）。成员资格的测试基本上是数组查找的成本（并且您可以通过不进行减法来节省操作 - 而只是使数组更大并直接按字符索引。

思想实验

下一个潜在的加速是识别任何在两个字符串中出现次数不完全相同的字符将立即成为失败的匹配。您可以使用直方图计算两个字符串中的所有字符频率，这可以在 O(N) 时间内完成。这样，如果这样的字符出现在查询中，您可以修剪搜索 space，并且您可以在恒定时间内对此进行测试。

当然，这对真正的 stress-test 没有帮助，因为它可以保证所有可能的字母在两个字符串中的频率都匹配。那你怎么办？

好吧，您通过认识到 对于字符串 1 中字符 x 的任何位置 以及该字符在字符串 2 中的某个位置来扩展上述前提有效匹配（i.e 相同数量的字符 x 出现在两个字符串中，直到它们各自的位置），然后任何 other 到这些位置的字符必须也相等。对于任何不是这样的字符，它不可能与字符 x.

兼容

概念

让我们从称为 memoization 的技术开始考虑这个问题，您可以利用预先计算的或 partially-computed 信息并从中获取大量信息。所以考虑像这样的两个字符串：

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

这会占用大量内存，但别担心——我们稍后会处理。相反，花时间吸收我们实际在做的事情。

查看上面的 table，我们在这两个字符串的每个位置都有运行个字符总数。

现在让我们通过显示匹配查询 "ab" 和 non-matching 查询的示例来了解我们的匹配规则是如何工作的 "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'），我们只在两个字符串中查找其计数匹配的位置，然后我们比较这两列以查看其他值比赛。这为我们提供了一组所有 other 字符，这些字符在与 'a' 一起使用时有效。当然，'a'本身也是有效的。

我们的第一个优化是什么？位集——代表有效字符的 18 位值。你现在可以使用它了。对于每个字符串中的两列，您为具有匹配计数的字符设置 1，为具有 non-matching 计数的字符设置零。如果您以这种方式处理每一对匹配的 'a' 值，您将得到一堆它们所使用的集合。你可以保留一个运行 “主”集来表示这些的交集——你只需将它与你计算的每个中间集相交，这是一个单一的 bitwise-AND.

当您到达两个字符串的末尾时，您已经执行了 O(N) 搜索，并且在遇到 'a' 时检查了 18 行。结果是 all 个字符集与 'a'.

一起使用

现在重复其他字符，一次一个。每次都是如上所述的 O(N) 扫描，您最终会得到一组与您正在处理的字符一起工作的所有其他字符。

处理后处理所有这些行，您现在拥有一个包含 18 个值的数组，这些值表示可与任何一个字符一起使用的所有字符集。该操作花费了 O(18N) 的时间和 O(18N) 的存储空间。

查询

因为你现在有一个数组，其中每个字符都有所有可能的字符，你只需在查询中查找每个字符，然后将它们的集合相交（同样，使用 bitwise-AND） .通过使用查询中存在的所有字符的集合，需要进一步的交集。这会删除所有不相关的字符。

这为您留下了一个值，对于查询中的所有值，该值表示可以产生匹配字符串的所有值的集合。因此，如果此值然后等于到查询，那么您就有了匹配项。否则，你不会。

这是现在快的部分。它基本上将您的查询测试减少到恒定时间。然而，最初的索引确实耗费了我们大量的内存。对此可以做些什么？

动态规划

是否真的有必要为我们的频率阵列分配所有存储空间？

实际上，不。它作为一种可视化工具很有用，它以表格形式列出我们的计数，并从概念上解释该方法，但实际上，这些值中的很多在大多数时候都不是很有用，这确实使该方法看起来有点复杂。

好消息是我们可以在计算字符数的同时计算我们的主集，而不需要存储 any 个频率数组。请记住，当我们计算计数时，我们使用一个直方图，它就像一个小的 18 值数组数组一样简单，其中你说 count[c] += 1 （如果 c 是一个字符或从中派生的索引特点）。因此，如果我们只执行以下操作，我们就可以节省大量内存：

正在处理字符 c:

的所有兼容字符集（掩码）

将字符 c 的掩码初始化为全 1 (mask[c] = (1 << 18) - 1) -- 这表示当前所有字符都是兼容的。将字符直方图（计数）初始化为全零。
遍历字符串 1，直到到达字符 c。对于您一路上遇到的每个字符 x，增加它在直方图中的计数 (count[x]++)。
遍历字符串 2，直到到达字符 c。对于您一路上遇到的每个字符 x，减少它在直方图中的计数 (count[x]--)。
构造一个 'good' 集，其中任何当前具有 zero-count 的字符都有一个 1 位，否则为 0 位。将此与 c 的当前掩码相交（使用 bitwise-AND）：mask[c] &= good
从第 2 步继续，直到到达两个字符串的末尾。如果过早到达其中一个字符串的末尾，则字符计数不匹配，因此您将此字符的掩码设置为零：mask[c] = 0
每个字符从 1 开始重复，直到完成所有字符。

以上，我们基本上具有相同的时间复杂度 O(18N) 除了我们有绝对最小的额外存储——每个字符只有一个计数数组和一个掩码数组。

结合上述技术以真正快速地解决看似复杂的组合问题通常被称为 动态编程。我们将问题简化为一个真值 table，代表所有可能的字符，这些字符适用于任何单个字符。时间复杂度与字符串的长度保持线性关系，并且仅按可能的字符数缩放。

下面是上面用 C++ 编写的算法：https://godbolt.org/z/PxzYvGs8q

Answer 2

令 RESTRICT(s,q) 为字符串 s 对集合 q 中字母的限制。

如果 q 包含两个以上的字母，则可以从所有字符串 RESTRICT(s,q_ij) 重构完整的字符串 RESTRICT(s,q) 其中 q_ij 是 q. 对个字母

因此，RESTRICT(s1,q) = RESTRICT(s2,q) 当且仅当 RESTRICT(s1,q_ij) = RESTRICT(s2,q_ij) 对于 q.

中的所有对 q_ij

由于限制为 18 个字母，因此只有 153 个字母对，或者只有 171 个基本单查询或 double-letter 查询。

如果您预先计算了这 171 个查询的结果，那么您只需组合它们的结果就可以回答任何其他更复杂的查询，而根本不需要检查字符串。

从两个字符串中删除一个字符子集后检查两个字符串是否相等

Checking if two strings are equal after removing a subset of characters from both

algorithm

math

思想实验

概念

放在一起

查询

动态规划