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

Question

昨天我在一个算法测试中遇到这个问题，我想不出答案。这让我非常疯狂，因为它值40分。我想大多数同学都没有正确地解决这个问题，因为我在过去的24小时里没有想出一个解决方案。
给定一个长度为n的任意二进制字符串，如果字符串存在，则在字符串中找到三个均匀间隔的字符串。写一个算法在O（n*log（n））时间内解决这个问题。
所以像这样的字符串有三个是“等距的”：111000000100100
编辑：这是一个随机数，所以它应该可以为任何数字工作。我举的例子是为了说明“等间距”属性。所以1001011是一个有效数字其中1、4和7是均匀分布的。

Answer 1

终于在sdcvvc's answer中跟踪线索，我们得到了它：问题的O（n logn）算法这也很简单，在你理解之后那些猜测fft的人是对的。
问题：我们得到一个长度为n的二进制字符串S，我们想在其中找到三个均匀分布的1例如，S可以是110110010，其中n＝9它在位置2、5和8处具有均匀分布的1。
从左到右扫描，列出1的位置对于上面的S，我们有一个列表L=[1，2，4，5，8]这个步骤是o（n）。现在的问题是在L中找到一个长度为3的算术级数，即在S=110110010中找到不同的a、b、c，使得b-a=c-b，或者等价于a+c=2b。对于上面的例子，我们要找到级数（2、5、8）。
对于L中的每个k，使用项xk进行多项式L对于上面的例子，我们将多项式p（x）=（x+x2+x4+x5+x8）。这个步骤是o（n）。
使用Fast Fourier Transform找到多项式p=p2。对于上面的例子，我们得到多项式q（x）=x16+2x13+2x12+3x10+4x9+x8+2x7+4x6+2x5+x4+2x3+x2。这个步骤是o（n logn）。
忽略除x2k对应于L中某些k之外的所有术语。对于上面的例子，我们得到了术语x16、3x10、x8、x4、x2。如果你愿意的话，这一步是O（n）。
这里的关键点是：在q中，b的任何x2b的系数正好是L中的对（a，c），使得a+c= 2b。[CLSR，Ex.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），然后看看在2b-a in位置是否有1L。这个步骤是O（n）。
就这些，伙计们。
有人可能会问：我们需要使用fft吗？许多答案，如beta's、flybywire's和rsp's，都表明，检查每对1的方法，看看在“第三”位置是否有1，可能在o（n logn）中工作，基于这样的直觉：如果有太多的1，我们会很容易找到一个三元组；如果有太少的1，检查所有的对只需要很少的时间。不幸的是，虽然这种直觉是正确的，而且简单的方法比o（n2）好，但并不明显好。在sdcvvc's answer中，我们可以取长度为n=3k的字符串的“Cantor-like集”，其中1s位于三元表示中只有0s和2s（no 1s）的位置这样的一个字符串有2k=n（log 2）/（log 3）≈n0.63个，没有均匀分布的1s，所以检查所有对的顺序是1s个数的平方：即4k≈n1.26，不幸的是，它的渐近值远远大于（n logn）。事实上，最坏的情况甚至更糟：Leo Moser在1953年constructed（实际上）这样的字符串，其中有n1-c/（log n）1s，但没有均匀间隔的1s，这意味着在这样的字符串上，简单的方法将采取（n2-2c/（logn））——只比（n2）好一点点，令人惊讶！
关于长度为n的字符串中的1s的最大数目，没有3个均匀间隔的字符串（我们上面看到的至少是n0.63从容易的康托尔式构造，至少N1-C//（log n）与莫泽的构造）-这是OEIS A003002。也可以直接从OEIS A065825作为k计算，使得a065825（k）≤nnon-averaging sets网站上开设了一个网站。确切的数字只有194个。