Educational DP Contest - LCS

You are given strings s and t. Find one longest string that is a subsequence of both s and t.

Constraints

* s and t are strings consisting of lowercase English letters.
* 1 \leq |s|, |t| \leq 3000

Input

Input is given from Standard Input in the following format:


s
t


Output

Print one longest string that is a subsequence of both s and t. If there are multiple such strings, any of them will be accepted.

Examples

Input

axyb
abyxb


Output

axb


Input

aa
xayaz


Output

aa


Input

a
z


Output




Input

abracadabra
avadakedavra


Output

aaadara

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
s1 = input()
s2 = input()
dp = [0] * (len(s1) + 1)
dp[0] = [0] * (len(s2) + 1)
for i in range(1, len(s1) + 1):
	dp[i] = [0] * (len(s2) + 1)
	for j in range(1, len(s2) + 1):
		if s1[i - 1] == s2[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
s = ''
(i, j) = (len(s1), len(s2))
while i > 0 and j > 0:
	if s1[i - 1] == s2[j - 1]:
		s += s1[i - 1]
		i -= 1
		j -= 1
	elif dp[i][j - 1] > dp[i - 1][j]:
		j -= 1
	else:
		i -= 1
print(s[::-1])


s = input()
t = input()
(S, T) = (len(s), len(t))
dp = [[0] * (T + 1) for _ in range(S + 1)]
for i in range(S):
	for j in range(T):
		if s[i] == t[j]:
			dp[i + 1][j + 1] = dp[i][j] + 1
		else:
			dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
l = dp[S][T]
(x, y) = (S, T)
ans = [0] * l
while l > 0:
	if s[x - 1] == t[y - 1]:
		ans[l - 1] = s[x - 1]
		l -= 1
		x -= 1
		y -= 1
	elif dp[x][y] == dp[x - 1][y]:
		x -= 1
	else:
		y -= 1
print(''.join(ans))


(s, t) = (input(), input())
(n, m) = (len(s), len(t))
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
	for j in range(n):
		if t[i] == s[j]:
			dp[i + 1][j + 1] = max(dp[i][j] + 1, dp[i + 1][j + 1])
		dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1])
ans = ''
cnt = 0
(i, j) = (m, n)
while cnt != dp[-1][-1]:
	if dp[i][j] == dp[i][j - 1]:
		j -= 1
	elif dp[i][j] == dp[i - 1][j]:
		i -= 1
	else:
		ans += s[j - 1]
		cnt += 1
		(i, j) = (i - 1, j - 1)
print(ans[::-1])


(s, t) = (input(), input())
dp = [[0] * (len(t) + 1) for i in range(len(s) + 1)]
for i in range(len(s)):
	for j in range(len(t)):
		if s[i] == t[j]:
			dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1, dp[i][j + 1], dp[i + 1][j])
		dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1])
ans_str = ''
i = len(s)
j = len(t)
while i > 0 and j > 0:
	if dp[i][j] == dp[i - 1][j]:
		i = i - 1
	elif dp[i][j] == dp[i][j - 1]:
		j = j - 1
	else:
		ans_str = s[i - 1] + ans_str
		i = i - 1
		j = j - 1
print(ans_str)


s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0 for a in range(3300)] for b in range(3300)]
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if s[i - 1] == t[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		dp[i][j] = max(dp[i][j], dp[i - 1][j], dp[i][j - 1])
rewsna = ''
while n >= 0 and m >= 0:
	if dp[n][m] == dp[n - 1][m]:
		n -= 1
	elif dp[n][m] == dp[n][m - 1]:
		m -= 1
	else:
		rewsna += s[n - 1]
		n -= 1
		m -= 1
print(rewsna[::-1])


s = input()
t = input()
ls = len(s)
lt = len(t)
ans = ''
dp = [[0] * (lt + 1) for i in range(ls + 1)]
for i in range(1, ls + 1):
	for j in range(1, lt + 1):
		if s[i - 1] == t[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
x = lt
y = ls
while x - 1 >= 0 and y - 1 >= 0:
	if dp[y][x] == dp[y][x - 1]:
		x -= 1
	elif dp[y][x] == dp[y - 1][x]:
		y -= 1
	else:
		ans = s[y - 1] + ans
		x -= 1
		y -= 1
print(ans)


s = input()
t = input()
S = len(s)
T = len(t)
dp = [[0 for j in range(T + 1)] for i in range(S + 1)]
for i in range(S):
	for j in range(T):
		if s[i] == t[j]:
			dp[i + 1][j + 1] = dp[i][j] + 1
		else:
			dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
a = ''
i += 1
j += 1
while i > 0 and j > 0:
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	else:
		i -= 1
		j -= 1
		a = s[i] + a
print(a)


a = input()
b = input()
dp = [[0] * (len(b) + 1) for i in range(len(a) + 1)]
for i in range(1, len(a) + 1):
	for j in range(1, len(b) + 1):
		if a[i - 1] == b[j - 1]:
			dp[i][j] = 1 + dp[i - 1][j - 1]
		else:
			dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
ans = []
p = len(a)
t = len(b)
while p > 0 and t > 0:
	if a[p - 1] == b[t - 1]:
		ans.insert(0, a[p - 1])
		p = p - 1
		t = t - 1
	elif dp[p][t - 1] > dp[p - 1][t]:
		t = t - 1
	else:
		p = p - 1
print('%s' % ''.join(ans))


S = input()
T = input()
(s, t) = (len(S), len(T))
dp = [[0] * (t + 1) for _ in range(s + 1)]
for i in range(1, s + 1):
	for j in range(1, t + 1):
		if S[i - 1] == T[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
ans = ''
(n, m) = (s, t)
while n > 0 and m > 0:
	if dp[n][m] == dp[n - 1][m]:
		n -= 1
	elif dp[n][m] == dp[n][m - 1]:
		m -= 1
	else:
		ans = S[n - 1] + ans
		n -= 1
		m -= 1
print(ans)


s = input()
t = input()
lenS = len(s)
lenT = len(t)
dp = []
for i in range(lenS + 1):
	dp.append([0] * (lenT + 1))
for i in range(1, lenS + 1):
	for j in range(1, lenT + 1):
		if s[i - 1] == t[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
ans = ''
i = lenS
j = lenT
while i > 0 and j > 0:
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	else:
		ans += s[i - 1]
		i -= 1
		j -= 1
print(ans[::-1])


s = input()
t = input()
ls = len(s)
lt = len(t)
INF = float('inf')
dp = [[0 for i in range(lt + 1)] for j in range(ls + 1)]
R = [[INF for i in range(lt + 1)] for j in range(ls + 1)]
for i in range(1, ls + 1):
	for j in range(1, lt + 1):
		if s[i - 1] == t[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
l = dp[ls][lt]
ans = ''
i = ls
j = lt
while l > 0:
	if s[i - 1] == t[j - 1]:
		ans = str(s[i - 1]) + ans
		l -= 1
		i -= 1
		j -= 1
	elif dp[i][j] == dp[i - 1][j]:
		i -= 1
	else:
		j -= 1
print(ans)


s = input()
t = input()
DP = [[0 for i in range(len(s) + 1)] for i in range(len(t) + 1)]
ans = ''
for i in range(len(t)):
	for j in range(len(s)):
		if t[i] == s[j]:
			DP[i + 1][j + 1] = DP[i][j] + 1
		else:
			DP[i + 1][j + 1] = max(DP[i][j + 1], DP[i + 1][j])
i = len(t)
j = len(s)
ans = ''
while i >= 0 and j >= 0:
	if DP[i][j] == DP[i - 1][j]:
		i -= 1
	elif DP[i][j] == DP[i][j - 1]:
		j -= 1
	else:
		i -= 1
		j -= 1
		ans = ans + t[i]
ans = ans[::-1]
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
tdlist = lambda i, j, value=0: [[value] * j for _ in range(i)]
s = input()
t = input()
(n, m) = (len(s), len(t))
dp = tdlist(n + 5, m + 5)
for i in range(n):
	for j in range(m):
		dp[i + 1][j + 1] = dp[i][j] + 1 if s[i] == t[j] else max(dp[i + 1][j], dp[i][j + 1])
res = []
(i, j) = (n, m)
while i and j:
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	else:
		res.append(s[i - 1])
		i -= 1
		j -= 1
print(''.join(res[::-1]))


import sys
input = sys.stdin.readline
S = input().rstrip()
T = input().rstrip()
DP = [[0] * (len(T) + 1) for i in range(len(S) + 1)]
for i in range(len(S)):
	for j in range(len(T)):
		if S[i] == T[j]:
			DP[i + 1][j + 1] = DP[i][j] + 1
		else:
			DP[i + 1][j + 1] = max(DP[i + 1][j], DP[i][j + 1])
(m, n) = (len(S), len(T))
ans = ''
while m > 0 and n > 0:
	if DP[m][n] == DP[m][n - 1]:
		n -= 1
	elif DP[m][n] == DP[m - 1][n]:
		m -= 1
	else:
		(m, n) = (m - 1, n - 1)
		ans = T[n] + ans
print(ans)


s = input()
t = input()
S = len(s)
T = len(t)
ans = [[0 for e in range(S + 1)] for f in range(T + 1)]
chk = []
for a in range(1, T + 1):
	for b in range(1, S + 1):
		if t[a - 1] == s[b - 1]:
			ans[a][b] = ans[a - 1][b - 1] + 1
		elif ans[a - 1][b] > ans[a][b - 1]:
			ans[a][b] = ans[a - 1][b]
		else:
			ans[a][b] = ans[a][b - 1]
(x, y) = (T, S)
while x > 0 and y > 0:
	if ans[x][y] == ans[x - 1][y]:
		x -= 1
	elif ans[x][y] == ans[x][y - 1]:
		y -= 1
	else:
		x -= 1
		y -= 1
		chk.append(s[y])
chk.reverse()
print(''.join(chk))


s = input()
t = input()
H = len(s)
W = len(t)
dp = [[0 for x in range(W + 1)] for y in range(H + 1)]
for y in range(H):
	for x in range(W):
		if s[y] == t[x]:
			dp[y + 1][x + 1] = dp[y][x] + 1
		else:
			dp[y + 1][x + 1] = max(dp[y + 1][x], dp[y][x + 1])
ans = ''
while H > 0 and W > 0:
	if dp[H][W] == dp[H - 1][W]:
		H -= 1
	elif dp[H][W] == dp[H][W - 1]:
		W -= 1
	else:
		H -= 1
		W -= 1
		ans = s[H] + ans
print(ans)


s = input()
t = input()
lenS = len(s)
lenT = len(t)
dp = [[0] * (lenT + 1) for _ in range(lenS + 1)]
for i in range(1, lenS + 1):
	for j in range(1, lenT + 1):
		if s[i - 1] == t[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
m = lenS
n = lenT
ans = ''
while m and n:
	if dp[m][n] == dp[m - 1][n]:
		m -= 1
		continue
	elif dp[m][n] == dp[m][n - 1]:
		n -= 1
		continue
	else:
		m -= 1
		n -= 1
		ans = ''.join([s[m], ans])
		continue
print(ans)


s = str(input())
t = str(input())
dp = [[0 for i in range(len(s) + 1)] for j in range(len(t) + 1)]
for i in range(1, len(s) + 1):
	for u in range(1, len(t) + 1):
		if s[i - 1] == t[u - 1]:
			dp[u][i] = dp[u - 1][i - 1] + 1
		else:
			dp[u][i] = max(dp[u - 1][i], dp[u][i - 1])
lenth = dp[-1][-1]
i = len(s)
j = len(t)
ans = ''
while lenth > 0:
	if s[i - 1] == t[j - 1]:
		ans = s[i - 1] + ans
		i -= 1
		j -= 1
		lenth -= 1
	elif dp[j][i] == dp[j - 1][i]:
		j -= 1
	else:
		i -= 1
	lenth = dp[j][i]
print(ans)


s = input()
t = input()
len_s = len(s)
len_t = len(t)
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(1, len_s + 1):
	for j in range(1, len_t + 1):
		if s[i - 1] == t[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
rev = ''
i = len_s
j = len_t
while i >= 1 and j >= 1:
	if dp[i][j] == dp[i][j - 1]:
		j -= 1
	elif dp[i][j] == dp[i - 1][j]:
		i -= 1
	else:
		rev = t[j - 1] + rev
		i -= 1
		j -= 1
print(rev)


s = input()
t = input()
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(len(s)):
	for j in range(len(t)):
		if s[i] == t[j]:
			dp[i + 1][j + 1] = dp[i][j] + 1
		else:
			dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
st = ''
x = len(s)
y = len(t)
while x > 0 and y > 0:
	if dp[x][y] == dp[x - 1][y]:
		x -= 1
	elif dp[x][y] == dp[x][y - 1]:
		y -= 1
	else:
		x -= 1
		y -= 1
		st += s[x]
print(st[::-1])


s = input()
t = input()
S = len(s)
T = len(t)
dp = [[0] * (T + 1) for _ in range(S + 1)]
revans = ''
for i in range(1, S + 1):
	for j in range(1, T + 1):
		if s[i - 1] == t[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
while dp[i][j] > 0:
	if dp[i - 1][j] == dp[i][j]:
		i -= 1
	elif dp[i][j - 1] == dp[i][j]:
		j -= 1
	else:
		revans += s[i - 1]
		i -= 1
		j -= 1
print(revans[::-1])


s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n):
	for j in range(m):
		dp[i][j] = max([dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1] + (s[i] == t[j])])
ans = []
i = n - 1
j = m - 1
while i >= 0 and j >= 0:
	if i >= 0 and dp[i - 1][j] == dp[i][j]:
		i -= 1
	elif j >= 0 and dp[i][j - 1] == dp[i][j]:
		j -= 1
	else:
		ans.append(s[i])
		i -= 1
		j -= 1
print(''.join(reversed(ans)))


(s, t) = (input(), input())
(n, m) = (len(s), len(t))
dp = [[0] * -~m for _ in [0] * -~n]
for i in range(n):
	for j in range(m):
		dp[i + 1][j + 1] = dp[i][j] + 1 if s[i] == t[j] else max(dp[i][j + 1], dp[i + 1][j])
R = ''
while n and m:
	if dp[n][m] == dp[n - 1][m]:
		n -= 1
	elif dp[n][m] == dp[n][m - 1]:
		m -= 1
	else:
		n -= 1
		m -= 1
		R = s[n] + R
print(R)


s = input()
t = input()
n = len(s)
m = len(t)
s1 = ''
dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
for i in range(n + 1):
	for j in range(m + 1):
		if i == 0 or j == 0:
			continue
		if s[i - 1] == t[j - 1]:
			dp[i][j] = 1 + dp[i - 1][j - 1]
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
l = dp[n][m]
i = n
j = m
while i >= 0 and j >= 0:
	if s[i - 1] == t[j - 1]:
		s1 += s[i - 1]
		i -= 1
		j -= 1
	elif dp[i][j - 1] > dp[i - 1][j]:
		j -= 1
	else:
		i -= 1
s2 = ''
for u in range(dp[n][m] - 1, -1, -1):
	s2 += s1[u]
print(s2)


s1 = input()
s2 = input()
n = len(s1)
m = len(s2)
dp = [[0 for i in range(m + 1)] for i in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if s1[i - 1] == s2[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
ans = ''
i = n
j = m
while i > 0 and j > 0:
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	else:
		ans = s1[i - 1] + ans
		i -= 1
		j -= 1
print(ans)


s = input()
t = input()
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
ans = []
for (i, _s) in enumerate(s):
	for (j, _t) in enumerate(t):
		dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
		if _s == _t:
			dp[i + 1][j + 1] = max(dp[i][j] + 1, dp[i + 1][j + 1])
(i, j) = (len(s), len(t))
while i > 0 and j > 0:
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	else:
		ans.append(s[i - 1])
		i -= 1
		j -= 1
print(*list(reversed(ans)), sep='')


s = input()
t = input()
(n, m) = (len(s), len(t))
dp = [[0] * 3010 for i in range(3010)]
for i in range(n):
	for j in range(m):
		if s[i] == t[j]:
			dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
		dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
		dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
res = ''
(i, j) = (n, m)
while i > 0 and j > 0:
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	else:
		res = s[i - 1] + res
		i -= 1
		j -= 1
print(res)


a = input()
b = input()
na = len(a)
nb = len(b)
dp = [[0] * (nb + 1) for _ in range(na + 1)]
for i in range(na):
	for j in range(nb):
		if a[i] == b[j]:
			dp[i + 1][j + 1] = dp[i][j] + 1
		else:
			dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
ans = []
num = dp[na][nb]
x = na
y = nb
while num:
	if dp[x][y] == dp[x - 1][y]:
		x -= 1
	elif dp[x][y] == dp[x][y - 1]:
		y -= 1
	else:
		ans.append(a[x - 1])
		x -= 1
		y -= 1
		num -= 1
print(''.join(ans[::-1]))


a = input()
b = input()
dp = [[0] * (len(b) + 1) for i in range(len(a) + 1)]
for x in range(len(a)):
	for y in range(len(b)):
		if a[x] == b[y]:
			dp[x + 1][y + 1] = dp[x][y] + 1
		else:
			dp[x + 1][y + 1] = max(dp[x + 1][y], dp[x][y + 1])
(x, y) = (len(a) - 1, len(b) - 1)
s = ''
while x >= 0 and y >= 0:
	if a[x] == b[y]:
		s = a[x] + s
		x -= 1
		y -= 1
	elif dp[x][y + 1] > dp[x + 1][y]:
		x -= 1
	else:
		y -= 1
print(s)


s = input()
t = input()
Ls = len(s)
Lt = len(t)
dp = [[0] * (Ls + 1) for i in range(Lt + 1)]
Lans = 0
for i in range(1, Lt + 1):
	for j in range(1, Ls + 1):
		if s[j - 1] == t[i - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		Lans = max(Lans, dp[i][j])
i = Lt
j = Ls
ans = [''] * Lans
count = 0
while Lans > 0:
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	else:
		ans[Lans - 1] = s[j - 1]
		i -= 1
		j -= 1
		Lans -= 1
print(''.join(ans))


import sys
input = sys.stdin.readline
s = ' ' + input().rstrip()
t = ' ' + input().rstrip()
m = len(s) - 1
n = len(t) - 1
dp = [[0] * (n + 1) for i in range(m + 1)]
for i in range(1, m + 1):
	for j in range(1, n + 1):
		if s[i] == t[j]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
ans = ''
while m > 0 and n > 0:
	if dp[m][n] == dp[m][n - 1]:
		n -= 1
	elif dp[m][n] == dp[m - 1][n]:
		m -= 1
	elif dp[m][n] == dp[m - 1][n - 1] + 1:
		ans = s[m] + ans
		m -= 1
		n -= 1
print(ans)


S = input()
T = input()
N = len(S)
M = len(T)
dp = [[0 for _ in range(N + 1)] for _ in range(M + 1)]
for i in range(1, M + 1):
	for j in range(1, N + 1):
		if S[j - 1] == T[i - 1]:
			dp[i][j] += dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
(i, j) = (M, N)
lcs = ''
while i > 0 and j > 0:
	if T[i - 1] == S[j - 1]:
		lcs += T[i - 1]
		i -= 1
		j -= 1
	elif dp[i - 1][j] > dp[i][j - 1]:
		i -= 1
	else:
		j -= 1
print(lcs[::-1])


a = input()
b = input()
aa = len(a)
bb = len(b)
dp = [[0] * (bb + 1) for i in range(aa + 1)]
for i in range(aa):
	for j in range(bb):
		if a[i] == b[j]:
			dp[i + 1][j + 1] = dp[i][j] + 1
		else:
			dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
ans = ''
while aa > 0 and bb > 0:
	if a[aa - 1] == b[bb - 1]:
		aa -= 1
		bb -= 1
		ans += a[aa]
	elif dp[aa][bb - 1] > dp[aa - 1][bb]:
		bb -= 1
	else:
		aa -= 1
print(ans[::-1])


S = input()
T = input()
(m, n) = (len(S), len(T))
DP = [[0 for j in range(n + 1)] for i in range(m + 1)]
for i in range(1, m + 1):
	for j in range(1, n + 1):
		if S[i - 1] == T[j - 1]:
			DP[i][j] = DP[i - 1][j - 1] + 1
		else:
			DP[i][j] = max(DP[i][j - 1], DP[i - 1][j])
(i, j) = (m, n)
X = ''
while len(X) < DP[m][n]:
	if S[i - 1] == T[j - 1]:
		X = S[i - 1] + X
		i -= 1
		j -= 1
	elif DP[i][j] == DP[i - 1][j]:
		i -= 1
	elif DP[i][j] == DP[i][j]:
		j -= 1
print(X)


s1 = input()
s2 = input()
l1 = len(s1)
l2 = len(s2)
dp = [[0 for i in range(l2 + 1)] for j in range(l1 + 1)]
for i in range(1, l1 + 1):
	for j in range(1, l2 + 1):
		if s1[i - 1] == s2[j - 1]:
			dp[i][j] = 1 + dp[i - 1][j - 1]
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
i = l1
j = l2
ans = ''
while i > 0 and j > 0:
	if s1[i - 1] == s2[j - 1]:
		ans = s1[i - 1] + ans
		i -= 1
		j -= 1
	elif dp[i - 1][j] > dp[i][j - 1]:
		i -= 1
	else:
		j -= 1
print(ans)


S = str(input())
T = str(input())
ls = len(S)
lt = len(T)
DP = [[0] * (lt + 1) for _ in range(ls + 1)]
for i in range(1, ls + 1):
	for j in range(1, lt + 1):
		if S[i - 1] == T[j - 1]:
			DP[i][j] = max(DP[i - 1][j - 1] + 1, DP[i][j - 1], DP[i - 1][j])
		else:
			DP[i][j] = max(DP[i][j - 1], DP[i - 1][j])
lf = DP[ls][lt]
res = ''
u = ls
v = lt
while u > 0 and v > 0:
	if DP[u][v] == DP[u - 1][v]:
		u -= 1
	elif DP[u][v] == DP[u][v - 1]:
		v -= 1
	else:
		res = S[u - 1] + res
		u -= 1
		v -= 1
print(res)


s = input().strip()
t = input().strip()
ls = len(s)
lt = len(t)
dp = [[0] * (lt + 1) for i in range(ls + 1)]
for i in range(ls):
	for j in range(lt):
		v = dp[i][j] + 1 if s[i] == t[j] else 0
		dp[i + 1][j + 1] = max([v, dp[i + 1][j], dp[i][j + 1]])
ans = ''
(i, j) = (ls, lt)
while i > 0 and j > 0:
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	else:
		ans = s[i - 1] + ans
		i -= 1
		j -= 1
print(ans)


s = input()
t = input()
m = len(s)
n = len(t)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
	for j in range(1, n + 1):
		x = s[i - 1]
		y = t[j - 1]
		if x == y:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
res = ''
while n != 0 and m != 0:
	if dp[m][n] == dp[m - 1][n]:
		m -= 1
	elif dp[m][n] == dp[m][n - 1]:
		n -= 1
	else:
		n -= 1
		m -= 1
		res = s[m] + res
print(res)


s = input()
t = input()
a = len(s)
b = len(t)
dp = [[0] * (b + 1) for i in range(a + 1)]
for j in range(1, a + 1):
	for i in range(1, b + 1):
		if s[j - 1] == t[i - 1]:
			dp[j][i] = dp[j - 1][i - 1] + 1
		else:
			dp[j][i] = max(dp[j - 1][i], dp[j][i - 1])
N = dp[a][b]
y = a
x = b
H = []
while N > 0:
	if dp[y][x - 1] - dp[y][x] == 0:
		x -= 1
		continue
	if dp[y - 1][x] - dp[y][x] == 0:
		y -= 1
		continue
	H.append(t[x - 1])
	N -= 1
	y -= 1
	x -= 1
print(''.join(H[::-1]))


a = input()
b = input()
dp = [[0 for i in range(len(a) + 1)] for j in range(len(b) + 1)]
for i in range(1, len(b) + 1):
	for j in range(1, len(a) + 1):
		if a[j - 1] == b[i - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
res = ''
j = len(a)
i = len(b)
while j > 0 and i > 0:
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	elif dp[i][j] == dp[i - 1][j - 1] + 1:
		res += a[j - 1]
		i -= 1
		j -= 1
print(res[::-1])


a = input()
b = input()
dp = [[0 for j in range(len(b) + 1)] for i in range(len(a) + 1)]
for i in range(1, len(a) + 1):
	for j in range(1, len(b) + 1):
		if a[i - 1] == b[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
			continue
		dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
m = dp[-1][-1]
ans = ''
(i, j) = (-1, -1)
while len(ans) < m:
	if a[i] == b[j]:
		ans = a[i] + ans
		i -= 1
		j -= 1
	elif dp[i - 1][j] > dp[i][j - 1]:
		i -= 1
	else:
		j -= 1
print(ans)


s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if s[i - 1] == t[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
i = n
j = m
st = ''
while dp[i][j]:
	while dp[i - 1][j] == dp[i][j]:
		i -= 1
	while dp[i][j - 1] == dp[i][j]:
		j = j - 1
	j -= 1
	st += s[i - 1]
	i -= 1
print(st[::-1])


s = str(0) + input()
t = str(0) + input()
dp = [[0] * len(t) for i in range(len(s))]
for i in range(1, len(s)):
	for j in range(1, len(t)):
		if s[i] == t[j]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
ans = [''] * dp[i][j]
i = len(s) - 1
j = len(t) - 1
k = dp[i][j] - 1
while i > 0 and j > 0:
	if s[i] == t[j]:
		ans[k] = s[i]
		k -= 1
		i -= 1
		j -= 1
	elif dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
print(''.join(ans))


s = input()
t = input()
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(1, len(s) + 1):
	for j in range(1, len(t) + 1):
		if s[i - 1] == t[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
(i, j) = (len(s), len(t))
f = ''
while (i > 0) & (j > 0):
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	else:
		f += s[i - 1]
		i -= 1
		j -= 1
print(f[::-1])


s = input()
t = input()
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for n in range(len(s)):
	for m in range(len(t)):
		if s[n] == t[m]:
			dp[n + 1][m + 1] = dp[n][m] + 1
		else:
			dp[n + 1][m + 1] = max(dp[n + 1][m], dp[n][m + 1])
n = len(s)
m = len(t)
ans = ''
while n >= 0 and m >= 0:
	if dp[n][m] == dp[n - 1][m]:
		n -= 1
	elif dp[n][m] == dp[n][m - 1]:
		m -= 1
	else:
		ans = s[n - 1] + ans
		n -= 1
		m -= 1
print(ans)


S = input()
T = input()
dp = [[0] * (len(T) + 1) for i in range(len(S) + 1)]
for (i, s) in enumerate(S, 1):
	for (j, t) in enumerate(T, 1):
		if s == t:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
ans = []
while i > 0 and j > 0:
	if dp[i][j] == dp[i][j - 1]:
		j -= 1
	elif dp[i][j] == dp[i - 1][j]:
		i -= 1
	else:
		ans.append(S[i - 1])
		i -= 1
		j -= 1
print(''.join(ans[::-1]))


(s, t) = (input(), input())
(ls, lt) = (len(s), len(t))
table = [[0] * (lt + 1) for i in range(ls + 1)]
for ss in range(ls):
	for st in range(lt):
		table[ss + 1][st + 1] = table[ss][st] + 1 if s[ss] == t[st] else max(table[ss + 1][st], table[ss][st + 1])
ans = ''
(ss, st) = (ls, lt)
while ss * st != 0:
	if table[ss][st] == table[ss - 1][st]:
		ss -= 1
	elif table[ss][st] == table[ss][st - 1]:
		st -= 1
	else:
		ss -= 1
		st -= 1
		ans = s[ss] + ans
print(ans)


s = input()
t = input()
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for (i, ei) in enumerate(s, 1):
	for (j, ej) in enumerate(t, 1):
		dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], (dp[i - 1][j - 1] + 1) * (ei == ej))
i = len(s)
j = len(t)
ans = []
while i and j:
	if dp[i - 1][j] == dp[i][j]:
		i -= 1
	elif dp[i][j - 1] == dp[i][j]:
		j -= 1
	else:
		ans.append(s[i - 1])
		i -= 1
		j -= 1
ans = ''.join(ans[::-1])
print(ans)


s = input()
t = input()
lens = len(s)
lent = len(t)
dp = [[0] * (lent + 1) for _ in range(lens + 1)]
for i in range(lens):
	for j in range(lent):
		if s[i] == t[j]:
			dp[i + 1][j + 1] = dp[i][j] + 1
		else:
			dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
i = lens
j = lent
ans = ''
while i > 0 and j > 0:
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	elif dp[i][j] == dp[i - 1][j - 1] + 1:
		ans = s[i - 1] + ans
		i -= 1
		j -= 1
print(ans)


S = input()
T = input()
M = len(S)
N = len(T)
dp = [[0] * (N + 1) for _ in range(M + 1)]
for (i, s) in enumerate(S):
	for (j, t) in enumerate(T):
		if s == t:
			dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
		dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1])
res = ''
while M > 0 and N > 0:
	if dp[M][N] == dp[M - 1][N]:
		M -= 1
	elif dp[M][N] == dp[M][N - 1]:
		N -= 1
	else:
		res = S[M - 1] + res
		M -= 1
		N -= 1
print(res)


(S, T) = (input(), input())
dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]
for i in range(1, len(S) + 1):
	for j in range(1, len(T) + 1):
		dp[i][j] = max(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1] + (S[i - 1] == T[j - 1]))
res = []
(x, y) = (len(S), len(T))
v = dp[x][y]
while v > 0:
	if dp[x - 1][y] == v:
		x -= 1
	elif dp[x][y - 1] == v:
		y -= 1
	else:
		res.append(S[x - 1])
		x -= 1
		y -= 1
	v = dp[x][y]
print(''.join(reversed(res)))


S = input()
T = input()
dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]
for i in range(1, len(S) + 1):
	s = S[i - 1]
	for j in range(1, len(T) + 1):
		t = T[j - 1]
		if s == t:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
ans = ''
i = len(S)
j = len(T)
while i > 0 and j > 0:
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	elif dp[i][j] == dp[i - 1][j - 1] + 1:
		ans += S[i - 1]
		i -= 1
		j -= 1
print(''.join(reversed(list(ans))))


s1 = list(input())
s2 = list(input())
n = len(s1)
m = len(s2)
dp = [[0] * (m + 1) for _ in range(n + 1)]
dp = [[0] * (m + 1) for i in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if s1[i - 1] == s2[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
res = []
(i, j) = (n, m)
while i > 0 and j > 0:
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	else:
		res.append(s1[i - 1])
		i -= 1
		j -= 1
print(''.join(res[::-1]))


S = input()
T = input()
(X, Y) = (len(S), len(T))
L = [[0 for _ in range(Y + 1)] for _ in range(X + 1)]
for i in range(X):
	for j in range(Y):
		if S[i] == T[j]:
			L[i + 1][j + 1] = L[i][j] + 1
		else:
			L[i + 1][j + 1] = max(L[i][j + 1], L[i + 1][j], L[i + 1][j + 1])
K = ''
while X * Y:
	if S[X - 1] == T[Y - 1]:
		K += S[X - 1]
		X -= 1
		Y -= 1
	elif L[X - 1][Y] > L[X][Y - 1]:
		X -= 1
	else:
		Y -= 1
print(K[::-1])


s = input()
t = input()
n = len(t) + 1
m = len(s) + 1
data = [[0 for _ in range(n)] for _ in range(m)]
ans = ''
for i in range(1, m):
	for j in range(1, n):
		if s[i - 1] == t[j - 1]:
			data[i][j] = data[i - 1][j - 1] + 1
		else:
			data[i][j] = max(data[i - 1][j], data[i][j - 1])
i = len(s)
j = len(t)
while i > 0 and j > 0:
	if data[i][j] == data[i][j - 1]:
		j -= 1
	elif data[i][j] == data[i - 1][j]:
		i -= 1
	else:
		ans = s[i - 1] + ans
		i -= 1
		j -= 1
print(ans)


X = input()
Y = input()
dp = [[0] * (len(Y) + 1) for _ in [0] * (len(X) + 1)]
for (i, x) in enumerate(X):
	i += 1
	for (j, y) in enumerate(Y):
		j += 1
		dp[i][j] = max(dp[i - 1][j - 1] + int(x == y), dp[i - 1][j], dp[i][j - 1])
ans = []
cnt = dp[-1][-1]
x = y = -1
while cnt:
	while dp[x - 1][y] == cnt:
		x -= 1
	while dp[x][y - 1] == cnt:
		y -= 1
	ans.append(X[x])
	cnt -= 1
	x -= 1
	y -= 1
ans = ''.join(ans)[::-1]
print(ans)


s = input()
t = input()
(m, n) = (len(s), len(t))
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
	for j in range(n):
		if s[i] == t[j]:
			dp[i + 1][j + 1] = dp[i][j] + 1
		elif dp[i + 1][j] > dp[i][j + 1]:
			dp[i + 1][j + 1] = dp[i + 1][j]
		else:
			dp[i + 1][j + 1] = dp[i][j + 1]
(a, b) = (m, n)
tmp = ''
while a and b:
	if s[a - 1] == t[b - 1]:
		a -= 1
		b -= 1
		tmp += s[a]
	elif dp[a][b] == dp[a - 1][b]:
		a -= 1
	else:
		b -= 1
print(tmp[::-1])


s = input()
t = input()
dp = [[0 for j in range(len(t) + 1)] for i in range(len(s) + 1)]
res = ''
for i in range(1, len(s) + 1):
	for j in range(1, len(t) + 1):
		if s[i - 1] == t[j - 1]:
			dp[i][j] = 1 + dp[i - 1][j - 1]
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
length = dp[-1][-1]
res = [''] * (length + 1)
i = len(s)
j = len(t)
while i > 0 and j > 0:
	if s[i - 1] == t[j - 1]:
		res[length - 1] = s[i - 1]
		i -= 1
		j -= 1
		length -= 1
	elif dp[i - 1][j] > dp[i][j - 1]:
		i -= 1
	else:
		j -= 1
print(''.join(res))


(s, t) = ('0' + input(), '0' + input())
(ns, nt) = (len(s) + 1, len(t) + 1)
dp = [[0 for i in range(nt)] for i in range(ns)]
for i in range(1, ns):
	for j in range(1, nt):
		if s[i - 1] == t[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
(i, j) = (ns - 1, nt - 1)
ans = ''
while i > 0 or j > 0:
	if dp[i][j] == dp[i][j - 1]:
		j -= 1
	elif dp[i][j] == dp[i - 1][j]:
		i -= 1
	else:
		ans = s[i - 1] + ans
		i -= 1
		j -= 1
print(ans[1:])


s = input()
t = input()
ns = len(s)
nt = len(t)
dp = [[0] * (nt + 1) for _ in range(ns + 1)]
for i in range(ns):
	for j in range(nt):
		if s[i] == t[j]:
			dp[i + 1][j + 1] = dp[i][j] + 1
		else:
			dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
ans = []
(i, j) = (ns, nt)
while dp[i][j]:
	while dp[i - 1][j] == dp[i][j]:
		i -= 1
	while dp[i][j - 1] == dp[i][j]:
		j -= 1
	ans.append(s[i - 1])
	i -= 1
	j -= 1
ans.reverse()
print(''.join(ans))


S = input()
T = input()
dp = [[0 for j in range(len(T) + 1)] for i in range(len(S) + 1)]
for i in range(len(S)):
	for j in range(len(T)):
		if S[i] == T[j]:
			dp[i + 1][j + 1] = dp[i][j] + 1
		dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
		dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
i = len(S)
j = len(T)
ans = ''
while i > 0 and j > 0:
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	else:
		ans = S[i - 1] + ans
		i -= 1
		j -= 1
print(ans)


s = input()
t = input()
N = len(s)
M = len(t)
dp = [[0] * (N + 1) for i in range(M + 1)]
for i in range(1, M + 1):
	for j in range(1, N + 1):
		if s[j - 1] == t[i - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
L = dp[-1][-1]
i = M
j = N
ans = [''] * L
cur = L - 1
while i >= 0 and j >= 0:
	if dp[i][j] != dp[i - 1][j] and dp[i][j] != dp[i][j - 1]:
		ans[cur] = s[j - 1]
		i -= 1
		j -= 1
		cur -= 1
	elif dp[i][j] == dp[i - 1][j]:
		i -= 1
	else:
		j -= 1
print(''.join(ans))


(s, t) = (input(), input())
(ls, lt) = (len(s), len(t))
dp = [[0] * (lt + 1) for _ in range(ls + 1)]
for i in range(1, ls + 1):
	for j in range(1, lt + 1):
		if s[i - 1] == t[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
l = dp[-1][-1]
(i, j, a) = (ls, lt, '')
while l != 0:
	if dp[i][j] == dp[i][j - 1]:
		j -= 1
	elif dp[i][j] == dp[i - 1][j]:
		i -= 1
	else:
		a = s[i - 1] + a
		i -= 1
		j -= 1
		l -= 1
print(a)


s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0] * (lt + 1) for i in range(ls + 1)]
for i in range(1, ls + 1):
	for j in range(1, lt + 1):
		dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		if s[i - 1] == t[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
i = ls
j = lt
ans = ''
while i >= 1 and j >= 1:
	if dp[i][j] == dp[i][j - 1]:
		j -= 1
		continue
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
		continue
	ans = s[i - 1] + ans
	i -= 1
	j -= 1
print(ans)


import sys
input = sys.stdin.readline
s = input().rstrip()
t = input().rstrip()
ls = len(s)
lt = len(t)
dp = [[0] * (lt + 1) for _ in range(ls + 1)]
for i in range(ls):
	for j in range(lt):
		if s[i] == t[j]:
			dp[i + 1][j + 1] = dp[i][j] + 1
		else:
			dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
ans = ''
while ls > 0 and lt > 0:
	if dp[ls][lt] == dp[ls - 1][lt]:
		ls -= 1
	elif dp[ls][lt] == dp[ls][lt - 1]:
		lt -= 1
	else:
		ans = s[ls - 1] + ans
		ls -= 1
		lt -= 1
print(ans)


s = input()
t = input()
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for sx in range(len(s)):
	for ty in range(len(t)):
		if s[sx] == t[ty]:
			dp[sx + 1][ty + 1] = dp[sx][ty] + 1
		else:
			dp[sx + 1][ty + 1] = max(dp[sx + 1][ty], dp[sx][ty + 1])
ans = ''
i = len(s)
j = len(t)
while i > 0:
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	else:
		ans = t[j - 1] + ans
		i -= 1
		j -= 1
print(ans)


(S, T) = (input(), input())
dp = [[0] * (len(T) + 1)] + [[0] + [None] * len(T) for _ in range(len(S))]
for (i, s) in enumerate(S):
	for (j, t) in enumerate(T):
		dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j], dp[i][j] + int(s == t))
res = []
(x, y) = (len(S), len(T))
while x > 0 and y > 0:
	if dp[x][y] == dp[x - 1][y]:
		x -= 1
	elif dp[x][y] == dp[x][y - 1]:
		y -= 1
	else:
		x -= 1
		y -= 1
		res.append(S[x])
print(''.join(reversed(res)))


s = input()
t = input()
(ls, lt) = (len(s), len(t))
dp = [[0] * (lt + 1) for _ in [0] * (ls + 1)]
for (i, cs) in enumerate(s, 1):
	for (j, ct) in enumerate(t, 1):
		if cs == ct:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
i = ls
j = lt
ans = ''
while i > 0 and j > 0:
	if s[i - 1] == t[j - 1]:
		ans += s[i - 1]
		i -= 1
		j -= 1
	elif dp[i - 1][j] > dp[i][j - 1]:
		i -= 1
	else:
		j -= 1
print(ans[::-1])


S = input()
T = input()
dp = [[0 for i in range(len(T) + 1)] for j in range(len(S) + 1)]
for i in range(len(S)):
	for j in range(len(T)):
		dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j], dp[i][j] + (S[i] == T[j]))
st = []
x = len(S)
y = len(T)
while x > 0 and y > 0:
	if dp[x][y] == dp[x - 1][y]:
		x -= 1
	elif dp[x][y] == dp[x][y - 1]:
		y -= 1
	else:
		x -= 1
		y -= 1
		st += S[x]
print(''.join(reversed(st)))


(s, t) = (input(), input())
(m, n) = (len(s), len(t))
l = [[0 for i in range(n + 1)] for j in range(m + 1)]
for i in range(1, m + 1):
	for j in range(1, n + 1):
		if s[i - 1] == t[j - 1]:
			l[i][j] = l[i - 1][j - 1] + 1
		else:
			l[i][j] = max(l[i - 1][j], l[i][j - 1])
pos = l[m][n]
(i, j, lcs) = (m, n, [''] * (pos + 1))
while i > 0 and j > 0:
	if s[i - 1] == t[j - 1]:
		lcs[pos - 1] = s[i - 1]
		(i, j, pos) = (i - 1, j - 1, pos - 1)
	elif l[i - 1][j] > l[i][j - 1]:
		i -= 1
	else:
		j -= 1
print(''.join(lcs))


s = list(input())
t = list(input())
dp = [[0] * (len(t) + 1) for i in range(len(s) + 1)]
num = []
for i in range(len(s)):
	for j in range(len(t)):
		if s[i] == t[j]:
			dp[i + 1][j + 1] = dp[i][j] + 1
		else:
			dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1])
ans = ''
i = len(s)
j = len(t)
while j > 0 and i > 0:
	if dp[i - 1][j] == dp[i][j]:
		i -= 1
	elif dp[i][j - 1] == dp[i][j]:
		j -= 1
	else:
		ans += s[i - 1]
		i -= 1
		j -= 1
print(ans[::-1])


s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0 for j in range(lt + 1)] for i in range(ls + 1)]
for i in range(1, ls + 1):
	for j in range(1, lt + 1):
		if s[i - 1] == t[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
ans = ''
length = dp[ls][lt]
i = ls
j = lt
while length > 0:
	if s[ls - 1] == t[lt - 1]:
		ans = s[ls - 1] + ans
		ls -= 1
		lt -= 1
		length -= 1
	elif dp[ls - 1][lt] == length:
		ls -= 1
	else:
		lt -= 1
print(ans)


S = input()
T = input()
s = len(S)
t = len(T)
dp = [[0 for i in range(s + 1)] for j in range(t + 1)]
for i in range(1, t + 1):
	for j in range(1, s + 1):
		if S[j - 1] == T[i - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
arr = []
while i > 0 and j > 0:
	if S[j - 1] == T[i - 1]:
		arr += [j - 1]
		j -= 1
		i -= 1
	elif dp[i - 1][j] > dp[i][j - 1]:
		i -= 1
	else:
		j -= 1
arr.sort()
for i in arr:
	print(S[i], end='')


s = list(input())
t = list(input())
a = len(s)
b = len(t)
dp = [[0] * (b + 1) for _ in range(a + 1)]
ans = ''
for i in range(a):
	for j in range(b):
		if s[i] == t[j]:
			dp[i + 1][j + 1] = dp[i][j] + 1
		else:
			dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
i = a
j = b
while i >= 0 and j >= 0:
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	else:
		ans = t[j - 1] + ans
		i -= 1
		j -= 1
print(ans)


s = input()
t = input()
(n1, n2) = (len(s), len(t))
dp = [[0] * (n1 + 1) for i in range(n2 + 1)]
st = ''
for i in range(1, n2 + 1):
	for j in range(1, n1 + 1):
		if s[j - 1] == t[i - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
while i > 0 and j > 0:
	if t[i - 1] == s[j - 1]:
		st = s[j - 1] + st
		i -= 1
		j -= 1
	elif dp[i][j - 1] > dp[i - 1][j]:
		j -= 1
	else:
		i -= 1
print(st)


s = input()
t = input()
sl = len(s)
tl = len(t)
dp = [[0 for i in range(tl + 1)] for _ in range(sl + 1)]
if s[0] == t[0]:
	dp[0][0] = 1
for i in range(sl):
	for j in range(tl):
		if s[i] == t[j]:
			dp[i + 1][j + 1] = max(dp[i][j] + 1, dp[i + 1][j + 1])
		dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1])
ans = str()
while sl > 0 and tl > 0:
	if dp[sl][tl] == dp[sl - 1][tl]:
		sl -= 1
	elif dp[sl][tl] == dp[sl][tl - 1]:
		tl -= 1
	else:
		ans += s[sl - 1]
		sl -= 1
		tl -= 1
print(ans[::-1])


S = input()
T = input()
ls = len(S)
lt = len(T)
DP = [[0] * (ls + 1) for _ in range(lt + 1)]
for i in range(lt):
	for j in range(ls):
		if T[i] == S[j]:
			DP[i + 1][j + 1] = DP[i][j] + 1
		else:
			DP[i + 1][j + 1] = max(DP[i + 1][j], DP[i][j + 1])
ans = ''
while ls * lt > 0:
	if DP[lt][ls] == DP[lt - 1][ls]:
		lt -= 1
	elif DP[lt][ls] == DP[lt][ls - 1]:
		ls -= 1
	elif DP[lt][ls] == DP[lt - 1][ls - 1] + 1:
		lt -= 1
		ls -= 1
		ans += S[ls]
print(ans[::-1])


s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
for j in range(1, n + 1):
	for i in range(1, m + 1):
		if s[j - 1] == t[i - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
i = n
j = m
inde = dp[m][n]
an = [''] * (inde + 1)
while i > 0 and j > 0:
	if s[i - 1] == t[j - 1]:
		an[inde - 1] = s[i - 1]
		i -= 1
		j -= 1
		inde -= 1
	elif dp[j - 1][i] > dp[j][i - 1]:
		j -= 1
	else:
		i -= 1
print(''.join(an))


s = tuple(input())
t = tuple(input())
n = len(s)
m = len(t)
dp = [[0] * (m + 1) for i in range(n + 1)]
for i in range(1, n + 1):
	for j in range(1, m + 1):
		if s[i - 1] == t[j - 1]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
res = []
while n != 0 and m != 0:
	if dp[n][m] == dp[n - 1][m]:
		n -= 1
	elif dp[n][m] == dp[n][m - 1]:
		m -= 1
	else:
		n -= 1
		m -= 1
		res.append(s[n])
print(''.join(res[::-1]))


s = ' ' + input()
t = ' ' + input()
dp = [[0] * len(t) for _ in range(len(s))]
for i in range(1, len(s)):
	for j in range(1, len(t)):
		if s[i] == t[j]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
ans = []
(i, j) = (len(s) - 1, len(t) - 1)
while dp[i][j]:
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	else:
		ans.append(s[i])
		i -= 1
		j -= 1
print(''.join(ans[::-1]))


s = ' ' + input().strip()
t = ' ' + input().strip()
(LS, LT) = (len(s), len(t))
dp = [[0] * LT for _ in range(LS)]
for i in range(1, LS):
	for j in range(1, LT):
		if s[i] == t[j]:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
(a, b) = (LS - 1, LT - 1)
r = ''
while a > 0 and b > 0:
	if s[a] == t[b]:
		r += s[a]
		(a, b) = (a - 1, b - 1)
	elif dp[a][b] == dp[a - 1][b]:
		a -= 1
	else:
		b -= 1
print(r[::-1])


a = input()
b = input()
(n, m) = (len(a), len(b))
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n):
	for j in range(m):
		if a[i] == b[j]:
			dp[i + 1][j + 1] = dp[i][j] + 1
		else:
			dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
(c, d) = (n, m)
ans = ''
while c > 0 and d > 0:
	if dp[c - 1][d] == dp[c][d]:
		c -= 1
	elif dp[c][d - 1] == dp[c][d]:
		d -= 1
	else:
		ans = a[c - 1] + ans
		c -= 1
		d -= 1
print(ans)


s = list(input())
t = list(input())
ns = len(s)
nt = len(t)
dp = [[0] * (nt + 1) for _ in range(ns + 1)]
for i in range(ns):
	for j in range(nt):
		if s[i] == t[j]:
			dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
		else:
			dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
ans = []
(i, j) = (ns, nt)
while i != 0 and j != 0:
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	elif dp[i][j] == dp[i - 1][j - 1] + 1:
		ans = [s[i - 1]] + ans
		i -= 1
		j -= 1
print(''.join(ans))


S = input().strip()
T = input().strip()
dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]
for (i, s) in enumerate(S):
	for (j, t) in enumerate(T):
		if s == t:
			dp[i][j] = dp[i - 1][j - 1] + 1
		else:
			dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
ans = []
s = (len(S) - 1, len(T) - 1)
while True:
	(x, y) = s
	if x < 0 or y < 0:
		break
	if S[x] == T[y]:
		ans.append(S[x])
		s = (x - 1, y - 1)
	elif dp[x - 1][y] > dp[x][y - 1]:
		s = (x - 1, y)
	else:
		s = (x, y - 1)
print(''.join(reversed(ans)))


def solve():
	ans = ''
	S = input()
	T = input()
	(n, m) = (len(S), len(T))
	dp = [[0] * (m + 1) for _ in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if S[i - 1] == T[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	(i, j) = (n, m)
	while i > 0 and j > 0:
		if dp[i - 1][j] == dp[i][j]:
			i -= 1
		elif dp[i][j - 1] == dp[i][j]:
			j -= 1
		else:
			ans = S[i - 1] + ans
			i -= 1
			j -= 1
	return ans
print(solve())


n = input()
m = input()
x = len(n)
y = len(m)
dp = [[0 for i in range(y + 1)] for j in range(x + 1)]
for i in range(0, x + 1):
	for j in range(0, y + 1):
		if i == 0 or j == 0:
			dp[i][j] = 0
		elif n[i - 1] == m[j - 1]:
			dp[i][j] = 1 + dp[i - 1][j - 1]
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
j = y
i = x
ans = ''
while i > 0 and j > 0:
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	else:
		ans = n[i - 1] + ans
		i -= 1
		j -= 1
print(ans)


s = input()
t = input()
a = len(s)
b = len(t)
dp = [[0 for _ in range(a + 1)] for _ in range(b + 1)]
for j in range(1, b + 1):
	for i in range(1, a + 1):
		if s[i - 1] == t[j - 1]:
			dp[j][i] = dp[j - 1][i - 1] + 1
		else:
			dp[j][i] = max(dp[j - 1][i], dp[j][i - 1])
ans = ''
x = a
y = b
while dp[y][x] != 0:
	if dp[y][x] == dp[y - 1][x]:
		y -= 1
	elif dp[y][x] == dp[y][x - 1]:
		x -= 1
	else:
		ans += s[x - 1]
		y -= 1
		x -= 1
print(ans[::-1])


s1 = input()
s2 = input()
a = [[0] * (len(s2) + 1) for i in range(len(s1) + 1)]
res = ''
for i in range(1, len(s1) + 1):
	for j in range(1, len(s2) + 1):
		if s1[i - 1] == s2[j - 1]:
			a[i][j] = a[i - 1][j - 1] + 1
		elif a[i - 1][j] >= a[i][j - 1]:
			a[i][j] = a[i - 1][j]
		else:
			a[i][j] = a[i][j - 1]
i = len(s1)
j = len(s2)
while i > 0 and j > 0:
	if a[i][j] == a[i - 1][j]:
		i -= 1
	elif a[i][j] == a[i][j - 1]:
		j -= 1
	else:
		res = s1[i - 1] + res
		i -= 1
		j -= 1
print(res)


def main():
	s = input()
	t = input()
	dp = [['' for _ in range(3010)] for _ in range(3010)]
	for i in range(len(s)):
		for j in range(len(t)):
			dp[i + 1][j + 1] = dp[i][j + 1] if len(dp[i][j + 1]) >= len(dp[i + 1][j]) else dp[i + 1][j]
			if s[i] == t[j] and len(dp[i][j]) + 1 > len(dp[i + 1][j + 1]):
				dp[i + 1][j + 1] = dp[i][j] + s[i]
	print(dp[len(s)][len(t)])
main()


s = input()
t = input()
b = len(t)
a = len(s)
dp = [[0 for i in range(a + 1)] for j in range(b + 1)]
for i in range(b + 1):
	for j in range(a + 1):
		if i == 0 or j == 0:
			continue
		if t[i - 1] == s[j - 1]:
			dp[i][j] = 1 + dp[i - 1][j - 1]
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
i = b
j = a
l = []
while i > 0 and j > 0:
	if t[i - 1] == s[j - 1]:
		l.append(t[i - 1])
		i = i - 1
		j = j - 1
	elif dp[i - 1][j] > dp[i][j - 1]:
		i = i - 1
	else:
		j = j - 1
for i in reversed(l):
	print(i, end='')


s = input()
t = input()
ma = 0
a = [0, 0]
dp = [[0 for i in range(len(t) + 1)] for j in range(len(s) + 1)]
for i in range(1, len(s) + 1):
	for j in range(1, len(t) + 1):
		dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		if s[i - 1] == t[j - 1]:
			dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1])
i = len(s)
j = len(t)
ss = ''
while i and j:
	if dp[i][j] == dp[i - 1][j]:
		i -= 1
	elif dp[i][j] == dp[i][j - 1]:
		j -= 1
	else:
		ss += s[i - 1]
		i -= 1
		j -= 1
ss = ss[-1::-1]
print(ss)


(S, T) = (input(), input())
(x, y) = (len(S), len(T))
dp = [[0] * (y + 1) for _ in range(x + 1)]
for (i, s) in enumerate(S):
	for (j, t) in enumerate(T):
		dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j], dp[i][j] + int(s == t))
a = ''
while x > 0 and y > 0:
	if dp[x][y] == dp[x - 1][y]:
		x -= 1
	elif dp[x][y] == dp[x][y - 1]:
		y -= 1
	else:
		x -= 1
		y -= 1
		a += S[x]
print(a[::-1])


S = input()
T = input()
N = len(S)
M = len(T)
dp = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
	for k in range(1, M + 1):
		if S[i - 1] == T[k - 1]:
			dp[i][k] = dp[i - 1][k - 1] + 1
		else:
			dp[i][k] = max(dp[i - 1][k], dp[i][k - 1])
ans = ''
x = N
y = M
while x > 0 and y > 0:
	if dp[x][y] == dp[x - 1][y]:
		x -= 1
	elif dp[x][y] == dp[x][y - 1]:
		y -= 1
	else:
		x -= 1
		y -= 1
		ans += S[x]
print(ans[::-1])


s = input()
t = input()
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(1, len(s) + 1):
	for j in range(1, len(t) + 1):
		k = dp[i - 1][j]
		if dp[i][j - 1] > k:
			k = dp[i][j - 1]
		if s[i - 1] == t[j - 1] and dp[i - 1][j - 1] + 1 > k:
			k = dp[i - 1][j - 1] + 1
		dp[i][j] = k
u = []
while i > 0 and j > 0:
	if dp[i - 1][j] == dp[i][j]:
		i -= 1
	elif dp[i][j - 1] == dp[i][j]:
		j -= 1
	else:
		u.append(s[i - 1])
		i -= 1
		j -= 1
print(''.join(reversed(u)))