7,909 views
4 votes
4 votes
The possible number of prefixes for the given 'n' length string is (assume all symbols in the given string are different)

a) n

b) n+1

c) n+2

d) n-1

please explain.

6 Answers

1 votes
1 votes
Let's take a string=gate.Now the prefixes possible are:
{g,ga,gat,gate,epsilon}=5=N+1
Similarly suffixes are:{epsilon,gate,ate,te,e}=5=N+1.
1 votes
1 votes
Consider the string 011 over the binary alphabet. All the prefixes, suffixes, and substrings of this string are listed below.

Prefixes: $\varepsilon$, 0, 01, 011.
Suffixes: $\varepsilon$, 1, 11, 011.
Substrings: $\varepsilon$, 0, 1, 01, 11, 011.

Note that x is a prefix (suffix or substring) to x, for any string x and $\varepsilon$ is a prefix (suffix or substring) to any string.

A string x is a proper prefix (suffix) of string y if x is a prefix (suffix) of y and $x\neq y$

In the above example, all prefixes except 011 are proper prefixes.

No related questions found