algorithm - 给定二进制字符串中不同数字的数量及其总和

Question

我正在考虑这个问题，但不知道从哪里开始>>

我们得到一个二进制字符串，除了蛮力之外，还有其他可能的方法来找到它包含的不同数字的数量（它们作为给定字符串中的子字符串的二进制表示）及其总和。

例如：

如果给定的二进制是：“1101”，那么它包含的可能数字是 -

0,01,10,11,101,110,1101

十进制：

0, 1, 2, 3,  5,  6,  13

总和 = 0 + 1 + 2 + 3 + 5 + 6 + 13 = 30

Answer 1

提示

看看Suffix Trees，它们可以让你在 O(n) 中找到字符串中不同子字符串的计数。

要找到不同数字的总和，我建议您实际计算反转字符串的后缀树，换句话说，您正在计算前缀树。

然后，您可以为每个前缀节点计算其下所有不同数字的总和。

反转字符串更好的原因是我们在数字末尾添加一个数字很容易（乘以 2 并添加数字），因此我们可以对小计执行此操作。

如果我们尝试对后缀树做同样的事情，我们希望在所有数字的前面添加一个数字，但是数字的长度不同，所以很难看出你可以对总数进行什么操作。

计算前缀树时要小心忽略以 0 开头的分支，否则您也会将 001 和 01 和 1 视为不同的。

我相信这应该会导致整个操作的 O(n) 成本，其中 n 是字符串中的位数。