algorithm - O(nlogn) 算法 - 在二进制字符串中找到三个均匀间隔的算法

Question

我昨天在算法测试中遇到了这个问题，但我想不出答案。这让我非常疯狂，因为它值大约 40 分。我认为大部分类(class)都没有正确解决它，因为我在过去 24 小时内没有想出解决方案。

给定一个长度为 n 的任意二进制字符串，如果它们存在，请在字符串中找到三个均匀间隔的字符串。编写一个算法，在 O(n * log(n)) 时间内解决这个问题。

所以像这样的字符串有三个“均匀间隔”的字符串:11100000, 0100100100

编辑:它是一个随机数，所以它应该可以用于任何数字。我给出的例子是为了说明“均匀间隔”的属性。所以 1001011 是一个有效的数字。 1、4 和 7 是均匀间隔的。

Answer 1

终于!跟踪线索 sdcvvc's answer ，我们有它:这个问题的 O(n log n) 算法!理解之后也很简单。猜 FFT 的人是对的。

问题:我们得到一个二进制字符串 S长度为 n，我们想在其中找到三个均匀间隔的 1。例如，S可能是 110110010 ，其中 n=9。它在位置 2、5 和 8 处均匀间隔 1s。

扫描 S从左到右，并列一个列表 L位置为 1。对于 S=110110010上面，我们有列表 L = [1, 2, 4, 5, 8]。这一步是 O(n)。现在的问题是找到一个长度为 3 的等差数列 在 L ，即在 L 中找到不同的 a、b、c使得 b-a = c-b，或等效地 a+c=2b .对于上面的示例，我们想要找到级数 (2, 5, 8)。

做个 多项式 p L 中每个 k 的项 xk .对于上面的例子，我们使多项式 p(x) = (x + x2 + x4 + x5+x8)。这一步是 O(n)。

求多项式 q = p2，使用 Fast Fourier Transform .对于上面的例子，我们得到多项式 q(x) = x16 + 2x13 + 2x12 + 3x10 + 4x9 + x8 + 2x7 + 4x6 + 2x5 + x4 + 2x3 + x2。 这一步是 O(n log n)。

对于 L 中的某些 k，忽略除对应于 x2k 的项之外的所有项.对于上面的示例，我们得到了 x16、3x10、x8、x4、x2 项。这一步是 O(n)，如果你选择这样做的话。

这是关键点: L 中 b 的任何 x2b 的系数正是 L 中 (a,c) 对的数量使得 a+c=2b。 [CLRS，例如。 30.1-7] 这样的一对总是 (b,b)(因此系数至少为 1)，但如果存在任何其他对 (a,c)，则系数至少为 3，来自 (a,c ) 和 (c,a)。对于上面的示例，由于 AP (2,5,8)，我们将 x10 的系数设为 3。 (出于上述原因，这些系数 x2b 将始终为奇数。q 中的所有其他系数将始终为偶数。)

那么，算法就是看这些项 x2b 的系数，看看有没有大于 1 的，如果没有，那么就没有均匀间隔的 1。如果 L 中有 b对于 x2b 的系数大于 1，那么我们知道有一些对 (a,c) - 除了 (b,b) - 对于 a+c=2b。要找到实际的配对，我们只需尝试 L 中的每个 a (相应的 c 将是 2b-a)并查看 S 中的位置 2b-a 是否有 1 .这一步是 O(n)。

就是这样，伙计们。

有人可能会问:我们需要使用 FFT 吗？很多答案，比如beta's , flybywire's , 和 rsp's ，建议检查每对 1 并查看“第三”位置是否有 1 的方法，可能在 O(n log n) 中起作用，基于直觉，如果 1 太多，我们会发现一个三重很容易，如果 1 太少，检查所有对花费的时间很少。不幸的是，虽然这种直觉是正确的并且简单的方法比 O(n2) 更好，但它并没有明显更好。如 sdcvvc's answer ，我们可以采用长度为 n=3k 的字符串的“类康托集”，在其三元表示中只有 0 和 2(没有 1)的位置处有 1。这样的字符串中有 2k = n(log 2)/(log 3) ≈ n0.63 个，并且没有均匀间隔的 1，因此检查所有对的顺序将是其中 1 数量的平方的顺序:那就是4k ≈ n1.26 不幸的是它渐近地比 (n log n) 大得多。事实上，最坏的情况甚至更糟:1953 年的 Leo Moser constructed (有效地)这样的字符串中有 n1-c/√(log n) 1s 但没有均匀间隔的 1s，这意味着在这样的字符串上，简单的方法将采用 Θ(n2-2c/√(log n)) —只有一个 小比 Θ(n2) 好一点，令人惊讶!

关于长度为 n 的字符串中 1 的最大数量，没有 3 个均匀间隔的字符串(我们在上面看到的简单的康托式结构中至少为 n0.63，并且至少为 n1-c/√(log n) 与Moser 的构造)——这是 OEIS A003002 .也可以直接从OEIS A065825计算作为 k 使得 A065825(k) ≤ n < A065825(k+1)。我写了一个程序来找到这些，结果证明贪心算法不会给出最长的这样的字符串。例如，对于 n=9，我们可以得到 5 个 1s (110100011) 但是贪婪只给出 4 (110110000)，对于 n=26 我们可以得到 11 个 1s (11001010001000010110001101) 但是 greedy1010 只给出00100010010010 N = 74，我们可以得到22个1S(11000010110001000001011010001000000000000000010001011010000010001101000011)，但贪婪使只有16(11011000011011000000000000011011000011011000000000000000000000000000000000)。不过，他们确实在很多地方都一致，直到 50(例如所有 38 到 50)。正如 OEIS 引用资料所说，Jaroslaw Wroblewski 似乎对这个问题很感兴趣，他在这些 non-averaging sets 上维护了一个网站。 .确切的数字最多只知道 194。