3

如何在二进制字符串中找到最长的子字符串，其中balance（即 1 和 0 的数量之差）>= 0？

例子：

01110000010 -> 6: 011100

1110000011110000111 -> 19：整个字符串

虽然这个问题看起来与最大值连续子序列（Maximum Contiguous Sum）问题非常相似，但动态规划解决方案似乎并不明显。在分而治之的方法中，如何进行合并？毕竟“高效”的算法是可能的吗？（一个简单的 O(n^2) 算法只会遍历所有可能的起点的所有子字符串。）

这是查找子字符串的修改变体，带有一些附加条件。不同之处在于，在链接的问题中，仅允许平衡永远不会低于零的此类子字符串（以向前或向后的方向查看字符串）。在给定的问题中，允许余额低于零，只要它在稍后阶段恢复。

4

5 回答 5

6

我有一个需要O(n)额外内存和O(n)时间的解决方案。

让我们将索引的“高度”表示h(i)为

h(i) = <number of 1s in the substring 1..i> - <number of 0s in the same substring>

现在可以将问题重新表述为：find iand jlike h(i) <= h(j)and j-i -> max。

显然，h(0) = 0，如果h(n) = 0，则解是整个字符串。

现在让我们计算数组B以便B[x] = min{i: h(i) = -x}. 换句话说，让成为 最左边的B[x]索引i。h(i)= -x

该数组B[x]的长度最多为n，并且在一次线性传递中计算。

现在我们可以遍历原始字符串，并为每个索引i计算具有非负余额的最长序列的长度，其结束i如下：

Lmax(i) = i - B[MIN{0, h(i)}]

最大Lmax(i)的i将为您提供所需的长度。

我将证明留作练习 :) 如果您无法弄清楚，请与我联系。

此外，我的算法需要 2 次原始字符串，但您可以将它们合并为一个。

于 2013-10-21T06:46:54.053 回答
4

使用“高度数组”可以很容易地回答这个问题O(n)，表示 1 的数量相对于 0 的数量。就像我在链接问题中的回答一样。

现在，我们不再关注原始数组，而是关注由 heights 索引的两个数组，一个将包含找到高度的最小索引，另一个将包含找到高度的最大索引。由于我们不想要负索引，我们可以将所有内容向上移动，使得最小高度为 0。

因此，对于示例案例（我在最后添加了两个 1 以表明我的观点）：

1110000011010000011111
数组高度可视化
  /\
 / \
/ \
      \ /\/\ /
       \/ \ /
              \ /
               \ /
                \/
（最低高度 = -5）
移位高度数组：
[5, 6, 7, 8, 7, 6, 5, 4, 3, 4, 5, 4, 5, 4, 3, 2, 1, 0, 1, 2, 3]
     身高：0 1 2 3 4 5 6 7 8
first_view = [17,16,15, 8, 7, 0, 1, 2, 3]
last_view = [17,18,19,20,21,22, 5, 4, 3]

请注意，我们有 22 个数字和 23 个不同的索引，0-22，代表数字之间的 23 个空格并填充数字

我们first_view可以last_view在O(n).

现在，对于 中的每个高度first_view，我们只需要检查 中每个较大的高度last_view，并取与索引相差最大的first_view索引。例如，从高度 0 开始，较大高度的索引最大值为 22。因此，从索引 17+1 开始的最长子字符串将在索引 22 处结束。

要查找last_view数组的最大索引，可以将其转换为右侧的最大值O(n)：

last_view_max = [22,22,22,22,22,22, 5, 4, 3]

所以找到答案只是简单地减去first_view，last_view_max

first_view = [17,16,15, 8, 7, 0, 1, 2, 3]
last_view_max = [22,22,22,22,22,22, 5, 4, 3]
结果 = [ 5, 6, 7,14,15,22, 4, 2, 0]

并取最大值（再次在 中O(n)），即 22，从起始索引 0 到结束索引 22，即整个字符串。=D

正确性证明：

假设最大子字符串从 index 开始，在 indexi结束j。如果 index 处的高度与 indexi处的高度相同k<i，那么k..j将是一个更长的子字符串，仍然满足要求。因此，考虑每个高度的第一个索引就足够了。类似地对于最后一个索引。

于 2013-10-21T07:04:47.740 回答
0

动态编程——线性运行时间（终于！）

受到这篇博文的启发。简单高效，一次性在线算法，但需要一些时间来解释。

主意

上面的链接显示了一个不同的问题：最大子序列和。它不能 1:1 映射到给定问题，这里需要 O(n) 的“状态”，与原始问题的 O(1) 形成对比。尽管如此，状态可以在 O(1) 中更新。

让我们重新表述这个问题。我们正在寻找输入中最长的子串，其中balance，即0's 和1's 之间的差值大于零。

该状态类似于我的其他分而治之的解决方案：我们为每个位置i 和每个可能的平衡 计算最长的字符串b的起始位置，该字符串的起始位置为平衡或更大，在位置结束。也就是说，从 index 开始到在结束的字符串具有 balance或更大，并且不再存在以 结尾的字符串。我们通过最大化 找到结果。s(i, b)bis(i, b) + 1ibii - s(i, 0)

算法

当然，我们不会将所有内容都保存s(i, b)在内存中，只是那些用于当前的i（我们迭代输入）。我们从s(0, b) := 0forb <= 0和:= undefinedfor开始b > 0。对于每个i，我们使用以下规则进行更新：

  1. 如果1被读取：s(i, b) := s(i - 1, b - 1).
  2. 如果0被读取：s(i, b) := s(i - 1, b + 1)如果已定义，s(i, 0) := i如果s(i - 1, 1)未定义。

该函数s（用于 current i）可以实现为指向长度数组的指针2n + 1；此指针根据输入向前或向后移动。在每次迭代中，我们注意到 的值s(i, 0)。

它是如何工作的？

状态函数s变得有效，特别是如果从开始到的余额i为负数。1它记录了所有可能尚未读取的 s 数量达到零余额的最早起点。

为什么它有效？

因为状态函数的递归定义等价于它的直接定义——在 positionb结束的具有 balance 或更大的最长字符串的起始位置i。

为什么递归定义是正确的？

归纳证明。

于 2013-10-26T07:46:05.240 回答
0

分而治之

另一个经典。应该在 O(n log n) 中运行，但很难实现。

主意

最长的可行子串要么在左半边，要么在右半边，要么越过边界。调用两半的算法。对于边界：

假设问题大小为 n。对于跨越边界的最长可行子串，我们将计算子串左半部分的余额。

对于 -n/2 和 n/2 之间的每个可能的平衡，在左半部分确定在边界处结束并具有此（或更大）平衡的最长字符串的长度。（线性时间！）对右半部分和从边界开始的最长字符串执行相同操作。结果是两个大小为 n + 1 的数组；我们反转其中一个，逐个添加它们并找到最大值。（再次，线性。）

为什么它有效？

如果另一部分对此进行补偿，则平衡 >= 0 且跨越边界的子串在左侧或右侧部分的 balance < 0。（“借款”余额。）关键问题是借多少；我们遍历所有潜在的“余额信用”并找到最佳权衡。

为什么这是 O(n log n)？

因为合并（查看跨越边界的字符串）只需要线性时间。

为什么要合并 O(n)？

练习留给读者。

于 2013-10-22T23:00:40.690 回答
0

压缩二次运行时

我们将从头开始寻找（本地）最长的平衡为零的子串。我们将忽略零字符串。（极端情况：全零 -> 空字符串，余额永远不会再次达到零 -> 整个字符串。）在这些余额为零的子字符串中，所有尾随零都将被删除。

用 B 表示余额 > 0 的子串，用 Z 表示只有零的子串。每个输入字符串可以分解如下（伪正则表达式）：

乙？(ZB)* Z?

每个 B 都是最大可行解，这意味着它不能在不降低平衡的情况下向任一方向扩展。但是，如果在折叠后余额仍然大于零，则可能会折叠 BZB 或 ZBZ 序列。

请注意，如果 ZBZ 部分的余额 >= 0，则始终可以将 BZBZB 的序列折叠为单个 B。（可以在线性时间内一次性完成。）一旦所有此类序列都被折叠，每个 ZBZ 的余额部分低于零。尽管如此，仍有可能存在余额高于零的 BZB 部分——即使在余额低于零的 BZBZB 序列中，前导和尾随 BZB 部分的余额都超过零。在这一点上，似乎很难决定崩盘哪个BZB。

还是二次元...

无论如何，使用这种简化的数据结构，可以尝试所有 B 作为起点（如果仍有余额，可能会向左延伸）。运行时间仍然是二次方的，但（在实践中）n 小得多。

于 2013-10-21T07:48:58.137 回答