我想到了一种可能有效的分治方法。
首先,在预处理中,您需要将所有小于输入大小的一半(n/3)的数字插入到列表中。
给定一个字符串:0000010101000100
(请注意,此特定示例是有效的)
将1到(16/2)之间的所有质数(和1)插入到列表中:{1, 2, 3, 4, 5, 6, 7}
然后将其分成两半:
100000101 01000100
继续这样做,直到得到大小为1的字符串。对于所有包含1的大小为1的字符串,将字符串的索引添加到可能性列表中;否则,返回-1表示失败。
您还需要返回与每个起始索引相关联的仍可能的间距距离列表。(从上面制作的列表开始,并随着进行而删除数字)在这里,空列表表示您只处理一个1,因此此时可以使用任何间距;否则,列表包括必须被排除的间距。
因此,继续以上面的示例:
1000 0101 0100 0100
10 00 01 01 01 00 01 00
1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0
在第一次合并步骤中,我们现在有八组两个数字。在第一组中,我们有可能的一组,但是由于其他零存在,我们学习到间隔为1是不可能的。因此我们返回0(索引)和{2,3,4,5,7}(表示间隔为1是不可能的)。在第二组中,我们没有任何匹配,因此返回-1。在第三组中,我们有一个匹配,在索引5处没有消除间隔,因此返回5和{1,2,3,4,5,7}。在第四组中,我们返回7和{1,2,3,4,5,7}。在第五组中,返回9和{1,2,3,4,5,7}。在第六组中,返回-1。在第七组中,返回13和{1,2,3,4,5,7}。在第八组中,返回-1。
将其重新组合成四组四个,我们有:
1000
:返回(0,{4,5,6,7})
0101
:返回(5,{2,3,4,5,6,7}),(7,{1,2,3,4,5,6,7})
0100
:返回(9,{3,4,5,6,7})
0100
:返回(13,{3,4,5,6,7})
组合成八个的集合:
10000101
:返回(0,{5,7}),(5,{2,3,4,5,6,7}),(7,{1,2,3,4,5,6,7})
01000100
:返回(9,{4,7}),(13,{3,4,5,6,7})
组合成一个十六个元素的集合:
10000101 01000100
随着我们的进展,我们不断地检查到目前为止的所有可能性。在这一步中,我们留下了超出字符串结尾的东西,但现在我们可以检查所有的可能性。
基本上,我们检查第一个1和5和7的间距,发现它们没有对齐1。 (请注意,每个检查是CONSTANT,而不是线性时间)然后我们使用2、3、4、5、6和7的间距检查第二个(索引5的位置),或者我们会停在2,因为那实际上匹配起来了。
哇!那是一个相当长的算法。
我不知道它是否100%是O(n log n),因为最后一步,但是就我所知,直到那里的一切肯定都是O(n log n)。稍后我会回来并尝试完善最后一步。
编辑:更改我的答案以反映Welbog的评论。对于错误表示抱歉。等我再次解密我写的内容时,我会稍后写一些伪代码。;-)