Longest Common Subsequence

Published on 16 October 2018 (Updated: 11 February 2024)
Longest Common Subsequence

Welcome to the Longest Common Subsequence page! Here, you'll find a description of the project as well as a list of sample programs written in various languages.

This article was written by:

Description

Given two arrays of numbers, find the longest common subsequence. For example, let's say we have the following pair of arrays:

A = [1, 4, 5, 3, 15, 6]
B = [1, 7, 4, 5, 11, 6]

The longest common subsequence is 1, 4, 5, 6.

Requirements

Write a program which accepts two command line arguments–each list–and outputs the longest common subsequence between the two lists. Input arguments should be in comma separated list notation: 1, 2, 14, 11, 31, 7, 9.

Your program should be able to parse these lists into some internal representation in your choice language (ideally an array). From there, the program should compare the two arrays to find the longest common subsequence and output it in comma separated list notation to the user.

The following is recursive pseudocode that you can use for reference:

LCS(arrayA, arrayB, indexA, indexB):
  if indexA == 0 || indexB == 0:
    return 0
  else if arrayA[indexA - 1] == arrayB[indexB - 1]:
    return 1 + LCS(arrayA, arrayB, indexA - 1, indexB - 1)
  else:
    return max(LCS(arrayA, arrayB, indexA - 1, indexB), LCS(arrayA, arrayB, indexA, indexB - 1))

Unfortunately, this pseudocode only gives us the length of the longest common subsequence. Since we want to actually print the result, we'll probably need to augment this algorithm a bit. Also, it may be useful to implement the memoized solution for the sake of efficiency.

Testing

Every project in the Sample Programs repo should be tested. In this section, we specify the set of tests specific to Longest Common Subsequence. In order to keep things simple, we split up the testing as follows:

Lcs Valid Tests

Description Sequence 1 Sequence 2 Output
Sample Input Same Length "1, 4, 5, 3, 15, 6" "1, 7, 4, 5, 11, 6" "1, 4, 5, 6"
Sample Input Different Length "1, 4, 8, 6, 9, 3, 15, 11, 6" "1, 7, 4, 5, 8, 11, 6" "1, 4, 8, 11, 6"

Lcs Invalid Tests

Description Input
No Input  
Empty Input ""
Missing Input "25 15 10 5"

All of these tests should output the following:

Usage: please provide two lists in the format "1, 2, 3, 4, 5"

Articles