Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Whilst solving a question, I have come across a problem regarding the maximal number of possible distinct $k$-length binary sub-strings in an $n$-length binary string.

My thought process was that if you take some $n$-length binary string, then the number of possible sub-strings could be found as follows:

$$\sum_{k=1}^{n}{n-k+1}=n^{2}-\frac{n(n+1)}{2}+n=\frac{n^{2}+n}{2}$$

But this doesn't take into account the maximum possible number of distinct sub-strings, which will be $2^{k}$, when we're looking for sub-strings of length $k$.

Does anyone have any suggestions as to how I could find the maximal number of distinct sub-strings (of length $k\le n$) contained within some binary string of length $n$?

Thanks in advance!

share|improve this question
    
Calculate it for some small values of $n$, then look it up in the Online Encyclopedia of Integer Sequences. –  Gerry Myerson Jun 16 '12 at 12:31

1 Answer 1

up vote 1 down vote accepted

I took my own advice: it's "Maximal number of distinct nonempty substrings of any binary string of length n." It seems that there is a question about this sequence that is very simple to state but is still open.

share|improve this answer
    
Ahh, so as yet there is no known closed-form to solve this problem? –  Shaktal Jun 16 '12 at 12:37
    
That's my interpretation of what it says at the OEIS. –  Gerry Myerson Jun 16 '12 at 12:51
    
Okay, thanks then! –  Shaktal Jun 16 '12 at 12:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.