The Gateway to Computer Science Excellence
+1 vote
12 views

In a string of length $n$, how many of the following are there?

  1.  Prefixes.
  2.  Suffixes.
  3.  Proper prefixes.
  4.  Substrings.
  5.  Subsequences.
in Compiler Design by Veteran (55k points)
edited by | 12 views

1 Answer

0 votes
  1. $n + 1 (n$ prefixes for $n$ characters, plus the empty string$)$
  2. $n + 1 ($similar to $(a))$
  3.  $n - 1 (n$ prefixes for $n$ characters, minus the string itself$)$
  4. $n [1$ character substring$] + (n - 1) [2$ character substring$] + \dots + 1 = \dfrac{n (n + 1)}{2}.$  Add $1$ to include the empty substring.
  5. $\displaystyle{}\sum_{i=0}^{n} {^{n}C_{i}} = 2^{n}$, if you include the empty subsequence.
by Active (1k points)
edited by

Related questions

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
50,645 questions
56,609 answers
195,893 comments
102,319 users