Longest Common subsequence – DP 4

package algorithm.weixin;

/**
* ABCDGH and AEDFHR is ADH length 3
* AGGTAB and GXTXAYB is GTAB of length 4
*
*
* @author xwei
*
*/

public class LongestCommonSubsequence {

    /**
     * assume you have 2 sequences Xi and Yj, let's define
     * c[i][j] to be the length of LCS sequence Xi and Yj
     * then you could get formular
     *           |---0   if i = 0 or j = 0
     *           |
     * c[i][j] = |---c[i-1][j-1] + 1 if xi = yj, i, j > 0
     *           |
     *           |---max{c[i-1][j], c[i][j-1]}
     *
     * @param args
     */
    public static int findLCS( String seq1, String seq2 )
    {
        int[][] LCS = new int[seq1.length()+1][seq2.length()+1];
        int i, j;
        // base case
        for( i = 0; i < seq1.length(); i++ )
        {
            LCS[i][0] = 0;
        }
        for( j = 0; j < seq2.length(); j++ )
        {
            LCS[0][j] = 0;
        }
        for( i = 1; i < seq1.length()+1; i++ )
        {
            for( j = 1; j < seq2.length()+1; j++ )
            {
                // need to be careful about the index
                // LCS[1][1] would use seq1[0] and seq2[0] to get
                if( seq1.charAt( i-1 ) == seq2.charAt( j-1 ) )
                {
                    LCS[i][j] = 1 + LCS[i-1][j-1];
                }
                else
                {
                    LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]);
                }
            }
        }
        return LCS[seq1.length()][seq2.length()];
    }
    public static void main(String[] args) {
        String seq1 = "ABCDGH";
        String seq2 = "AEDFHR";
        int result = findLCS( seq1, seq2 );
        System.out.println( result );
        String seq3 = "AGGTAB";
        String seq4 = "GXTXAYB";
        int result2 = findLCS( seq3, seq4 );
        System.out.println( result2 );
    }

}

Advertisements
This entry was posted in programming and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s