# Definition of longest common subsequences

Edit: I realized that I was confusing subsequences and substrings out of absent-mindedness. I've changed the post to reflect this. My question still stands.

I was shown this research problem: If x is a string of length m and y is a string of length n, then what is the maximum possible number of longest common subsequences between x and y as a function of m and n?

My question is: Is a longest common subsequence defined by its content, or by the positions of its character? Suppose you have string x = 1010, and string y = 10. Do they have 3 common subsequences of length 2 (x_1x_2 == y_1y_2 & x_3x_4 == y_1y_2 & x_1x_4 == y_1y_2), or just one (10 in x and 10 in y)?

Also, any suggestions on resources to look at and general approach? I figure I'll start with special case |x| = c < |y| or |x| = k|y|, probably with k = 1, and a binary alphabet. Is there any compelling reason why this potentially wouldn't be a good simplification to begin with?

-
From point of view of programming languages and implementations of substring function, there is only 2 substrings in y=1010 which matches x=10 string. It is like a window of size 2 positions which moves thought y and when matches blinks yellow;-) It is like searching for a *word in text, and not like searching for a unrestricted combination of letters in order. So probably You may define some another functions but this kind of implementation is standard one so probably may be respected as correct. –  kakaz Feb 25 '10 at 13:39

This is a strange issue to be stuck on: Just try to solve your problem for each definition, starting with the one that feels easier.

-
The situation here feels to me much like that of counting roots of a polynomial. S'pose I ask, out of the blue, "How many roots does x^3+x^2-x-1 have?" Maybe you say 2, or maybe you count -1 twice and say 3. Either one might be the "right answer", depending on why I want to know. Both are valid and reasonable questions. –  Cap Khoury Feb 25 '10 at 13:11
Sorry, but in my opinion Your example has three roots, and took zero value in two points. –  kakaz Feb 25 '10 at 13:32

I think that a subsequence is defined by "the positions of its characters," the same way that a subgroup is defined as a particular injection of one group into another: two groups may be isomorphic ("same content"), but represent distinct subgroups ("different position") of a larger group. (Strictly speaking, a subgroup is an equivalence class of injections, but you know what I mean.)

-
So, 2 "shared" longest common subsequences of x and y might differ just in the subsequence from x, both matching to the same y subsequence? –  DoubleJay Oct 28 '09 at 3:32

A subsequence is itself a sequence. For 1010 and 10 to have three common subsequences of length 2, there would have to exist three distinct sequences a, b and c of length 2, such that a, b and c are all subsequences of 1010 and 10 (which is not true).

Therefore, I feel it would be quite unnatural to define "longest common subsequence" including its position.

-