Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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

3 Answers 3

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.

share|improve this answer
    
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.)

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.