proper non empty substrings

Question

The maximum no of proper non empty sub-strings for the given 'n' length string is:

A)    n*(n+1)/2    -   1

B)    n*(n+1)/2

C)    n*(n+1)/2   +  1

D)    none of the above

I basically want a good explanation here for whatever option you choose???thanks in advance .

<answer given as per coaching book is B>

Answer 1

take "abc" string. Sub strings are

1. a
2. b
3. c
4. ab
5. bc
6. abc

For a string of length n, we can have 1 sub-string of length n, 2 sub-strings of length n-1, 3 sub-strings of length n-2, ... n substrings of length 1. So, total no. of sub-strings = 1 + 2 + ... + n = n (n+1)/2

But the question asks for "proper" sub-strings. Proper sub-string means the given string (of length n) must not be counted. So, the answer must be n(n+1)/2 - 1.

Ref: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/StringMatch/stringMatchIntro.htm

Comments

Sir n(n+1)/2 is no of non empty substring..

But they asked "NO OF NON EMPTY PROPER SUBSTRING".. doesn't mean we have to eliminate NULL as well as ACTUAL STRING i.e. ABC ??

Not null & Proper means Non Trivial na ??

---

in choosing substrings why we can't have ac(i guess order changes).??what do you say??

---

Yes ac is not a substring of abc , keep them in order .

---

@laser is right. "Proper" sub-string would eliminate the given string. Answer must be A.
@Sumit "ac" would be part of sub-sequences. But a sub-string must be a continuous sub-sequence.

Answer 2

option a is right

Comments

abhishekmehta4u Sir the number of 0 length substring should be 1