我对一个算法的测试这个问题，昨天，我不能找出答案。这是推动我绝对是疯了，因为它是价值约40点。我想，大多数类并没有解决它正确，因为我还没有想出了在过去24小时内解决。

I had this question on an Algorithms test yesterday, and I can't figure out the answer. It is driving me absolutely crazy, because it was worth about 40 points. I figure that most of the class didn't solve it correctly, because I haven't come up with a solution in the past 24 hours.

鉴于长度为n的任意的二进制串，查找字符串在三个均匀间隔的，如果它们存在。写一个算法，解决了这个为O（N *的log（n））的时间。

Given a arbitrary binary string of length n, find three evenly spaced ones within the string if they exist. Write an algorithm which solves this in O(n * log(n)) time.

所以像这些字符串有三种那些被均匀间隔：11100000，0100100100

So strings like these have three ones that are "evenly spaced": 11100000, 0100100100

编辑：这是随机数，所以它应能适用于任何数目。我给的例子是为了说明均匀分布的属性。所以，1001011是有效的数字。带1,4和7被那些被均匀地间隔开。

edit: It is a random number, so it should be able to work for any number. The examples I gave were to illustrate the "evenly spaced" property. So 1001011 is a valid number. With 1, 4, and 7 being ones that are evenly spaced.

推荐答案

终于来了！继在sdcvvc's回答，我们有它：在为O（n log n）的算法问题！这也很简单，你了解它之后。这些谁猜FFT是正确的。

Finally! Following up leads in sdcvvc's answer, we have it: the O(n log n) algorithm for the problem! It is simple too, after you understand it. Those who guessed FFT were right.

问题：我们有一个二进制字符串长度取值的 N 的，我们要找到三个均匀间隔1秒在里面。例如，取值可能 110110010 ，其中的 N = 9。它已均匀在位置2,5，和8隔开1秒

The problem: we are given a binary string S of length n, and we want to find three evenly spaced 1s in it. For example, S may be 110110010, where n=9. It has evenly spaced 1s at positions 2, 5, and 8.

扫描取值左到右，并制作一个列表→ 1为阵地 S = 110110010 上面，我们有列表L = [1，2，4，5，8]。这一步是O（n）。现在的问题是找到长度的算术级数3 在→，即找到不同的 A，B，C 在→这样的 BA = CB 的，或者等价的的 A + C = 2B 的 。对于上面的例子中，我们希望找到的进展（2，5,8）。

Scan S left to right, and make a list L of positions of 1. For the S=110110010 above, we have the list L = [1, 2, 4, 5, 8]. This step is O(n). The problem is now to find an arithmetic progression of length 3 in L, i.e. to find distinct a, b, c in L such that b-a = c-b, or equivalently a+c=2b. For the example above, we want to find the progression (2, 5, 8).

请在多项式 P 与条件的 X K 的每个 K 的在→。对于上面的例子中，我们使多项式的 P（x）=（X + X 2 + X 4 + X 5 + x 8 ）的。这一步是O（n）。

Make a polynomial p with terms xk for each k in L. For the example above, we make the polynomial p(x) = (x + x2 + x4 + x5+x8). This step is O(n).

查找多项式① = P 2 的，使用的OEIS A003002 。它也可直接从 OEIS A065825 的计算为第k使得A065825（k）的≤N'其中; A065825第（k + 1）。我写了一个程序来找到这些，而且事实证明，贪心算法做的没有的给予最长的字符串。例如，对于的 N 的= 9，我们可以得到5 1S（110100011），但贪婪只给出4（110110000），为的 N = 26，我们可以得到11 1S（ 11001010001000010110001101），但贪婪仅给出8（11011000011011000000000000），和用于 N 的= 74，我们可以得到22 1秒（11000010110001000001011010001000000000000000010001011010000010001101000011），但贪婪仅给出16（11011000011011000000000000011011000011011000000000000000000000000000000000）。他们不同意，在不少地方，直到50（例如，所有的38至50），虽然。由于OEIS引用说，似乎雅罗斯瓦夫·莱夫斯基很关心这个问题，他认为这些网站的非平均集的。具体的数字是已知的只到194。

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 n0.63 from the easy Cantor-like construction, and at least n1-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.