com.mhhe.clrs2e
Class LongestCommonSubsequence

java.lang.Object
  |
  +--com.mhhe.clrs2e.LongestCommonSubsequence

public class LongestCommonSubsequence

extends java.lang.Object

Implements the dynamic-programming algorithm to find a longest common subsequence of two strings, as described in Section 15.4 of Introduction to Algorithms, Second edition.

Nested Class Summary

private static class

LongestCommonSubsequence.Direction Inner class for a typesafe enum pattern for directions in a two-dimensional array.

Field Summary

private LongestCommonSubsequence.Direction[][]	b The table entry used in constructing an LCS of prefixes Xi and Yj, for 0 ≤ i ≤ m-1 and 0 ≤ j ≤ n-1.
private int[][]	c The length of an LCS of a subproblem.
private static LongestCommonSubsequence.Direction	LEFT
private int	m How many entries are in X.
private int	n How many entries are in Y.
private static LongestCommonSubsequence.Direction	UP
private static LongestCommonSubsequence.Direction	UP_AND_LEFT
private java.lang.String	x The input X.

Constructor Summary

LongestCommonSubsequence(java.lang.String x, java.lang.String y)
Computes an LCS of two strings, allocating the instance variables and storing the result in them.

Method Summary

private char	index(java.lang.String z, int k) Returns a given character from a String.
private void	lcsLength(java.lang.String x, java.lang.String y) Computes an LCS of two strings, storing the result in the instance variables.
private java.lang.String	printLCS(int i, int j) Returns an LCS of prefixes Xi and Yj.
java.lang.String	toString() Returns an LCS of X and Y as a String.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

UP

private static final LongestCommonSubsequence.Direction UP

LEFT

private static final LongestCommonSubsequence.Direction LEFT

UP_AND_LEFT

private static final LongestCommonSubsequence.Direction UP_AND_LEFT

c

private int[][] c

The length of an LCS of a subproblem. c[i][j] is the length of an LCS of prefixes X_i and Y_j, for 0 ≤ i ≤ m-1 and 0 ≤ j ≤ n-1.

b

private LongestCommonSubsequence.Direction[][] b

The table entry used in constructing an LCS of prefixes X_i and Y_j, for 0 ≤ i ≤ m-1 and 0 ≤ j ≤ n-1.

m

private final int m

How many entries are in X.

n

private final int n

How many entries are in Y.

x

private final java.lang.String x

The input X. Needed for reconstructing an optimal solution.

Constructor Detail

LongestCommonSubsequence

public LongestCommonSubsequence(java.lang.String x,
                                java.lang.String y)

Computes an LCS of two strings, allocating the instance variables and storing the result in them.

Parameters:

x - The string X.

y - The string Y.

Method Detail

lcsLength

private void lcsLength(java.lang.String x,
                       java.lang.String y)

Computes an LCS of two strings, storing the result in the instance variables. The instance variables are assumed to be already allocated. Implements the LCS-Length procedure on page 353.

Parameters:

x - The string X.

y - The string Y.

index

private char index(java.lang.String z,
                   int k)

Returns a given character from a String. Compensates for character positions in a String being indexed from 0, rather than from 1 as in Section 15.4.

Parameters:

z - A String.

k - An index into z, but starting from 1.

Returns:

Returns the kth character of z.

printLCS

private java.lang.String printLCS(int i,
                                  int j)

Returns an LCS of prefixes X_i and Y_j. Implements the Print-LCS procedure on page 355.

Parameters:

i - Index into X.

j - Index into Y.

Returns:

A String that is an LCS of X_i and Y_j.

toString

public java.lang.String toString()

Returns an LCS of X and Y as a String.

Overrides:

toString in class java.lang.Object