Comparing two sequences of characters arises in several applications including the life sciences and information retrieval. Suppose you are given two sequences of characters drawn from a common alphabet: S of length m and T of length n, each possibly containing a character more than once. We say that S is a subsequence of T if S can be obtained from T by deleting some characters from T. For instance, the sequence A,T,C,T,G is a subsequence of G,A,A,A,T,C,G,G,T,T,G. (Positions indicating the subsequence property are underlined.)

Give an algorithm that takes as input two sequences S and T and determines whether S is a sub- sequence of T . Prove the correctness of your algorithm and state its time complexity.

Answer rating: 100% (QA)

function that returns if a given S of length m is Sub sequence of String T of length n it is a linea... View the full answer