Untitled

mail@pastecode.io avatar
unknown
plain_text
4 years ago
1.1 kB
4
Indexable
Never
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
char x[1002], y[1002];
int LCS[1002][1002];
int prev[1002][1002][2];
int n, m;
void calc() {
	for (int i = 1; i < m; ++i)
		for (int j = 1; j < n; ++j) {
			if (x[i] == y[j])
				LCS[i][j] = LCS[i - 1][j - 1] + 1,
				prev[i][j][0] = i - 1, prev[i][j][1] = j - 1;
			else if (LCS[i - 1][j] >= LCS[i][j - 1])
				LCS[i][j] = LCS[i - 1][j],
				prev[i][j][0] = i - 1, prev[i][j][1] = j;
			else
				LCS[i][j] = LCS[i][j - 1],
				prev[i][j][0] = i, prev[i][j][1] = j - 1;
		}
}

char em = 1;
void print(int i, int j) {
	if (!i || !j)
		return;
	if (prev[i][j][0] == i - 1 && prev[i][j][1] == j - 1)
		print(i - 1, j - 1), printf("%c", x[i]), em = 0;
	else if (prev[i][j][0] == i - 1 && prev[i][j][1] == j)
		print(i - 1, j);
	else
		print(i, j - 1);
}
signed main() {
	scanf("%s%s", (char*)&x[1], (char*)&y[1]);
	m = strlen((char*)&x[1]) + 1;
	n = strlen((char*)&y[1]) + 1;
	calc();
	print(m, n);
	if (LCS[m][n] == 0)
		printf("Empty");
}