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 是字符串中的位数。