如何在二进制字符串的特定范围内找到010的数字

Question

给定一个二进制字符串。如何在字符串的特定范围内找到 "010" 的出现。
例如，我有字符串 "0100110" 。如果给定范围是 3 7（基于 1 的索引），则输出将为 4。我找不到任何更快的方法来解决它。

在尝试这个的同时，我可以在 O(N) 复杂度下解决它。方法是 - 首先我指出所有 '1' 在一定范围内的位置，然后使用这些位置我会计算出 '0'[= 的数量50=] 来回。然后将单个 '1' 后面找到的 '0' 的数量乘以 '0'[= 的数量50=]在forth中找到。然后将一定范围内的每个'1'的相乘结果相加。

对于给定的示例，'1' 在范围内的位置是 {5, 6}。现在对于索引 5 我来回都有 '0' 的数量是 2 和 1分别。所以我们可以让子序列"010"是2。同样对于索引 6 我们也得到答案是 2。总的来说，我们可以使子序列 "010" 总共 4 次。

但是当我们对给定的字符串进行一定范围的 Q 查询时，我的方法很容易达到时间复杂度 O(N²)。我尝试了很多但未能找到优化它的方法。任何人都可以用小于 O(N²) 复杂度的方法帮助我吗？顺便提一下时限应该是1秒。如能提供伪代码加分。

~提前致谢。

Answer 1

预处理：制作辅助数组，其中包含到给定位置的累积零数（aux[0]=0）

  0 1 0 0 1 1 0  //string
0 1 1 2 3 3 3 4  //aux array A[]

对于给定的 L..R 范围扫描，对于 1 的每个 k 索引获取范围内零的数量 - O(1) 操作

P[k] = (A[k] - A[L-1]) * (A[R] - A[k])
S = Sum(P[k], k=L..R)

所以我们每个查询有 O(R-L) 时间，Q 查询的最坏情况 O(Q*N)

但是仔细看公式：

P[k] = (A[k] - A[L-1]) * (A[R] - A[k]) = 
       A[k] * (A[R] + A[L-1]) - A[k]^2 - A[R] * A[L-1] = 
       A[k] * LRSum - A[k]^2 - LRProd
S = Sum(A[k] for ones) * LRSum - Sum(A[k]^2) - LRProd * NumOfOnes

请注意，LRSum 和 LRProd 是给定查询的常量，我们必须计算 1 位置的 A[k] 和以及相同位置的平方和。似乎我们可以使用累积数组的相同想法并在每个查询中获得 O(1) 的结果。

快速检查为您的示例提供 (3+3)*5 - (9+9) - 4*2 = 30-18-8 = 4。

使用累积数组：

  0 1 0 0 1  1  0  //string
0 1 1 2 3 3  3  4  //aux array A[]
0 0 1 1 1 4  7  7  //aux array B[]
0 0 1 1 1 10 19 19  //aux array C[]

Result = (B[R] - B[L-1]) * (A[R] + A[L-1]) - (C[R] - C[L-1]) - 
                 A[R] * A[L-1] * (R - L - 1 - (A[R] - A[L-1])) = 
         (7-1) * (4 + 1) - (19 - 1) - 4 * 1 * (7 - 2  - 4 + 1) = 4

如何在二进制字符串的特定范围内找到010的数字

How to find number of 010 in a certain range of a binary string

string

algorithm

string-algorithm