Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

When I recently came across this posting about LongestCommonSubsequence I was curious about how the function worked.

LongestCommonSubsequence appears to behave as I expected from the description in the documentation.

?LongestCommonSubsequence

lcss

For example

LongestCommonSubsequence["DOLORE", "LOREM"]
LongestCommonSubsequence[{"D", "O", "L", "O", "R", "E"}, {"L", "O", "R", "E", "M"}]

LongestCommonSubsequence["AD", "MAGNAD"]
LongestCommonSubsequence[{"A", "D"}, {"M", "A", "G", "N", "A", "D"}]

"LORE"
{"L", "O", "R", "E"}
"AD"
{"A", "D"}

The documentation provides very little information about LongestCommonSubsequencePositions , but it presumably returns the positions of the longest common substrings of two words (or lists of characters).

lcssp

Sometimes it behaves as I expect:

LongestCommonSubsequencePositions["DOLORE", "LOREM"]
LongestCommonSubsequencePositions[{"D", "O", "L", "O", "R", "E"},

{{3, 6}, {1, 4}}
{{3, 6}, {1, 4}}

At other times it returns the positions in the incorrect order:

LongestCommonSubsequencePositions["AD", "MAGNAD"]
LongestCommonSubsequencePositions[{"A", "D"}, {"M", "A", "G", "N", "A", "D"}]

{{5, 6}, {1, 2}}
{{5, 6}, {1, 2}}

Is this a bug? Or am I misunderstanding how LongestCommonSubsequencePositions works?


Edit

HyperGroups raises the hypothesis that the relative string length of the words may lie behind this behavior. Let's do a quick check. In the examples below, the first word grows in length until it surpasses the stringlength of the second word.

 d = {{"AD", "MAGNAD"}, {"ADE", "MAGNAD"}, {"ADEV", "MAGNAD"}, {"ADEVO", "MAGNAD"},  
 {"ADEVOL", "MAGNAD"}, {"ADEVOLT", "MAGNAD"}, {"ADEVOLTI", "MAGNAD"}, 
 {"ADEVOLTIC", "MAGNAD"}, {"ADEVOLTICK", "MAGNAD"}};

 TableForm[{#, LongestCommonSubsequence @@ #, LongestCommonSubsequencePositions @@ #, 
 (StringLength[#[[1]]] > StringLength[#[[2]]])} & /@ d]

data

There is clear support for this idea. Whenever the length of the lefthand word is equal to or greater than that of the righthand word, the greatest common substring positions are returned in the respective order. Otherwise, the order of the positions is inverted.


The same pattern holds for words given as lists of characters. (Note: Length is used instead of StringLength.)

d1 = Characters@d;
TableForm[{#, LongestCommonSubsequence @@ #, LongestCommonSubsequencePositions @@ #, 
(Length[#[[1]]] >  Length[#[[2]]])} & /@ d1]

data1

By the way, LongestCommonSubsequence seems to work correctly whenever the strings are of the same length (I checked by running the same tests, but with the order of each pair reversed.)


The question remains: Why does this happen? Bug or feature?

Looks to me like a bug, one that can be kept under control by checking the relative stringlengths and correcting when needed.

share|improve this question
    
maybe the function SortBy StringLength and works In[147]:= LongestCommonSubsequencePositions["DOLORE","LOREMJKKJLKJL"] Out[147]= {{1,4},{3,6}} So now {1,4} is in the left –  HyperGroups May 10 '13 at 5:21
add comment

1 Answer

up vote 2 down vote accepted

Maybe this

LongestCommonSubsequencePositions["DOLORE","LOREM"]
LongestCommonSubsequencePositions[{"D","O","L","O","R","E"},{"L","O","R","E","M"}]
{{3,6},{1,4}}
{{3,6},{1,4}}
LongestCommonSubsequencePositions["DOLORE", "LOREMIJKLMKJLKJLKJLJK"]
LongestCommonSubsequencePositions[{"D", "O", "L", "O", "R", "E"}, Characters@"LOREMIJKLMKJLKJLKJLJK"]
{{1,4},{3,6}}
{{1,4},{3,6}}

The shorter string's position is always in the right of the result.

share|improve this answer
    
You appear to be correct in your hypothesis. (See edit.) –  David Carraher May 10 '13 at 16:27
add comment

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.