Jacob_Thomas

LCS

Jan 28th, 2021
597
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2. class LCS{
  3.     public static void main(String[] args){
  4.         Scanner sc = new Scanner(System.in);
  5.         System.out.println("Enter the first string");
  6.         String a = sc.nextLine();
  7.         System.out.println("Enter the second string");
  8.         String b = sc.nextLine();
  9.         int arr[][] = new int[a.length()+1][b.length()+1];
  10.         for(int x = 0; x <= a.length(); x++)
  11.             arr[x][0]=0;
  12.         for(int x = 0; x <= b.length(); x++)
  13.             arr[0][x]=0;
  14.         for(int x = 1; x <= a.length(); x++){
  15.             for(int y = 1; y <= b.length(); y++){
  16.                 if(a.charAt(x-1) == (b.charAt(y-1)))
  17.                     arr[x][y] = arr[x-1][y-1] + 1;
  18.                 else
  19.                     arr[x][y] = Math.max(arr[x-1][y], arr[x][y-1]);
  20.             }
  21.         }
  22.         System.out.println(arr[a.length()][b.length()]);
  23.         int x = a.length();
  24.         int y = b.length();
  25.         int index = arr[x][y];
  26.         int temp = index;
  27.         char lcs[] = new char[arr[x][y]];
  28.         int i = x;
  29.         int j = y;
  30.        
  31.         while(i>0 && j >0){
  32.             if(a.charAt(i-1) == b.charAt(j-1)){
  33.                 lcs[index-1] = a.charAt(i-1);
  34.                 i--;
  35.                 j--;
  36.                 index--;
  37.             }
  38.             else if(arr[i-1][j] > arr[i][j-1]){
  39.                 i--;
  40.             }
  41.             else{
  42.                 j--;
  43.             }
  44.         }
  45.        
  46.         System.out.println(Arrays.toString(lcs));
  47.        
  48.        
  49.     }
  50. }
RAW Paste Data