# An efficient algorithm that finds subsequences?

• Oct 19th 2013, 09:40 AM
Donna654
An efficient algorithm that finds subsequences?
Can anyone help me come up with a solution to this problem I found in my textbook please?

imgur: the simple image sharer

Thanks!
• Oct 19th 2013, 06:24 PM
SlipEternal
Re: An efficient algorithm that finds subsequences?
Start with any algorithm that gives the correct answer. Figure out where inefficiency arises and alter the algorithm to reduce it. Depending on the definition your book gives for "efficient", this may require several attempts until you get an efficient algorithm.

Example: If the length of a is smaller than the length of b, have the algorithm return the result when the sequences are swapped. Then, find the longest subsequence of $a$ that is also a subsequence of $b$. Then, proceed to add digits to the sequence $a$ until $b$ is a subsequence in its entirety.

This algorithm is not well defined, but it gives a basic idea of the process. It is probably extremely inefficient, since finding the longest subsequence of $a$ that is also a subsequence of $b$ requires checking all possible subsequences of one of the two and comparing it to the other.