Longest Common Subsequence

QUESTION

We are given two sequences and we have to find the longest subsequence present in both of them. The subsequence must appear in the same order in both the sequences and need not be continuous.\n\nFor example:\n\nS1 = \”AABCEGACA\” \nS2 = \”ABCFGCBAHKA\”\n\nLength of the Longest Common Subsequence of S1 and S2 is 6. \n\”ABCGCA\” is the LCS of S1 and S2.\n\nLCS isn’t necessarily unique, there can be more than one common subsequence with the maximum length.\n\nFor example:\n\nS1 = \”AABBCC\” S2 = \”ABCAB\”\n\nThe length of the LCS is 3.\n\nThe LCS can be \”ABC\”, \”AAB\” or \”ABB\”.

ANSWER

import java.io.*;
import java.util.*;
public class TestClass {
    static void lcs(String X, String Y, int m, int n)
    {
        int[][] L = new int[m+1][n+1];      
        for (int i=0; i<=m; i++)
        {
            for (int j=0; j<=n; j++)
            {
                if (i == 0 || j == 0)
                    L[i][j] = 0;
                else if (X.charAt(i-1) == Y.charAt(j-1))
                    L[i][j] = L[i-1][j-1] + 1;
                else
                    L[i][j] = Math.max(L[i-1][j], L[i][j-1]);
            }
        }
        int index = L[m][n];
        int temp = index; 
        char[] lcs = new char[index+1];
        lcs[index] = '\0'; 
  
        int i = m, j = n;
        while (i > 0 && j > 0)
        {

            if (X.charAt(i-1) == Y.charAt(j-1))
            {              
                lcs[index-1] = X.charAt(i-1); 
                i--; 
                j--; 
                index--;     
            }         
            else if (L[i-1][j] > L[i][j-1])
                i--;
            else
                j--;
        }
        
        System.out.print("The Longest Common Subsequence is ");
        for(int k=0;k<=temp;k++)
            System.out.print(lcs[k]);
    }
     
	 public static void main(String[] args) { 
       Scanner scan = new Scanner(System.in);
		String X;
        String Y;
        Y= scan.nextLine();
        X = scan.nextLine();
        int m = X.length();
        int n = Y.length();
        lcs(X, Y, m, n);
	}
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.