A substring of a string w is a string whose symbols occur consecutively within w

Question

A substring of a string w is a string whose symbols occur consecutively within w For example, if w = inhabitant, substrings of w include hab, ant, abita, inhabitant and the empty string epsilon. Let sigma = {a, b, c, d, ellipsis y, z}. Suppose that x is a non-empty string over sigma and that |x| = n, for some positive integer n. What is the maximum number of substrings that x could have, as a function of n? Explain your answer. [As a specific example, the string dog (which has length 3) has 7 different substrings: epsilon, d, o, g, do, og, dog. Your job in this question is to give a formula that tells us the maximum number of substrings that any string of length n could have. Your formula can use summation notation if you want - for example, 1 + 2 + 4 + 8 + 16 + ellipsis + 2^n could be written as sigma_i = 0^n 2^i.]

Explanation / Answer

Total number of substring for a string of length n is 1 + (n)(n+1)/2

Proof:

so it will be 1 + n + n*(n-1)/2 = 1 + n(n+1)/2

so

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.