# 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