number of different numbers in a given binary string and their sum

I'am thinking of this problem and don't have an idea where to start with >>

We are given a binary string and is there any possible way other than brute force to find number of different numbers(their binary representations as sub-strings in the given string) it consists of and their sum.

for example:

if given binary is: "1101" then the possible numbers it consists are -

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

in decimal:

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

sum = 0 + 1 + 2 + 3 + 5 + 6 + 13 = 30

Answers


HINTS

Have a look at Suffix Trees, they let you find the count of different substrings in a string in O(n).

To find the sum of the different numbers I would recommend you actually compute the suffix tree for the reversed string, in other words you are computing a prefix tree.

You can then compute for each prefix node the sum of all distinct numbers underneath it.

The reason a reversed string is better is that we adding a digit to the end of a number is easy (multiply by 2 and add the digit), and so we can do this operation to our subtotals.

If we try to do the same with a suffix tree, we would want to add a digit to the front of all our numbers, but the numbers are of different lengths so it is hard to see what operation you can do to the total.

Take care when counting the prefix trees to ignore branches that start with 0 or you will also count 001 and 01 and 1 as being distinct.

I believe this should result in an O(n) cost for the entire operation where n is the number of digits in your string.


Need Your Help

Can the ZedGraph charting library for .NET be recommended?

c# graphics charts zedgraph

I am working on a project for my company, and I need to integrate some graphs of different types and average complexity to C# in the process of studying stock markets. I found this free library on ...

Replace string spaces with an underscore

c# string replace

I need to replace some spaces with an underscore (i.e. "PM HD PSP" > "PM_HD_PSP")

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.