For this assignment, you will implement Hirschberg’s algorithm to compute the longest common subsequence between two strings. Your implementation should return the longest common subsequence between the two input strings. If you implement the brute force space inefficient version, you will lose 20 points. The input strings will be created with strings containing lowercase and uppercase characters.

The starter code is provided. As usual, you have the option of completing the project in either C++ or Java. Read the following submission guidelines carefully to ensure that the autograder can properly evaluate your work.

When submitting, zip the exact files listed below for the language you use using the same directory structure, and upload the zip file to gradescope. For any questions/clarifications, please ask on Ed.

C++

In the C++ directory, you will find the following files.

main.cpp *
lcs.h *
language.txt *
Makefile *
lcs.cpp

Do not edit the files marked with an asterisk (*), as this could interfere with the autograder. You should only edit the “lcs.cpp” file to implement the skew algorithm. To test your code locally, you can use make to build and compile the project, which will generate “project6”. The program will take 2 command line parameters which are the strings between which your program should find the longest common substring.

$ ./project6 [string1] [string2]

Java

In the Java directory, you will find the following files.

language.txt *
project6
|- Main.java * 
|- LCS.java

Do not edit the files marked with an asterisk (*), as this could interfere with the autograder. You should only edit the “LCS.java” file to implement the skew algorithm. To test your code locally, you can use make to build and compile the project, which will generate “project6”. The program will take 2 command line parameters which are the strings between which your program should find the longest common substring.

javac project6/*.java
java project6.Main [string1] [string2