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); } }