Longest common substring

Assignment 

package edu.wit.cs.comp2350;

import java.io.IOException;

import java.nio.file.Files;

import java.nio.file.Paths;

import java.util.Scanner;

/* Aligns strings in two text files by matching their longest common substring

*

* Wentworth Institute of Technology

* COMP 2350

* Lab Assignment 7

*

*/

public class LAB7 {

//TODO Document this method

public static String[] findLCSdyn(String text1, String text2) {

// TODO Implement this method

// TODO set static var “longest” to longest common subsequence length

return new String[]{“”, “”};

}

/********************************************

*

* You shouldn’t modify anything past here

*

********************************************/

private static int longest = -1;

// recursive helper for DFS

private static void dfs_solve(int i1, int i2, String s1, String s2, char[] out1, char[] out2, int score, int index) {

if ((i1 >= s1.length()) && (i2 >= s2.length())) {

if (score > longest) {

out1[index] = ‘\0’;

out2[index] = ‘\0’;

longest = score;

sol1 = String.valueOf(out1).substring(0, String.valueOf(out1).indexOf(‘\0’));

sol2 = String.valueOf(out2).substring(0, String.valueOf(out2).indexOf(‘\0’));

}

}

else if ((i1 >= s1.length()) && (i2 < s2.length())) {     // at the end of first string

out1[index] = ‘-‘;

out2[index] = s2.charAt(i2);

dfs_solve(i1, i2 + 1, s1, s2, out1, out2, score, index+1);

}

else if ((i1 < s1.length()) && (i2 >= s2.length())) {     // at the end of second string

out1[index] = s1.charAt(i1);

out2[index] = ‘-‘;

dfs_solve(i1 + 1, i2, s1, s2, out1, out2, score, index+1);

}

else {

if (s1.charAt(i1) == s2.charAt(i2)) { // matching next character

out1[index] = s1.charAt(i1);

out2[index] = s2.charAt(i2);

dfs_solve(i1 + 1, i2 + 1, s1, s2, out1, out2, score + 1, index + 1);

}

out1[index] = ‘-‘;

out2[index] = s2.charAt(i2);

dfs_solve(i1, i2 + 1, s1, s2, out1, out2, score, index + 1);

out1[index] = s1.charAt(i1);

out2[index] = ‘-‘;

dfs_solve(i1 + 1, i2, s1, s2, out1, out2, score, index + 1);

}

}

// Used for DFS solution

private static String sol1, sol2;

// recursively searches for longest substring, checking all possible alignments

public static String[] findLCSdfs(String text1, String text2) {

int max_len = text1.length() + text2.length() + 1;

char[] out1 = new char[max_len];

char[] out2 = new char[max_len];

dfs_solve(0, 0, text1, text2, out1, out2, 0, 0);

String[] ret = new String[2];

ret[0] = sol1; ret[1] = sol2;

return ret;

}

// returns the length of the longest string

public static int getLongest() {

return longest;

}

public static void main(String[] args) {

Scanner s = new Scanner(System.in);

String file1, file2, text1 = “”, text2 = “”;

System.out.printf(“Enter <text1><text2><algorithm>, ([dfs] – depth first search, [dyn] – dynamic programming): “);

System.out.printf(“(e.g: text/a.txt text/b.txt dfs)\n”);

file1 = s.next();

file2 = s.next();

try {

text1 = new String(Files.readAllBytes(Paths.get(file1)));

text2 = new String(Files.readAllBytes(Paths.get(file2)));

} catch (IOException e) {

System.err.println(“Cannot open files ” + file1 + ” and ” + file2 + “. Exiting.”);

System.exit(0);

}

String algo = s.next();

String[] result = {“”};

switch (algo) {

case “dfs”:

result = findLCSdfs(text1, text2);

break;

case “dyn”:

result = findLCSdyn(text1, text2);

break;

default:

System.out.println(“Invalid algorithm”);

System.exit(0);

break;

}

s.close();

System.out.printf(“Best cost: %d\nLongest string alignment:\n%s\n\n%s\n”, longest, result[0], result[1]);

}

} 

ChartMaker.java

package edu.wit.cs.comp2350.tests;

import java.awt.Color;

import java.util.Random;

import javax.swing.JPanel;

import org.jfree.chart.ChartFactory;

import org.jfree.chart.ChartPanel;

import org.jfree.chart.JFreeChart;

import org.jfree.chart.plot.PlotOrientation;

import org.jfree.chart.plot.XYPlot;

import org.jfree.chart.renderer.xy.XYLineAndShapeRenderer;

import org.jfree.data.function.Function2D;

import org.jfree.data.general.DatasetUtilities;

import org.jfree.data.xy.XYDataset;

import org.jfree.ui.ApplicationFrame;

import org.jfree.ui.RefineryUtilities;

import edu.wit.cs.comp2350.LAB7;

/**

* An example showing how to plot a simple function in JFreeChart.  Because

* JFreeChart displays discrete data rather than plotting functions, you need

* to create a dataset by sampling the function values.

*/

public class ChartMaker extends ApplicationFrame {

private static final long serialVersionUID = 1L;

private static final int DATASETS = 2;

/**

* Creates a new demo.

*

* @param title  the frame title.

*/

public ChartMaker(String title) {

super(title);

JPanel chartPanel = createDemoPanel();

chartPanel.setPreferredSize(new java.awt.Dimension(700, 400));

setContentPane(chartPanel);

}

/**

* Creates a chart with four datasets of algorithm runtimes and

* sets appearance of chart objects.

*

* @return A chart instance.

*/

private static JFreeChart createChart() {

XYDataset[] data = new XYDataset[DATASETS];

data[0] = createDataset(“dfs”, “depth-first search”);

data[1] = createDataset(“dyn”, “dynamic programming”);

JFreeChart chart = ChartFactory.createXYLineChart(

“DNA alignment runtimes”,  // chart title

“number of basepairs”,     // x axis label

“time(ms)”,                // y axis label

data[0],                   // data

PlotOrientation.VERTICAL,

true,                      // include legend

true,                      // tooltips

false                      // urls

);

XYPlot plot = (XYPlot) chart.getPlot();

plot.getDomainAxis().setLowerMargin(0.0);

plot.getDomainAxis().setUpperMargin(0.0);

XYLineAndShapeRenderer renderer[] = new XYLineAndShapeRenderer[DATASETS];

for (int i = 0; i < DATASETS; i++) {

plot.setDataset(i, data[i]);

renderer[i] = new XYLineAndShapeRenderer();

plot.setRenderer(i, renderer[i]);

}

plot.getRendererForDataset(plot.getDataset(0)).setSeriesPaint(0, Color.red);

plot.getRendererForDataset(plot.getDataset(1)).setSeriesPaint(0, Color.blue);

return chart;

}

/**

* Creates a dataset based on algorithm runtimes.

*

* @param algo  The string used to represent algorithm

* @param name  The name of algorithm to appear in the legend

*

* @return A sample dataset.

*/

public static XYDataset createDataset(String algo, String name) {

XYDataset result = DatasetUtilities.sampleFunction2D(new AddRuns(algo),

8.0, 15.0, 8, name);

return result;

}

/**

* Creates a panel for the demo (used by SuperDemo.java).

*

* @return A panel.

*/

public static JPanel createDemoPanel() {

JFreeChart chart = createChart();

return new ChartPanel(chart);

}

/**

* Generates all the runtimes for the graph.

*/

static class AddRuns implements Function2D {

private String algo;

public AddRuns(String a) { algo = a; }

// t is the number of characters in each string

public double getValue(double t) {

double sec = 0;

 

if (t == 0)

return 0;

String text1 = randDNA(Double.valueOf(t).intValue());

String text2 = randDNA(Double.valueOf(t).intValue());

long start = System.nanoTime();

switch (algo) {

case “dfs”:

LAB7.findLCSdfs(text1, text2);

break;

case “dyn”:

LAB7.findLCSdyn(text1, text2);

break;

default:

System.out.println(“Invalid algorithm”);

System.exit(0);

break;

}

long end = System.nanoTime();

sec += (end-start)/1E6;

return sec;

}

private String randDNA(int intValue) {

String alphabet = “TCGA”;

int len = alphabet.length();

String ret = “”;

Random r = new Random();

for (int i = 0; i < intValue; i++) {

ret += alphabet.charAt(r.nextInt(len));

}

return ret;

}

}

/**

* Starting point for the chartmaker.

*

* @param args  ignored.

*/

public static void main(String[] args) {

ChartMaker cm = new ChartMaker(

“Chart Window”);

cm.pack();

RefineryUtilities.centerFrameOnScreen(cm);

cm.setVisible(true);

}

} 

LAB7TestCase.java

 package edu.wit.cs.comp2350.tests;

import java.io.IOException;

import java.nio.file.Files;

import java.nio.file.Paths;

import java.security.Permission;

import org.junit.After;

import org.junit.Before;

import org.junit.Rule;

import org.junit.Test;

import org.junit.rules.Timeout;

import edu.wit.cs.comp2350.LAB7;

import static org.junit.Assert.*;

public class LAB7TestCase{

@Rule

public Timeout globalTimeout = Timeout.seconds(15);

@SuppressWarnings(“serial”)

private static class ExitException extends SecurityException {}

private static class NoExitSecurityManager extends SecurityManager

{

@Override

public void checkPermission(Permission perm) {}

@Override

public void checkPermission(Permission perm, Object context) {}

@Override

public void checkExit(int status) { super.checkExit(status); throw new ExitException(); }

}

@Before

public void setUp() throws Exception

{

System.setSecurityManager(new NoExitSecurityManager());

}

@After

public void tearDown() throws Exception

{

System.setSecurityManager(null);

}

private void _testDynLen(String s0, String s1, int expectedLongest) {

int actualLongest = 0;

try {

LAB7.findLCSdyn(s0, s1);

actualLongest = LAB7.getLongest();

} catch (ExitException e) {}

assertEquals(“Longest value is incorrect.”, expectedLongest, actualLongest);

}

private void _testFileDynLen(String f1, String f2, int expectedBest) {

String t1 = “”;

String t2 = “”;

try {

t1 = new String(Files.readAllBytes(Paths.get(f1)));

t2 = new String(Files.readAllBytes(Paths.get(f2)));

} catch (IOException e) {

}

_testDynLen(t1, t2, expectedBest);

}

private void _testDynStr(String s0, String s1, int expectedLongest) {

String[] actual = new String[0];

String act0 = “”;

String act1 = “”;

try {

actual = LAB7.findLCSdyn(s0, s1);

} catch (ExitException e) {}

assertEquals(“Length of results should be the same,”, actual[0].length(), actual[1].length());

for (int i = 0; i < actual[0].length(); i++) {

if ((actual[0].charAt(i) != ‘-‘) && (actual[1].charAt(i) != ‘-‘))

assertEquals(“Characters at same positions should be the same.”, actual[0].charAt(i), actual[1].charAt(i));

if (actual[0].charAt(i) != ‘-‘)

act0 += actual[0].charAt(i);

if (actual[1].charAt(i) != ‘-‘)

act1 += actual[1].charAt(i);

}

assertEquals(“First string doesn’t match result.”, s0, act0);

assertEquals(“Second string doesn’t match result.”, s1, act1);

}

private void _testFileDynStr(String f1, String f2, int expectedBest) {

String t1 = “”;

String t2 = “”;

try {

t1 = new String(Files.readAllBytes(Paths.get(f1)));

t2 = new String(Files.readAllBytes(Paths.get(f2)));

} catch (IOException e) {

}

_testDynStr(t1, t2, expectedBest);

}

@Test

public void testSmallLen() {

_testDynLen(“overlap”, “overlop”, 6);

_testDynLen(“sap”, “sip”, 2);

_testDynLen(“ACGGAT”, “CCGCTT”, 3);

_testDynLen(“ACCCGAG”, “TCCTACGG”, 5);

_testDynLen(“big”, “even bigger”, 3);

}

@Test

public void testSmallStr() {

_testDynStr(“overlap”, “overlop”, 6);

_testDynStr(“sap”, “sip”, 2);

_testDynStr(“ACGGAT”, “CCGCTT”, 3);

_testDynStr(“ACCCGAG”, “TCCTACGG”, 5);

_testDynStr(“big”, “even bigger”, 3);

}

@Test

public void testLargeLen() {

_testFileDynLen(“text/melania.txt”, “text/michelle.txt”, 330);

_testDynLen(“GTCGTTATGCTAGTATACGCCTACCCGTCACCGGCCATCTGTGTGCAGATGGGGCGACGAGTTACTGGCCCTGATTTCTCCGCTTCTAATACCACACACTGGGCAATACGAGCTCAAGCCAGTCTCGCAGTAACGCTCATCAGCTAACGAAAGAGTTAGAGGCTCGCTAATTCGCACTGTCGGGGTCCCTTGGGTGTTTTGCACTAGCGTCAGGTAGGCTAGTATGTGTCTTTCCTTCCAGGGGTATGTGGCTGCGTGGTCAAATGTGCAGCATACGTATTTGCTCGGCGTGCTTGGTCTCTCGTACTTCTCCTGGAGATCAAGGAAATGTTTCTTGTCCAAGCGGACAGCGGTTCTACGGAATGGATCTACGTTACTGCCTGCATAAGGAGAACGGAGTTGCCAAGGACGAAAGCGACTCTAGGTTCTAACCGTCGACTTTGGCGGAAAGGTTTCACTCAGGAAGCAGACACTGATTGACACGGTTTAGCAGAACGTTTGAGGATTAGGTCAAATTGAGTGGTTTAATATCGGTATGTCTGGGATTAAAATATAGTATAGTGCGCTGATCGGAGACGAATTAAAGACACGAGTTCCCAAAACCAGGCGGGCTCGCCACGACGGCTAATCCTGGTAGTTTACGTGAACAATGTTCTGAAGAAAATTTATGAAAGAAGGACCCGTCATCGCCTACAATTACCTACAACGGTCGACCATACCTTCGATTGTCGTGGCCACCCTCGGATTACACGGCAGAGGTGGTTGTGTTCCGATAGGCCAGCATATTATCCTAAGGCGTTACCCCAATCGTTTTCCGTCGGATTTGCTATAGCCCCTGAACGCTACATGCACGAAACCAAGTTATGTATGCACTGGGTCATCAATAGGACATAGCCTTGTAGTTAACATGTAGCCCGGCCGTATTAGTACAGTAGAGCCTTCACCGGCATTCTGTTTATTAAGTTATTTCTACAGCAAAACGATCATATGCAGATCCGCA”, “GTGCGCGGTAGAGACACGTCCACCCGGCTGCTCTGTAATAGGGACTAAAAAAGTGATGATTATCATGAGTGCCCCGTTATGGTCGTGTTCGATCAGAGCGCTCTTACGAGCAGTCGTATGCTTTCTCGAATTCCGTGCGGTTAAGCGTGACAGTCCCAGTGAACCCACAAAACGTGATGGCAGTCCATGCGATCATACGCAAGAAGGATGGTCTCCAGACACCGGCGCACCAGTTTTCACGCCGAAAGCATAAACGAGGAGCACAAATGAGAGTGTTTGAACTGGACCTGTAGTTTCTCTACGAAGAACACCTTGAGCTGTTGCGTTGTTGCGCTGCCTAGATGCAGTGTCGCACGTATCACTTTTGCCTCAACGACTGCTGCTTTCGCTGTAACCCTAGACAGACAACAGTAAGCGCCTTTTGTAGGCAAGAGCTCCGCCTGTGACTAACTGCGCCAAAACGTCTTCCAATCCCCTTATCCAATTTAACTCACCGAATTCTTACAATTTAGACCCTAATATCACATCATTAGACACTAATTGCCTCTGCCAAAATTCTGTCCACAAGCGTTTTAGTTCGCCCCAGTAAAGTTGTCAATAACGACCACCAAATCCGCATGTTACGGGACTTCTTATTAATTCTTTTTTCGTGGGGAGCAGCGGATCTTAATGGATGGCGCCAGGTGGTATGGAAGCTAATAGCGCGGGTGAGAGGGTAATCAGCCGTCTCCACCAACACAACGCTATCGGGTCATACTATAAGATTCCGCAATGCGACTACTTATAAGATGCCTTAACGGTATCCGCAACTTGCGATGTGCCTGCTATGCTTAAATGCATATCTCGCCCAGTAGCTTTCCAATATGAGAGCATCAATTGTAGATCGGGCCGGGATAATCATGTCGTCACGGAACTTACTGTAAGAGTAATAATTTAAAAGAGATGTCGGTTTGCTGGTTCACGTAAAGGTCCCTCGCGCTACCTCTAAGTAAGTGAGCGG”, 646);

_testFileDynLen(“text/znc1.txt”, “text/znc2.txt”, 3827);

}

@Test

public void testLargeStr() {

_testFileDynStr(“text/melania.txt”, “text/michelle.txt”, 330);

_testDynStr(“GTCGTTATGCTAGTATACGCCTACCCGTCACCGGCCATCTGTGTGCAGATGGGGCGACGAGTTACTGGCCCTGATTTCTCCGCTTCTAATACCACACACTGGGCAATACGAGCTCAAGCCAGTCTCGCAGTAACGCTCATCAGCTAACGAAAGAGTTAGAGGCTCGCTAATTCGCACTGTCGGGGTCCCTTGGGTGTTTTGCACTAGCGTCAGGTAGGCTAGTATGTGTCTTTCCTTCCAGGGGTATGTGGCTGCGTGGTCAAATGTGCAGCATACGTATTTGCTCGGCGTGCTTGGTCTCTCGTACTTCTCCTGGAGATCAAGGAAATGTTTCTTGTCCAAGCGGACAGCGGTTCTACGGAATGGATCTACGTTACTGCCTGCATAAGGAGAACGGAGTTGCCAAGGACGAAAGCGACTCTAGGTTCTAACCGTCGACTTTGGCGGAAAGGTTTCACTCAGGAAGCAGACACTGATTGACACGGTTTAGCAGAACGTTTGAGGATTAGGTCAAATTGAGTGGTTTAATATCGGTATGTCTGGGATTAAAATATAGTATAGTGCGCTGATCGGAGACGAATTAAAGACACGAGTTCCCAAAACCAGGCGGGCTCGCCACGACGGCTAATCCTGGTAGTTTACGTGAACAATGTTCTGAAGAAAATTTATGAAAGAAGGACCCGTCATCGCCTACAATTACCTACAACGGTCGACCATACCTTCGATTGTCGTGGCCACCCTCGGATTACACGGCAGAGGTGGTTGTGTTCCGATAGGCCAGCATATTATCCTAAGGCGTTACCCCAATCGTTTTCCGTCGGATTTGCTATAGCCCCTGAACGCTACATGCACGAAACCAAGTTATGTATGCACTGGGTCATCAATAGGACATAGCCTTGTAGTTAACATGTAGCCCGGCCGTATTAGTACAGTAGAGCCTTCACCGGCATTCTGTTTATTAAGTTATTTCTACAGCAAAACGATCATATGCAGATCCGCA”, “GTGCGCGGTAGAGACACGTCCACCCGGCTGCTCTGTAATAGGGACTAAAAAAGTGATGATTATCATGAGTGCCCCGTTATGGTCGTGTTCGATCAGAGCGCTCTTACGAGCAGTCGTATGCTTTCTCGAATTCCGTGCGGTTAAGCGTGACAGTCCCAGTGAACCCACAAAACGTGATGGCAGTCCATGCGATCATACGCAAGAAGGATGGTCTCCAGACACCGGCGCACCAGTTTTCACGCCGAAAGCATAAACGAGGAGCACAAATGAGAGTGTTTGAACTGGACCTGTAGTTTCTCTACGAAGAACACCTTGAGCTGTTGCGTTGTTGCGCTGCCTAGATGCAGTGTCGCACGTATCACTTTTGCCTCAACGACTGCTGCTTTCGCTGTAACCCTAGACAGACAACAGTAAGCGCCTTTTGTAGGCAAGAGCTCCGCCTGTGACTAACTGCGCCAAAACGTCTTCCAATCCCCTTATCCAATTTAACTCACCGAATTCTTACAATTTAGACCCTAATATCACATCATTAGACACTAATTGCCTCTGCCAAAATTCTGTCCACAAGCGTTTTAGTTCGCCCCAGTAAAGTTGTCAATAACGACCACCAAATCCGCATGTTACGGGACTTCTTATTAATTCTTTTTTCGTGGGGAGCAGCGGATCTTAATGGATGGCGCCAGGTGGTATGGAAGCTAATAGCGCGGGTGAGAGGGTAATCAGCCGTCTCCACCAACACAACGCTATCGGGTCATACTATAAGATTCCGCAATGCGACTACTTATAAGATGCCTTAACGGTATCCGCAACTTGCGATGTGCCTGCTATGCTTAAATGCATATCTCGCCCAGTAGCTTTCCAATATGAGAGCATCAATTGTAGATCGGGCCGGGATAATCATGTCGTCACGGAACTTACTGTAAGAGTAATAATTTAAAAGAGATGTCGGTTTGCTGGTTCACGTAAAGGTCCCTCGCGCTACCTCTAAGTAAGTGAGCGG”, 646);

_testFileDynStr(“text/znc1.txt”, “text/znc2.txt”, 3827);

}

} 

Solution 

package edu.wit.cs.comp2350;

import java.io.IOException;

import java.nio.file.Files;

import java.nio.file.Paths;

import java.util.Scanner;

/* Aligns strings in two text files by matching their longest common substring

*

* Wentworth Institute of Technology

* COMP 2350

* Lab Assignment 7

*

*/

public class LAB7 {

// use dynamic programming to find the best alignment of two given strings.

public static String[] findLCSdyn(String text1, String text2) {

final int len1 = text1.length();

final int len2 = text2.length();

// use an array to store the track of the dynamic programming process.

// so that track[i][j] = 0 indicates text1[i – 1] and text2[j – 1] is matched.

//                      -1 indicates add – to text1 at the position i.

//                       1 indicates add – to text2 at the position j.

final int[][] track = new int[len1 + 1][len2 + 1];

final int[][] value = new int[len1 + 1][len2 + 1]; // to save the longest match so far.

for (int i = 1; i <= len1; i++) {

for (int j = 1; j <= len2; j++) {

if (value[i – 1][j] > value[i][j – 1]) {

// add – to text2

value[i][j] = value[i – 1][j];

track[i][j] = 1;

} else {

// add – to text1

value[i][j] = value[i][j – 1];

track[i][j] = -1;

}

// find a matching pair, check if it is longer in this way.

if (text1.charAt(i – 1) == text2.charAt(j – 1)) {

if (value[i – 1][j – 1] + 1 >= value[i][j]) {

value[i][j] = value[i – 1][j – 1] + 1;

track[i][j] = 0;

}

}

}

}

longest = value[len1][len2];

// recover the two strings from the track

final StringBuilder str1 = new StringBuilder();

final StringBuilder str2 = new StringBuilder();

int i = len1, j = len2;

while (i > 0 && j > 0) {

switch (track[i][j]) {

case 0: // matched pair

str1.append(text1.charAt(i – 1));

str2.append(text2.charAt(j – 1));

i –;

j –;

break;

case -1: // added a – to text1

str1.append(‘-‘);

str2.append(text2.charAt(j – 1));

j –;

break;

case 1: // added a – to text2

str1.append(text1.charAt(i – 1));

str2.append(‘-‘);

i –;

break;

}

}

// add the heading characters matched by –

while (i > 0) {

str1.append(text1.charAt(i – 1));

str2.append(‘-‘);

i –;

}

while (j > 0) {

str1.append(‘-‘);

str2.append(text2.charAt(j – 1));

j –;

}

str1.reverse();

str2.reverse();

// return the aligned strings in an array.

return new String[] { str1.toString(),  str2.toString()};

}

/********************************************

*

* You shouldn’t modify anything past here

*

********************************************/

private static int longest = -1;

// recursive helper for DFS

private static void dfs_solve(int i1, int i2, String s1, String s2, char[] out1, char[] out2, int score, int index) {

if ((i1 >= s1.length()) && (i2 >= s2.length())) {

if (score > longest) {

out1[index] = ‘\0’;

out2[index] = ‘\0’;

longest = score;

sol1 = String.valueOf(out1).substring(0, String.valueOf(out1).indexOf(‘\0’));

sol2 = String.valueOf(out2).substring(0, String.valueOf(out2).indexOf(‘\0’));

}

}

else if ((i1 >= s1.length()) && (i2 < s2.length())) {     // at the end of first string

out1[index] = ‘-‘;

out2[index] = s2.charAt(i2);

dfs_solve(i1, i2 + 1, s1, s2, out1, out2, score, index+1);

}

else if ((i1 < s1.length()) && (i2 >= s2.length())) {     // at the end of second string

out1[index] = s1.charAt(i1);

out2[index] = ‘-‘;

dfs_solve(i1 + 1, i2, s1, s2, out1, out2, score, index+1);

}

else {

if (s1.charAt(i1) == s2.charAt(i2)) { // matching next character

out1[index] = s1.charAt(i1);

out2[index] = s2.charAt(i2);

dfs_solve(i1 + 1, i2 + 1, s1, s2, out1, out2, score + 1, index + 1);

}

out1[index] = ‘-‘;

out2[index] = s2.charAt(i2);

dfs_solve(i1, i2 + 1, s1, s2, out1, out2, score, index + 1);

out1[index] = s1.charAt(i1);

out2[index] = ‘-‘;

dfs_solve(i1 + 1, i2, s1, s2, out1, out2, score, index + 1);

}

}

// Used for DFS solution

private static String sol1, sol2;

// recursively searches for longest substring, checking all possible alignments

public static String[] findLCSdfs(String text1, String text2) {

int max_len = text1.length() + text2.length() + 1;

char[] out1 = new char[max_len];

char[] out2 = new char[max_len];

dfs_solve(0, 0, text1, text2, out1, out2, 0, 0);

String[] ret = new String[2];

ret[0] = sol1; ret[1] = sol2;

return ret;

}

// returns the length of the longest string

public static int getLongest() {

return longest;

}

public static void main(String[] args) {

Scanner s = new Scanner(System.in);

String file1, file2, text1 = “”, text2 = “”;

System.out.printf(“Enter <text1><text2><algorithm>, ([dfs] – depth first search, [dyn] – dynamic programming): “);

System.out.printf(“(e.g: text/a.txt text/b.txt dfs)\n”);

file1 = s.next();

file2 = s.next();

try {

text1 = new String(Files.readAllBytes(Paths.get(file1)));

text2 = new String(Files.readAllBytes(Paths.get(file2)));

} catch (IOException e) {

System.err.println(“Cannot open files ” + file1 + ” and ” + file2 + “. Exiting.”);

System.exit(0);

}

String algo = s.next();

String[] result = {“”};

switch (algo) {

case “dfs”:

result = findLCSdfs(text1, text2);

break;

case “dyn”:

result = findLCSdyn(text1, text2);

break;

default:

System.out.println(“Invalid algorithm”);

System.exit(0);

break;

}

s.close();

System.out.printf(“Best cost: %d\nLongest string alignment:\n%s\n\n%s\n”, longest, result[0], result[1]);

}

}