recategorized by
1 flag 9,912 views
26 votes
26 votes

The number of substrings (of all lengths inclusive) that can be formed from a character string of length $n$ is

  1. $n$
  2. $n^2$
  3. $\frac{n(n-1)}{2}$
  4. $\frac{n(n+1)}{2}$
  • ๐Ÿšฉ Edit necessary | ๐Ÿ‘ฎ PreyumKr | ๐Ÿ’ฌ โ€œoptions are incorrect. +1 needed in the last option.โ€
recategorized by
1 flag

5 Answers

Best answer
30 votes
30 votes
  • Number of substrings of length $n$ is $1$.
  • Number of substrings of length $(n-1)$ is $2$.
  • Number of substrings of length $(n-2)$ is $3$.

So, total number of substrings $=\frac{n(n+1)}{2}$.

Correct Answer: D.

edited by
1 flag:
โœŒ Edit necessary (PreyumKr โ€œThe answer is wrong, it should have a plus 1 for 0 length substring!!!โ€)
12 votes
12 votes

The length of substrings are n or n-1 or n-2 or....or 2 or 1 or 0

let the string is abcd...xyz

no.of substrings of length 'n' = 1           ------  abcd....xyz

no.of substrings of length 'n-1' = 2       ------  abcd....xy , bcd....xyz

no.of substrings of length 'n-2' = 3       ------  abcd....x , bcd....xy , cdef.....xyz

.......

no.of substrings of length '2' = n-1      -----  ab,bc,cd,....vx,xy,yz

no.of substrings of length '1' = n         ------  a,b,c,d,....x,y,z

no.of substrings of length '0' = 1 ----> only empty string is possible

total substrings = 1+2+3+...+(n-1) + n + 1

                         = [ 1+2+3+...+(n-1) + n ] + 1

                         = $\frac{n(n+1)}{2}$ + 1

                         =  โˆ‘n + 1

 

NOTE :-

Trivial substrings :- empty string ( which is length = 0 ) and the original string ( which is length = n ) are trivial strings.

                      โˆด No.of Trivial substrings are 2 for any non-empty string

Non- Trivial substrings :-  which are not Trivial substrings are called as Non- Trivial substrings.

                      โˆด No.of Non-Trivial substrings are โˆ‘n - 1

Proper Substrings :- the substring which length is less than actual string

                      โˆด No.of Non-Trivial substrings are โˆ‘n

Non-empty Substrings :- the substring which length is grater than 0

                      โˆด No.of Non-Empty substrings are โˆ‘n

1 votes
1 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


Correct Answer: D

edited by
0 votes
0 votes
  • Number of substrings of length  is 1= n
  • Number of substrings of length 2 is =n-1
  • Number of substrings of length 3 is =n-2
  •                
  •                
  •               
  • Number of substrings of length  is n= 1

so total number of substrings= n + (n-1) + (n-2)+โ€ฆโ€ฆ..+1

                                                  sum of n natural number

                                                =  n(n+1) / 2 

 

 

 

       .

 

       

Answer:

Related questions

76 votes
76 votes
12 answers
1
Kathleen asked Oct 4, 2014
34,438 views
The number of distinct simple graphs with up to three nodes is$15$$10$$7$$9$
18 votes
18 votes
2 answers
2
Kathleen asked Oct 5, 2014
1,966 views
Use the patterns given to prove that$\sum\limits_{i=0}^{n-1} (2i+1) = n^2$(You are not permitted to employ induction)Use the result obtained in (A) to prove that $\sum\li...