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.

This question is probably quite easy.

I know that the number of substrings of length M in a string of length N are the total number of possible starting points. I know that this is N - M + 1. I don't doubt this. However, I can't seem to come up or find an explanation on WHY this is.

Similar to How many substrings of length m can be formed from a string of length n?. Different because I don't want the formula but the explanation behind the formula.

share|improve this question

3 Answers 3

up vote 1 down vote accepted

The first starting point is clearly $1$, so to find the number of possible starting points, we need to find the last possible starting point. Look first at a numerical example, say $M=6$ and $N=10$. Can I start at $10-6=4$? Yes, because I get the substring occupying positions $4,5,6,7,8$, and $9$. As you can see, I could have started one position later, at $5$, so there are actually $5$ possible starting points.

Try another, say $M=4$ and $N=15$. Again, it's natural to think first of $15-4=11$ as a possible late starting point, and it works: the substring occupies positions $11,12,13$, and $14$. Once again, I could have started one position later, at $12$, and there are $12$ possible starting points.

Note that in both cases $N-M$ came up one short of the right answer. There's a simple reason for this. If take away the first $N-M$ positions, $N-(N-M)=M$ positions remain. You took away positions $1$ through $N-M$, so the first of the remaining positions must be $N-M+1$. And it's the last possible starting point, because only $M$ positions are left: you're looking at the very last block of $M$ positions.

share|improve this answer
    
Exactly what I was looking for. Thanks! –  larry May 4 '12 at 19:12

If your string is an ordered sequence of characters $A=\{a_1,\dots,a_n\}$ and your substrings are contiguous subsequences, i.e. of consecutive terms of $A$, then they must start at some $a_i$. Since the substring has length $m$, it must then end at $a_{i+m-1}$. This gives you constraints $1\le i$ and $i+m-1\le n$ $\implies$ $i\le n-m+1$ or, altogether, $$1\le i\le n-m+1\,.$$ So how many starting places $i$ are possible for the substring?

share|improve this answer

It sort of depends on what you mean by substring. Look at the string ABABAB. How many substrings of length $2$ does it have? Start at the first letter. You get AB. Start at the second letter. You get BA. Start at the third letter. You get AB. Start at the fourth letter. You get BA. Start at the fifth letter. You get AB.

There were $5$ places to start, so in a certain sense we got five substrings. But there were only two different ones. So do we say $5$ or do we say $2$? Let us decide it is $5$. Of course, there cannot possibly be any ambiguity if the letters are all different.

So for simplicity assume the letters are all different. Now let's work out a few concrete case, and then everything will be obvious to you.

How many substrings of length $3$ are there in the string $12345678$? We can start anywhere up to and including $6$. So there are $6$ substrings of length $3$. Note that $6=8-3+1$.

How many substrings of length $3$ are there in the string $123456789ABC$? Note that our word has $12$ symbols, and we can start our substring at anything from $1$ to $A$, inclusive. So how many start points are there? Clearly $10$. Note that $10=12-3+1$.

Now we have the string $a_1a_2a_3\cdots a_{47}$. How many substrings of length $3$? The latest we can start is at $a_{45}$, so there are $45$ substrings. Note that $45=47-3+1$.

Now look at the string $a_1a_2a_3\cdots a_{100}$. How many substrings of length $8$? The latest we can start is at $a_{93}$, so there are $93$ substrings, and $93=100-8+1$.

Why is $a_{93}$ the last place we can start? We want to start at a place $p$ such that there are $8$ numbers from $p$ to $100$, inclusive. So there should be $100-8$ numbers from $1$ to $p-1$. Thus $p-1=92$, and therefore $p=93$.

Play with a few more concrete cases, they need not be too big. (So far, I have done all the playing, you have been reading.) Soon everything will be clear.

share|improve this answer

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.