How does `LongestCommonSubsequence` work?

Question

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

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

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]

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]

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.

Answer 1

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.