Question

When data is transmitted across a noisy channel,info can be lost during the transmission ,for ex-A message that is sent through a noisy channel as

"WHO PARKED ON HARRY'S POTTER SPOT?_" could be revised as the message

  "HOP ON POP_" i.e, some character could be lost during transmission,

so that only a selected portion of the original message is received.

We can model the phenomena using character string

X=x1,x2,x3.....xn,we say that a string

Y=y1,y2,y3.....ym,is a sub-sequence of X if there are set of in-dices

{i1,i2,i3...ik..in},such that y1=xi1, y2=xi2 .......yk=xik and ij<ij+1

for j=1 transcription of a received message is indeed a sub-sequence

of the message set.Therefore describe an O(n+m) time method for

determining if the given string Y of length m is a sub-sequence of a

given X of length n.

Answer 1

// Returns true if Y is a subsequence of X. m is
// length of Y and n is length of X
bool isSubSequence(char Y[], char X[], int m, int n)
{
// Base Cases
if (m == 0) return true;
if (n == 0) return false;

// If last characters of two strings are matching
if (Y[m-1] == X[n-1])
return isSubSequence(Y, X, m-1, n-1);

// If last characters are not matching
return isSubSequence(Y, X, m, n-1);
}

This method will return true if Y is subsequence of X or false otherwise.

Please note this method runs in O(m+n) time as it deletes atleast 1 chacrater from last of atleast one string in each recrsive step and hence size of either string will become 0 in atmax m+n recrsive calls.

Idea in this code is to start from end and see if chacrters are matching if yes then continue for second last charcter of each string. If last char is not matching then go to next char in original string. This will work as original string has to have all charcter for Y to be a subsequence.