Comparing two sequences of characters arises in several applications including the life sciences and information retrieval. Suppose
Question:
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.
An Introduction to the Mathematics of financial Derivatives
ISBN: 978-0123846822
2nd Edition
Authors: Salih N. Neftci