LCS

import java.util.*;
class LCS{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the first string");
        String a = sc.nextLine();
        System.out.println("Enter the second string");
        String b = sc.nextLine();
        int arr[][] = new int[a.length()+1][b.length()+1];
        for(int x = 0; x <= a.length(); x++)
            arr[x][0]=0;
        for(int x = 0; x <= b.length(); x++)
            arr[0][x]=0;
        for(int x = 1; x <= a.length(); x++){
            for(int y = 1; y <= b.length(); y++){
                if(a.charAt(x-1) == (b.charAt(y-1)))
                    arr[x][y] = arr[x-1][y-1] + 1;
                else
                    arr[x][y] = Math.max(arr[x-1][y], arr[x][y-1]);
            }
        }
        System.out.println(arr[a.length()][b.length()]);
        int x = a.length();
        int y = b.length();
        int index = arr[x][y];
        int temp = index;
        char lcs[] = new char[arr[x][y]];
        int i = x;
        int j = y;

        while(i>0 && j >0){
            if(a.charAt(i-1) == b.charAt(j-1)){
                lcs[index-1] = a.charAt(i-1);
                i--;
                j--;
                index--;
            }
            else if(arr[i-1][j] > arr[i][j-1]){
                i--;
            }
            else{
                j--;
            }
        }

        System.out.println(Arrays.toString(lcs));


    }
}