Java program to find longest common subsequence.
text1 = "abaabbaaa"; text2 = "babab"; OUT: Length = 4 Lcs = baba
// ? 2019 TheFlyingKeyboard and released under MIT License // theflyingkeyboard.net public class Main { public static void main(String[] args) { final String text1 = "abaabbaaa"; final String text2 = "babab"; int[][] lengths = new int[text1.length() + 1][text2.length() + 1]; for(int i = 1; i < text1.length() + 1; ++i){ for(int j = 1; j < text2.length() + 1; ++j){ if(text1.charAt(i - 1) == text2.charAt(j - 1)){ lengths[i][j] = lengths[i - 1][j - 1] + 1; }else{ lengths[i][j] = max(lengths[i - 1][j], lengths[i][j - 1]); } } } System.out.println("Length = " + lengths[lengths.length - 1][lengths[0].length - 1]); int i = lengths.length - 1; int j = lengths[0].length - 1; String lcs = ""; while (i > 0 && j > 0){ if(text1.charAt(i - 1) == text2.charAt(j - 1)){ lcs = text1.charAt(i - 1) + lcs; --i; --j; }else if(lengths[i - 1][j] > lengths[i][j - 1]){ i--; }else{ j--; } } System.out.println("Lcs = " + lcs); } private static int max(int a, int b){ return a > b ? a : b; } }