Cheap and Secure Web Hosting Provider : See Now

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

, ,
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))`?

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.