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

昨天算法考试的时候遇到了这个问题，我不知道答案。这简直让我抓狂，因为它大约值 40 分。我估计全班大部分人都没有正确解决这个问题，因为我在过去 24 小时内还没有想出解决方案。

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

因此，像这样的字符串具有三个“均匀间隔”的字符串：11100000、0100100100

编辑：它是一个随机数，因此它应该能够适用于任何数字。我给出的例子是为了说明“均匀分布”的性质。所以 1001011 是一个有效的数字。其中 1、4 和 7 是均匀分布的。

最后！跟进线索sdcvvc 的回答，我们有了：解决该问题的 O(n log n) 算法！理解之后也很简单。那些猜测 FFT 的人是对的。

问题：给定一个二进制字符串S长度n，我们想在其中找到三个均匀分布的 1。例如，S may be 110110010, where n=9。它在位置 2、5 和 8 处均匀间隔有 1。

1. Scan S从左到右，并列出一个列表L位置 1. 对于S=110110010上面，我们有列表 L = [1, 2, 4, 5, 8]。这一步的时间复杂度为O(n)。现在的问题是找到一个长度为 3 的算术级数 in L，即找到不同的a, b, c in L这样b-a = c-b，或等价地a+c=2b。对于上面的示例，我们想要找到级数 (2, 5, 8)。

2. Make a polynomial p with terms x^k for each k in L. For the example above, we make the polynomial p(x) = (x + x² + x⁴ + x⁵+x⁸). This step is O(n).

3. Find the polynomial q = p², using the Fast Fourier Transform. For the example above, we get the polynomial q(x) = x¹⁶ + 2x¹³ + 2x¹² + 3x¹⁰ + 4x⁹ + x⁸ + 2x⁷ + 4x⁶ + 2x⁵ + x⁴ + 2x³ + x². This step is O(n log n).

4. Ignore all terms except those corresponding to x^2k for some k in L. For the example above, we get the terms x¹⁶, 3x¹⁰, x⁸, x⁴, x². This step is O(n), if you choose to do it at all.

Here's the crucial point: the coefficient of any x^2b for b in L is precisely the number of pairs (a,c) in L such that a+c=2b. [CLRS, Ex. 30.1-7] One such pair is (b,b) always (so the coefficient is at least 1), but if there exists any other pair (a,c), then the coefficient is at least 3, from (a,c) and (c,a). For the example above, we have the coefficient of x¹⁰ to be 3 precisely because of the AP (2,5,8). (These coefficients x^2b will always be odd numbers, for the reasons above. And all other coefficients in q will always be even.)

So then, the algorithm is to look at the coefficients of these terms x^2b, and see if any of them is greater than 1. If there is none, then there are no evenly spaced 1s. If there is a b in L for which the coefficient of x^2b is greater than 1, then we know that there is some pair (a,c) — other than (b,b) — for which a+c=2b. To find the actual pair, we simply try each a in L (the corresponding c would be 2b-a) and see if there is a 1 at position 2b-a in S. This step is O(n).

就这些了，伙计们。

One might ask: do we need to use FFT? Many answers, such as beta's, flybywire's, and rsp's, suggest that the approach that checks each pair of 1s and sees if there is a 1 at the "third" position, might work in O(n log n), based on the intuition that if there are too many 1s, we would find a triple easily, and if there are too few 1s, checking all pairs takes little time. Unfortunately, while this intuition is correct and the simple approach is better than O(n²), it is not significantly better. As in sdcvvc's answer, we can take the "Cantor-like set" of strings of length n=3^k, with 1s at the positions whose ternary representation has only 0s and 2s (no 1s) in it. Such a string has 2^k = n^{(log 2)/(log 3)} ≈ n^0.63 ones in it and no evenly spaced 1s, so checking all pairs would be of the order of the square of the number of 1s in it: that's 4^k ≈ n^1.26 which unfortunately is asymptotically much larger than (n log n). In fact, the worst case is even worse: Leo Moser in 1953 constructed (effectively) such strings which have n^{1-c/√(log n)} 1s in them but no evenly spaced 1s, which means that on such strings, the simple approach would take Θ(n^{2-2c/√(log n)}) — only a tiny bit better than Θ(n²), surprisingly!

About the maximum number of 1s in a string of length n with no 3 evenly spaced ones (which we saw above was at least n^0.63 from the easy Cantor-like construction, and at least n^{1-c/√(log n)} with Moser's construction) — this is OEIS A003002. It can also be calculated directly from OEIS A065825 as the k such that A065825(k) ≤ n < A065825(k+1). I wrote a program to find these, and it turns out that the greedy algorithm does not give the longest such string. For example, for n=9, we can get 5 1s (110100011) but the greedy gives only 4 (110110000), for n=26 we can get 11 1s (11001010001000010110001101) but the greedy gives only 8 (11011000011011000000000000), and for n=74 we can get 22 1s (11000010110001000001011010001000000000000000010001011010000010001101000011) but the greedy gives only 16 (11011000011011000000000000011011000011011000000000000000000000000000000000). They do agree at quite a few places until 50 (e.g. all of 38 to 50), though. As the OEIS references say, it seems that Jaroslaw Wroblewski is interested in this question, and he maintains a website on these non-averaging sets. The exact numbers are known only up to 194.