print lcs
1234567891011121314151617181920212223242526272829303132333435363738394041424344
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String s1=sc.next();
String s2=sc.next();
System.out.print(lcs(s1,s2));
}
public static String lcs(String s1,String s2){
int m=s1.length();
int n=s2.length();
int t[][]=new int[m+1][n+1];
for(int i=1;i<m+1;i++){
for(int j=1;j<n+1;j++){
if(s1.charAt(i-1)==s2.charAt(j-1)){
t[i][j]=1+t[i-1][j-1];
}
else{
t[i][j]=Math.max(t[i-1][j],t[i][j-1]);
}
}
}
StringBuilder sb=new StringBuilder();
int i=m;
int j=n;
while(i>0&&j>0){
if(s1.charAt(i-1)==s2.charAt(j-1)){
sb.append(s1.charAt(i-1));
i--;
j--;
}
else{
if(t[i-1][j]>t[i][j-1]){
i--;
}
else{
j--;
}
}
}
return sb.reverse().toString();
}
}
Java
INFO