class for reference: https://www.cs.colorado.edu/~main/edu/colorado/nodes/CharNode.java

Task 4: Write a method called subSequence that given two linked lists of characters determines whether the shorter list (let us call it S) is a subsequence of the longer list (let us call it L). If the shorter list is a subsequence of the longer list, then the method should return the length of the shortest segment in L that contains S as a subsequence. For example, for sequences CAT and ACAGTGCGTATAT from the example below, the method should return 4.

If the shorter list is not a subsequence of the longer list, then the method should return value -1.

The method should have two parameters (of type CharNode) heads of the two linked lists. It is not known in advance which of the parameters (the first one or the second one) contains a shorter list. The length of the lists must be checked first to determine which of the two given lists is shorter. (Note: The goal of this task is to practice working with linked lists. Converting lists into strings and using String methods is not permitted.) In your program you should prompt the user to enter two strings, convert the strings into linked lists using the method which you wrote before (to convert a String into a linked list of characters),

call the method to determine whether a shorter list is a subsequence of a longer list and output the result.

Example:

Sequence similarity

Determining the similarity between two sequences is a common task in computational biology. Identifying similarities is important, as it is assumed that similar structure leads to similar biological functions.

A subsequence of a sequence is a list of characters from the sequence in the same order that they appear in that sequence. For example, sequence TTC is a subsequence of GATGTAACCTA since characters T, T, and C are the 3rd, the 5th, and the 8th characters in GATGTAACCTA. On the other hand, ACCG is not a subsequence of GATGTAACCTA since characters A, C, C, G appear in a different order in GATGTAACCTA (there is no G after C in the longer sequence).

When a sequence X is a subsequence of another sequence Y, then it can be a subsequence of different segments in Y. For example, let X be CAT and let Y be ACAGTGCGTATAT. Then, X appears as a subsequence of Y in many ways, including the following:

ACAGTGCGTATAT a subsequence of the segment CAGT of length 4 (2nd through 5th characters of Y),

ACAGTGCGTATAT a subsequence of the segment CGTATAT of length 7 (7th through 13th characters of Y),

ACAGTGCGTATAT a subsequence of the segment CGTAT of length 5 (7th through 11th characters of Y),

ACAGTGCGTATAT a subsequence of the segment CAGTGCGTAT of length 10 (2nd through 11th characters of Y), and so on.