problem solve using java

Longest common sub sequence

Description


Write a program to find the longest common subsequence of two strings. The common subsequence need not be contiguous. The two stings are given in one line in a file. Ignore empty lines.

Input sample

Two strings per line in following format. Assume there is only one unique subsequence per test case.
YAHOOMAIL;FACEBOOK

Output sample

The longest common subsequence.
AOO

Test cases

Input                                                                  Output

HBLMQSRATNVA;HXMHRIOTLA               HMRTA

PQABHCDES;AMPCBEDS                             ACES

AHPICDONIYMN;EHRSCTNJN                    HCNN



ANSWER





import java.util.Scanner;



public class QQ2{
 
 
    public static void main(String[]args){
         Scanner sc=new Scanner(System.in);
        String input=sc.nextLine();
     
        String spl[]=input.split(";");
     
        String str1;
        String str2;
        if(spl[0].length()>spl[1].length()){
        str1=spl[1];
        str2=spl[0];
    }
        else{
            str1=spl[0];
        str2=spl[1];
        }
     
     
     String out=lcs(str1,str2);
        System.out.print(out);
    }
 
 public static String lcs(String a, String b){
    int aLen = a.length();
    int bLen = b.length();
    if(aLen == 0 || bLen == 0){
        return "";
    }else if(a.charAt(aLen-1) == b.charAt(bLen-1)){
        return lcs(a.substring(0,aLen-1),b.substring(0,bLen-1))
            + a.charAt(aLen-1);
    }else{
        String x = lcs(a, b.substring(0,bLen-1));
        String y = lcs(a.substring(0,aLen-1), b);
        return (x.length() > y.length()) ? x : y;
    }
}
}