LongestCommonSubsequence.java

packagecom.jwetherell.algorithms.sequence;

importjava.util.HashSet;
importjava.util.Set;

/**
 * The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from problems 
 * of finding common substrings: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. 
 * <p>
 * @see <a href="https://en.wikipedia.org/wiki/Longest_common_subsequence_problem">Longest Common Subsequence Problem (Wikipedia)</a>
 * <br>
 * @author Justin Wetherell <phishman3579@gmail.com>
 */
@SuppressWarnings("unchecked")
publicclassLongestCommonSubsequence {

privatestaticint[][] lengthMatrix = null;
privatestaticSet<String>[][] sequenceMatrix = null;

privateLongestCommonSubsequence() { }

publicstaticMatrixPairgetLCS(char[] seq1, char[] seq2) {
try {
populateMatrix(seq1, seq2);

for (inti = 0; i < seq1.length; i++) {
for (intj = 0; j < seq2.length; j++) {
lengthMatrix[i + 1][j + 1] = longestCommonSubsequence(i, j, seq1, seq2);
 }
 }

return (newMatrixPair(lengthMatrix, sequenceMatrix));
 } finally {
lengthMatrix = null;
sequenceMatrix = null;
 }
 }

privatestaticvoidpopulateMatrix(char[] seq1, char[] seq2) {
lengthMatrix = newint[seq1.length + 1][seq2.length + 1];
sequenceMatrix = newHashSet[seq1.length][seq2.length];
 }

privatestaticintlongestCommonSubsequence(inti, intj, char[] seq1, char[] seq2) {
charx = seq1[i];
chary = seq2[j];
intresult = 0;
Set<String> set = sequenceMatrix[i][j];
if (set == null)
set = newHashSet<String>();
if (x == y) {
if (i > 0 && j > 0)
set = newHashSet<String>(sequenceMatrix[i - 1][j - 1]);
distribute(x, set);

result = (lengthMatrix[i][j]) + 1;
 } else {
inta = lengthMatrix[i][j + 1];
intb = lengthMatrix[i + 1][j];

if (a > b) {
set = newHashSet<String>(sequenceMatrix[i - 1][j]);

result = a;
 } elseif (b > a) {
set = newHashSet<String>(sequenceMatrix[i][j - 1]);

result = b;
 } elseif (a == b) {
if (i > 0 && j > 0) {
Set<String> list1 = sequenceMatrix[i - 1][j];
Set<String> list2 = sequenceMatrix[i][j - 1];

set.addAll(list1);
set.addAll(list2);
 }

result = a; // a==b
 }
 }
sequenceMatrix[i][j] = set;
returnresult;
 }

privatestaticvoiddistribute(charc, Set<String> set) {
if (set.size() == 0) {
set.add(String.valueOf(c));
 } else {
Object[] strings = set.toArray();
set.clear();
for (Objectobject : strings) {
Stringstring = (String) object;
Stringseq = String.valueOf(c);
if (!string.contains(seq))
string = string.concat(seq);
set.add(string);
 }
 }
 }

publicstaticclassMatrixPair {

privateint[][] lenMatrix = null;
privateSet<String>[][] seqMatrix = null;

publicMatrixPair(int[][] lengthMatrix, Set<String>[][] sequenceMatrix) {
this.lenMatrix = lengthMatrix;
this.seqMatrix = sequenceMatrix;
 }

publicintgetLongestSequenceLength() {
if (lenMatrix == null)
return0;

intlength1 = lenMatrix.length;
intlength2 = lenMatrix[length1 - 1].length;
returnlenMatrix[length1 - 1][length2 - 1];
 }

publicSet<String> getLongestSequences() {
if (seqMatrix == null)
return (newHashSet<String>());

intlength1 = seqMatrix.length;
intlength2 = seqMatrix[length1 - 1].length;
returnseqMatrix[length1 - 1][length2 - 1];
 }

publicint[][] getLengthMatrix() {
returnlenMatrix;
 }

publicSet<String>[][] getSequenceMatrix() {
returnseqMatrix;
 }

publicStringgetLengthMatrixString() {
StringBuilderbuilder = newStringBuilder();
if (lenMatrix == null) {
builder.append("Length matrix is NULL.\n");
 } else {
for (inti = 0; i < lenMatrix.length; i++) {
intlength = lenMatrix[i].length;
for (intj = 0; j < length; j++) {
intsize = lenMatrix[i][j];
builder.append(size);
if (j < length - 1)
builder.append(",\t");
 }
builder.append("\n");
 }
 }
returnbuilder.toString();
 }

publicStringgetSequenceMatrixString() {
StringBuilderbuilder = newStringBuilder();
if (seqMatrix == null) {
builder.append("Sequence matrix is NULL.\n");
 } else {
for (inti = 0; i < seqMatrix.length; i++) {
intlength = seqMatrix[i].length;
for (intj = 0; j < length; j++) {
Set<String> set = seqMatrix[i][j];
builder.append(set.toString());
if (j < length - 1)
builder.append(", ");
 }
builder.append("\n");
 }
 }
returnbuilder.toString();
 }
 }
}