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))?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Please include the question in the body of the question. Also. I have no idea what $C(N,i)$ means. $\endgroup$– Yuval FilmusCommented Oct 30, 2014 at 14:35
-
$\begingroup$ Do you mean different substrings? $\endgroup$– john_leoCommented Oct 30, 2014 at 16:06
-
$\begingroup$ Perhaps $C(N,i) = \binom{N}{i}$? Also, are the subsequences consecutive (i.e. $a_i,a_{i+1},\ldots,a_j$) or not (any subset of elements in the same order)? Your mention of $C(N,i)$ prompts me to think you mean the latter. $\endgroup$– Yuval FilmusCommented Oct 30, 2014 at 17:43
-
$\begingroup$ Sorry for not replying earlier, I forgot about this question. They are not consecutive, but subsequences, I think my method was wrong. $\endgroup$– jsguyCommented Nov 3, 2014 at 10:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ It depends on whether you want the subsequences to be consecutive or not. In the non-consecutive case, a priori it's not clear than $n$ is an upper bound. $\endgroup$ Commented Oct 30, 2014 at 17:44
-
$\begingroup$ Thats true, I edited my post to clearify the input of my answer. $\endgroup$– DannyCommented Oct 30, 2014 at 17:52