51 lines
1.3 KiB
Java
51 lines
1.3 KiB
Java
import java.util.*;
|
|
|
|
public class _9252 {
|
|
public static void main(String[] args) {
|
|
Scanner sc = new Scanner(System.in);
|
|
String a = sc.nextLine();
|
|
String b = sc.nextLine();
|
|
sc.close();
|
|
|
|
int la = a.length(), lb = b.length();
|
|
|
|
int[][] dp = new int[la+1][lb+1];
|
|
|
|
for(int i=1; i<=la; i++) {
|
|
for(int j=1; j<=lb; j++) {
|
|
if(a.charAt(i-1) == b.charAt(j-1)) {
|
|
dp[i][j] = Math.max(dp[i-1][j-1] + 1, dp[i][j]);
|
|
}
|
|
else {
|
|
dp[i][j] = Math.max(dp[i][j], Math.max(dp[i-1][j], dp[i][j-1]));
|
|
}
|
|
}
|
|
}
|
|
|
|
System.out.println(dp[la][lb]);
|
|
|
|
if(dp[la][lb] != 0) {
|
|
int pa = la, pb = lb;
|
|
String reverse = "";
|
|
|
|
while(pa != 0 && pb != 0) {
|
|
if(dp[pa-1][pb] == dp[pa][pb]) {
|
|
pa--;
|
|
}
|
|
else if (dp[pa][pb-1] == dp[pa][pb]){
|
|
pb--;
|
|
}
|
|
else {
|
|
reverse += a.charAt(pa-1);
|
|
pa--; pb--;
|
|
}
|
|
}
|
|
|
|
String res = "";
|
|
for(int i=dp[la][lb]-1; i >= 0 ; i--) res += reverse.charAt(i);
|
|
|
|
System.out.println(res);
|
|
}
|
|
}
|
|
}
|