48 lines
954 B
C
48 lines
954 B
C
#include <stdio.h>
|
|
#include <string.h>
|
|
|
|
char s1[1001], s2[1001];
|
|
char res[1001];
|
|
int dp[1001][1001];
|
|
|
|
int max(int a, int b) {
|
|
return a > b ? a : b;
|
|
}
|
|
|
|
int main() {
|
|
scanf("%s", s1);
|
|
scanf("%s", s2);
|
|
int l1 = strlen(s1), l2 = strlen(s2);
|
|
|
|
for(int i=1; i<=l1; i++) {
|
|
char c1 = s1[i-1];
|
|
|
|
for(int j=1; j<=l2; j++) {
|
|
char c2 = s2[j-1];
|
|
|
|
if(c1 == c2) dp[i][j] = dp[i-1][j-1] + 1;
|
|
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
|
|
}
|
|
}
|
|
|
|
printf("%d\n",dp[l1][l2]);
|
|
|
|
if(dp[l1][l2] != 0) {
|
|
int res_len = dp[l1][l2];
|
|
|
|
int p1 = l1, p2 = l2;
|
|
|
|
while(p1 > 0 && p2 > 0) {
|
|
if(dp[p1][p2] == dp[p1-1][p2]) p1--;
|
|
else if(dp[p1][p2] == dp[p1][p2-1]) p2--;
|
|
else {
|
|
res[--res_len] = s1[p1-1];
|
|
p1--; p2--;
|
|
}
|
|
}
|
|
|
|
printf("%s\n", res);
|
|
}
|
|
|
|
return 0;
|
|
} |