retagged by
6,801 views
37 votes
37 votes
How many substrings (of all lengths inclusive) can be formed from a character string of length $n$? Assume all characters to be distinct, prove your answer.
retagged by

5 Answers

0 votes
0 votes

If you have a string of length n 
Then you’ll have, 

n strings of length 1

n-1 strings of length 2

n-2 strings of length 3

n-4 strings of length 5

.

.

.

.

3 strings of length of n-2

2 strings of length n-1

1 string of length n

 

 Therefore total substrings will be n+(n-1)+(n-2)+(n-3)+........+3+2+1 = n(n+1)/2
_______________________________________________________________________________________________

Example : VARUN HAS LENGTH 5

5 strings of length  1 = {V,A,R,U,N}

4 strings of length  2 = {VA,AR,RU,UN}

3 strings of length  3 = {VAR,ARU,RUN}

2 strings of length  4 = {VARU,ARUN}

1 strings of length  5 = {VARUN}

Therefore total substrings will be 5+(5-1)+(5-2)+(5-3)+(5-4)+(5-5) = 5(5+1)/2 = 15

Related questions

11 votes
11 votes
1 answer
1
makhdoom ghaya asked Nov 30, 2016
7,135 views
For secondary key processing which of the following file organizations is preferred? Give a one line justification:Indexed sequential file organization.Two-way linked lis...
19 votes
19 votes
5 answers
2
31 votes
31 votes
4 answers
3
makhdoom ghaya asked Nov 27, 2016
7,721 views
Which of the following graphs is/are planar?
0 votes
0 votes
0 answers
4