When data is transmitted across a noisy channel information

When data is transmitted across a noisy channel. information can be lost during the transmission. For example, a message that is sent through a noisy channel as \"WHO PARKED ON HARRY POTTER\'S SPOT?\" could be received as the message, \"HOP ON POP\" That is, some characters could be lost during the transmission, so that only a selected portion of the original message is received. We can model this phenomenon using character strings, where, given a string X = x_1x_2... x_n, we say that a string Y = y_1 y_2... y_m is a subsequence of X if there are a set of indices {i_1, i_2, ..., i_k}. such that y_1 = y_2 = x_i2... y_k = x_ik, and i_j

Solution

A greedy solution will give us the solution in linear time.

Start with finding the first letter of the output transmission (hpr) in the original transmission(*h*arrypotter)
Second step is to find the second letter starting at the index of the first letter plus one (arry*p*otter), ignoring the letters we have matched already.
Continue the above two steps till all the letters in the output transmission have been matched, i.e. find the third letter starting at the index of the second letter plus one (otte*r*)
Stop when we run out of letters (MATCH) or till the letters of output are not present in the original.
Complexity: O(n) n=length of original transmission