Welcome to MathOverflow

Question

0

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?

edited Feb 25 2010 at 12:41

gowers
17.8k●9●77●131

asked Oct 28 2009 at 2:24

DoubleJay
1,269●11●29

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 2010 at 13:39

rgrig · Answer 1 · 2009-10-28 10:47:16Z UTC

2

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.

answered Oct 28 2009 at 10:47

rgrig
531●7●12

	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 2010 at 13:11
	Sorry, but in my opinion Your example has three roots, and took zero value in two points. – kakaz Feb 25 2010 at 13:32

David Steinberg · Answer 2 · 2009-10-28 03:06:30Z UTC

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.)

Douglas S. Stones · Answer 3 · 2010-02-25 12:19:23Z UTC

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.

Definition of longest common subsequences

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.