LCS problem
public class LCS
{
public static String lcs(String a, String b )
{
String lcs = lcs(a, b, "", 0, 0);
return lcs;
}
private static String lcs(String a, String b, String lcs, int i , int j)
{
int length_a = a.length();
int length_b = b.length();
if (i == length_a || j == length_b) return lcs;
if (a.charAt(i) == b.charAt(j))
{
lcs += a.charAt(i);
i++;
j++;
}
else
{
String lcs_i_plus = lcs(a, b, lcs ,i+1, j);
String lcs_j_plus = lcs(a, b , lcs ,i, j+1);
if ( lcs_i_plus.length() > lcs_j_plus.length())
i++;
else
j++;
}
return lcs(a, b, lcs , i, j) ;
}
public static void main(String[] args)
{
//client
String a = "GGCACCACG";
String b = "ACGGCGGATACG";
String lcs = lcs(a, b);
StdOut.println(lcs);
}
}
评论