The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
137 views
The number of substrings(of all lengths inclusive) that can be formed from character string of length n is

a)n

b)n^2

c)n(n-1)/2

d)(n(n+1)/2)+1
asked in Theory of Computation by (15 points) | 137 views
+1
let's take an example:

s = ABC

length 0 = 1

lenght 1 = {A , B , C} = 3

length 2 = {AB , BC } = 2

length 3 = {ABC} = 1

total string = length 0 + length 1 + length 2 + length  3 = 1 + 3 + 2 + 1 = 7

option D is the correct answer
0
For length 2,why have u not considered AC?
+1
@anji

AC is not  Substring of ABC   because it is separated by B , Substring is that in which we add another substring , in either left are Right side of Substring to get actual Substring.
0
+2

Substring is defined as "Zero or more Consecutive symbols taken"

What you must be confusing it with is "Subsequence" which is defined as "Zero or more Symbols left out (Consecutive or Not)"


Subword is defined as "One or more Consecutive symbols taken" (Subword is same as substring except for Zero length string)

2 Answers

+3 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

answered by Boss (31.3k points)
0 votes
In exam if we just want to find correct option then take any small example..

Like s=ab (n=2)

Substrings=a,b,ab,ε(epsilon)=4 substrings possible.

Hence we found that only last option is correct.:)
answered by Active (1.5k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,819 questions
47,498 answers
145,755 comments
62,259 users