# Longest Common Subsequence in Mathematica

Published on 19 January 2023 (Updated: 19 January 2023)

Welcome to the Longest Common Subsequence in Mathematica page! Here, you'll find the source code for this program as well as a description of how the program works.

## Current Solution

``````(* Code *)

(* Longest Common Subsequence option longestCommonSubsequence1 is just a Mathematica built-in
(note that Mathematica LongestCommonSubsequence searches only for contiguous subsequences): *)

longestCommonSubsequence1 = LongestCommonSequence;

(* If that is considered cheating, then option longestCommonSubsequence2 implements it directly: *)

longestCommonSubsequence2 = Function[{l, r},
(* if either list is empty, the LCS is also empty *)
If[Length[l] == 0 \[Or] Length[r] == 0, {},
(* if first element of both lists match, recurse after removing that element *)
If[First[l] == First[r],
Prepend[longestCommonSubsequence2[Rest[l], Rest[r]], First[l]],
(* recurse by computing LCS of removing either first element from the left or from the right list *)
Module[{ll = longestCommonSubsequence2[Rest[l], r], rr = longestCommonSubsequence2[l, Rest[r]]},
(* pick whichever produces the longest LCS *)
If[Length[ll] > Length[rr], ll, rr]]]]];

(* The outer function provides the 'user interface' (e.g., the string parsing): *)

longestCommonSubsequenceMain = Function[{left, right},
Module[{e = "Usage: please provide two lists in the format \"1,2,3,4,5\""},
Catch[
StringRiffle[
longestCommonSubsequence2 @@
Map[
(* convert string to integer, or throw *)
s \[Function] If[StringMatchQ[s, DigitCharacter ..],
FromDigits[s],
Throw[e]],
(* construct two arguments to longestCommonSubsequence: left list, right list *)
{
If[StringLength[left] > 0, StringSplit[left, ", "], Throw[e]],
If[StringLength[right] > 0, StringSplit[right, ", "],
Throw[e]]
},
{-1} (* at each leaf *)],
", "]]]];

(* Valid Tests *)

Print /@ Apply[longestCommonSubsequenceMain] /@ {
{"1, 4, 5, 3, 15, 6", "1, 7, 4, 5, 11, 6"},
{"1, 4, 8, 6, 9, 3, 15, 11, 6", "1, 7, 4, 5, 8, 11, 6"}
};

(* Invalid Tests *)

longestCommonSubsequenceMain["3", ""]

``````

Longest Common Subsequence in Mathematica was written by:

• Ben Hekster

If you see anything you'd like to change or update, please consider contributing.

## How to Implement the Solution

No 'How to Implement the Solution' section available. Please consider contributing.

## How to Run the Solution

No 'How to Run the Solution' section available. Please consider contributing.