Cheap and Secure Web Hosting Provider : See Now

Given two sequences of the same size, how many longest common subsequences can they have?

, , No Comments
Problem Detail: 

For simplicity assume that both have the same size N.

the lengh of this subsequence can be at most N, so maybe it's

max(C(N,1), C(N,2), ... , C(N,N))?

Asked By : jsguy

Answered By : Danny

I understand the question as follows:

Given $n$. How many different longest common consecutive subsequences might two strings of length $n$ have at most?

If this is your question, than consider for example the string $a_1a_2...a_n$ with $a_i\ne a_j$ for $i\ne j$ and the reverse string $a_na_{n-1}...a_1$. The longest common subsequences of those strings are all subsequences of length $1$ $(a_1,a_2,...,a_n)$. Therefore, in your unrestricted question, the maximal number of different longest common subsequences of two strings of length $n$ is equal to the the maximal number of different subsequences with same length, which is $n$ for subsequences of length $1$.

If you restrict the question to strings over a given alphabet of fixed size, lets say $k$, the answer is much more difficult.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback