## 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;        }        for( j = 0; j < seq2.length(); j++ )        {            LCS[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 would use seq1 and seq2 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 );    }
}
```
This entry was posted in programming and tagged . Bookmark the permalink.