Number of substrings in a string: n-squared or exponential

Question

How many subtrings are there in a string in general?

Why does string x [1:n] have O(n^2) subtrings according to the lecture 21 Dynamic Programming III of        
6.006 from MIT? 
Why it is not O(2^n)?

Here is a link [http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec21.pdf]

Solution 1

Simply a substring is defined by two parameters [i,j] which are start index and end index for substring in the original string . Now 0<=i,j<=n as indices should be within the string, Total values i&j each can have are n so all combinations of [i,j] would be n*(n+1)/2 which is O(n^2)

Solution 2

Take a string length n=4, say: "ABCD"

The sub-strings of the above are (by length):

• 1 character: A,B,C,D (4 sub-strings)
• 2 character: AB,BC,CD, (3 sub-strings)
• 3 character: ABC,BCD (2 sub-strings)
• 4 character: ABCD (1 sub-string)

Totaling the numbers yields: 1+2+3+4 = 10.

So, to generalize, the number of possible sub-strings is the sum of all integers from 1 to n.

This sum is calculated using the formula (n^2 + n) / 2 (see here: Sum of Consecutive Numbers)

So the efficiency is of the n^2 order of magnitude.

Solution 3

Given a string of n elements,

If you start with 1st element, you can form n strings

If you start with 2nd element, you can form n-1 strings .... so on...

For example, take 1234

1,12,123,1234

2,23,234

3,34

4

As you can see, the total is n + (n-1) + (n-2) ...1 i.e. sum of n elements which is n(n+1)/2

Solution 4

you might have been confused with the number of subsets of a set but it is seemingly important here that these are the substrings which have fixed pattern and the value that you think 2^n, that will be the number of subsequences of the given string.

View more solutions

Comments

[zhushun0008]

Is any python function available?

[Gi0rgi0s]

Also, i < j so this isn't accurate. And 0,0 the trivial case doesn't count.

[Vikram Bhat]

Gi0rgi0s I know , this was just a order analysis so no need to go into details

[SDG]

This is a far superior answer than the accepted answer. This is the one that should have been accepted!

[Gi0rgi0s]

Looking back at this, I wonder...is the full string a substring? if not, then subtract one from the answer.

[Mingwei Samuel]

Or add 1 for the empty string ""

[Carl-Fredrik Nyberg Brodda]

This answer adds nothing to the answers from years ago.