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?

*wordin 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