Directions:

Step 1. Look at the skeleton in LongestCommonSubsequence.java. Compile and run the main method. Checkpoint: If all has gone well, the program will run and accept input. It will report that the strings to check is null and give the empty string as the longest common subsequence. The goal now is to create the bag of strings to check.

Step 2. In main create a new bag and assign it to toCheckContainer. Add in the string first.

Step 3. Print out the bag toCheckContainer. Checkpoint: Compile and run the program. Enter ABD and BCD for the two strings. You should see Bag [ ABD ] The next goal is to do take a string from the bag and see if it is a subsequence of the input string second. This check will be encapsulated in the method isSubsequence().

Step 4. Refer to the pre-lab exercises and complete the method isSubsequence().

Step 5. Remove an item from toCheckContainer and store it in an String variable.

Step 6. Call the method isSubsequence() with the string you just removed from the bag and the second input string. If the method returned true, report that it was a subsequence

step 7: The following is the algorithm we saw in the pre-lab for computing the longest common subsequence. We have already completed parts of it, but now you should finish everything but the while loop.

1. Put the first string into the bag 2. Set the longest match to the empty string 3. While the bag is not empty 3.1 Remove a test string from the bag 3.2 If the longest match is shorter than the test string 3.2.1 If the test string is a subsequence of the second string 3.2.1.1 Set the longest match to the test string 3.2.2 Otherwise if the test string is at least two longer than the longest match 3.2.2.1 Generate new strings and put them into the bag 3.3 Print the bag of strings to check 4. Report the longest match The only tricky part of this is the generation step 3.2.2.1. You will need to create a for loop that loops over the positions of characters in the test string and creates the smaller test string as discussed in the pre-lab exercises. Checkpoint: Compile and run the program. Enter ABCD and FAC for the two input strings. The code should report that the new bag is Bag[ BCD ACD ABD ABC ] and the longest subsequence should remain empty. Run the code again and enter BA and ABCA for the two input strings. The code should report that the new bag is Bag[ ] and the longest subsequence is BA. Run the code again and enter ABA and ABCB for the two input strings. The code should report that the new bag is Bag[ BA AA AB ] and the longest subsequence should remain empty Run the code again and enter D and ABCA for the two input strings. The code should report that the new bag is Bag[ ] and the longest subsequence should remain empty For our final goal, we will add in the code that loops over the items in the bag

Step 8. Wrap the code from steps 3.1 to 3.3 in the algorithm in a while loop that continues as long as the toCheckContainer bag is not empty. Final checkpoint: Compile and run the program. Enter ABCD and FAC for input strings. Compare the results with the pre-lab exercises. Reconcile any differences.

LongestCommonSubsequnce:

import java.io.*;

import java.util.*;

/**

* LongestCommonSubsequence is a program that will determine the longest string that is

* a subsequence of two input strings. This program applies a brute force solution technique.

*

* @author Charles Hoot

* @version 4.0

*/

public class LongestCommonSubsequence {

public static void main(String args[]) {

BagInterface toCheckContainer = null;

Scanner input;

input = new Scanner(System.in);

System.out.println("This program determines the longest string that is a subsequence of two input string.");

System.out.println("Please enter the first string:");

String first = input.next();

System.out.println("Please enter the second string:");

String second = input.next();

// ADD CODE HERE TO CREATE THE BAG WITH THE INITIAL STRING

System.out.println("The strings to check are: " + toCheckContainer);

String bestSubsequence = new String("");

// ADD CODE HERE TO CHECK THE STRINGS IN THE BAG

System.out.println("Found " + bestSubsequence + " for the longest common subsequence");

}

/**

* Determine if one string is a subsequence of the other.

*

* @param check See if this is a subsequence of the other argument.

* @param other The string to check against.

* @return A boolean if check is a subsequence of other.

*/

public static boolean isSubsequence(String check, String against) {

boolean result = false;

// ADD CODE HERE TO CHECK IF WE HAVE A SUBSEQUENCE

return result;

}

}

BagInterface:

/**

An interface that describes the operations of a bag of objects.

@author Frank M. Carrano

* This code is from Chapter 1 of

* Data Structures and Abstractions with Java 3/e

* by Carrano

*/

public interface BagInterface {

/** Gets the current number of entries in this bag.

@return The integer number of entries currently in the bag. */

publicintgetCurrentSize();

/** Sees whether this bag is empty.

@return True if the bag is empty, or false if not. */

public boolean isEmpty();

/** Adds a new entry to this bag.

@param newEntry The object to be added as a new entry.

@return True if the addition is successful, or false if not. */

public boolean add(T newEntry);

/** Removes one unspecified entry from this bag, if possible.

@return Either the removed entry, if the removal

was successful, or null. */

public T remove();

/** Removes one occurrence of a given entry from this bag,

if possible.

@param anEntry The entry to be removed.

@return True if the removal was successful, or false if not */

public boolean remove(T anEntry);

/** Removes all entries from this bag. */

public void clear();

/** Counts the number of times a given entry appears in this bag.

@param anEntry The entry to be counted.

@return The number of times anEntry appears in the bag. */

publicintgetFrequencyOf(T anEntry);

/** Tests whether this bag contains a given entry.

@param anEntry The entry to locate.

@return True if the bag contains anEntry, or false if not. */

public boolean contains(T anEntry);

/** Retrieves all entries that are in this bag.

@return A newly allocated array of all the entries in the bag.

Note: If the bag is empty, the returned array is empty. */

public T[] toArray();

} // end BagInterface