Problem:
 Score : 100 points    Problem Statement You are given strings s and t .
Find one longest string that is a subsequence of both s and t .      Notes A subsequence of a string x is the string obtained by removing zero or more characters from x and concatenating the remaining characters without changing the order.      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.        Sample Input 1 axyb
abyxb      Sample Output 1 axb  The answer is axb or ayb ; either will be accepted.       Sample Input 2 aa
xayaz      Sample Output 2 aa       Sample Input 3 a
z      Sample Output 3   The answer is (an empty string).       Sample Input 4 abracadabra
avadakedavra      Sample Output 4 aaadara

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines







def main():
	s=input().rstrip().decode('utf-8')
	t=input().rstrip().decode('utf-8')
	slen=len(s)
	tlen=len(t)
	
	dp=[[0]*(slen+1) for _ in range(tlen+1)]
	pr=[[0]*(slen+1) for _ in range(tlen+1)]
	
	
	for i in range(tlen):
		for j in range(slen):
			if s[j]==t[i]:
				dp[i+1][j+1]=dp[i][j]+1
				pr[i+1][j+1]=1
			elif dp[i][j+1]<dp[i+1][j]:
				dp[i+1][j+1]=dp[i+1][j]
				pr[i + 1][j + 1] = 2
			else:
				dp[i+1][j+1]=dp[i][j+1]
				pr[i + 1][j + 1] = 3
	
	ss=slen
	tt=tlen
	ans=""
	while ss>0 and tt>0:
		if pr[tt][ss]==1:
			ans+=s[ss-1]
			tt-=1
			ss-=1
		elif pr[tt][ss]==2:
			ss-=1
		else:
			tt-=1
	print(ans[::-1])
	
	
	
if __name__ == "__main__":
	main()

Solution (Python):
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

s = ns()
t = ns()
S, T = len(s), len(t)
dp = [[0] * (T+1) for _ in range(S+1)]

for i in range(0,S):
    for j in range(0,T):
        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])

i, j = S, 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)

Solution (Python):
s = input()
t = input()

t_len = len(t)
s_len = len(s)

dp = [[0]*(t_len+1) for _ in range(s_len+1)]

for i in range(1,s_len+1):
    for j in range(1,t_len+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])



s_len_tmp = s_len
t_len_tmp = t_len
ans = ''

while s_len_tmp > 0 and t_len_tmp > 0:
    if dp[s_len_tmp][t_len_tmp] == dp[s_len_tmp-1][t_len_tmp]:
        s_len_tmp -= 1
    elif dp[s_len_tmp][t_len_tmp] == dp[s_len_tmp][t_len_tmp-1]:
        t_len_tmp -= 1
    else:
        ans += s[s_len_tmp-1]
        s_len_tmp -= 1
        t_len_tmp -= 1
   
print(ans[::-1])

Solution (Python):
def solve(n, m, s, t):
    dp = [[0 for i in range(m + 1)] for _ in range(n + 1)]
    for i in range(n):
        for j in range(m):
            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])

    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)
    return

s = input()
t = input()

solve(len(s), len(t), s, t)

Solution (Python):
*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+1][j], dp[i][j+1])

ans = ""

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 = s[i-1] + ans
        i -= 1
        j -= 1

print(ans)

Solution (Python):
def solve():
    S = input()
    T = input()
    len_t = len(T)
    len_s = len(S)
    dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
    for i, s in enumerate(S):
        pre_dp_i = dp[i]
        dp_i = dp[i+1]
        for j, t in enumerate(T):
            tmp_dp = max((pre_dp_i[j] + 1) * (s == t),
                         pre_dp_i[j+1],
                         dp_i[j])
            dp_i[j+1] = tmp_dp
    res = ''
    while len_t > 0 and len_s > 0:
        current = dp[len_s][len_t]
        if current == dp[len_s - 1][len_t]:
            len_s -= 1
        elif current == dp[len_s][len_t - 1]:
            len_t -= 1
        else:
            res = S[len_s - 1] + res
            len_s -= 1
            len_t -= 1
    return res


if __name__ == "__main__":
    answer = solve()
    print(answer)

Solution (Python):
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)))

Solution (Python):
import sys

input=sys.stdin.readline
s=input()
t=input()
n,m=len(s),len(t)

dp=[[0]*(m+1) for i in range(n+1)]
ans=[]

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],dp[i][j+1])
    else:
      dp[i+1][j+1]=dp[i][j]+1
      
i,j=n,m      
while i>0 and j>0:
  if s[i-1]==t[j-1]:
    ans.append(s[i-1])
    i-=1
    j-=1
  elif dp[i][j]==dp[i-1][j]:
    i-=1
  else:
    j-=1
print(''.join(ans[::-1]))

Solution (Python):
S = input()
T = input()

lenS = len(S)
lenT = len(T) 
memo = []
dp = [[0]*(lenS+1) for _ in range(lenT+1)]
for i in range(1,lenT+1):
    for j in range(1,lenS+1):
        if S[j-1] == T[i-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])
 

ans = ""
s = lenS
t = lenT
while s>0 and t>0:
    if S[s-1] == T[t-1]:
        ans += S[s-1]
        s -= 1
        t -= 1
    else:
        if dp[t][s-1] > dp[t-1][s]:
            s -= 1
        else:
            t -= 1
print(ans[::-1])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=S()
  t=S()

  lns=len(s)
  lnt=len(t)

  dp=[[0 for _ in range(lns+1)]for _ in range(lnt+1)]
  for i in range(lnt):
    for j in range(lns):
      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])

  ans=''
  i=lnt
  j=lns
  while dp[i][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]:
      i-=1
      j-=1
    elif dp[i][j]==dp[i-1][j-1]+1:
      ans=t[i-1]+ans
      i-=1
      j-=1

  return ans


print(main())

Solution (Python):
s = str(input())
t = str(input())

dp = [[0]*3100 for _ in range(3100)]


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+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)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    S=input()
    T=input()
    dp=[[0]*(len(T)+1) for _ in range(len(S)+1)]
    dp2=[[()]*(len(T)+1) for _ in range(len(S)+1)]
    for s in range(len(S)):
        for t in range(len(T)):
            if S[s]==T[t]:
                dp[s+1][t+1]=dp[s][t]+1
                dp2[s+1][t+1]=(s,t)
            else:
                if dp[s+1][t]>dp[s][t+1]:
                    dp[s+1][t+1]=dp[s+1][t]
                    dp2[s+1][t+1]=dp2[s+1][t]
                else:
                    dp[s+1][t+1]=dp[s][t+1]
                    dp2[s+1][t+1]=dp2[s][t+1]
    tmp=dp2[len(S)][len(T)]
    if tmp:
        ans=deque()
        ans.appendleft(S[tmp[0]])
        for _ in range(dp[len(S)][len(T)]-1):
            tmp=dp2[tmp[0]][tmp[1]]
            ans.appendleft(S[tmp[0]])
        print(''.join(ans))

if __name__ == '__main__':
    main()

Solution (Python):
s=input()
t=input()

n=len(s)
m=len(t)

dp=[[0 for i in range(m+1)] for i in range(n+1)]

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])

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:
  m-=1
  n-=1
  ans=s[n]+ans

print(ans)

Solution (Python):
s=input()
t=input()

n=len(s)+1
m=len(t)+1

dp=[[0 for i in range(m)] for i in range(n)]

for i in range(n-1):
 for j in range(m-1):

  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])



n-=1
m-=1

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:
  m-=1
  n-=1
  ans=s[n]+ans

print(ans)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    
    S = Scanner.string()
    T = Scanner.string()
    dp = [[0 for _ in range(3100)] for _ in range(3100)]
    for i in range(len(S)):
        for j in range(len(T)):
            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])
            if S[i] == T[j]:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
    ans = ""
    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 = S[i-1] + ans
            i -= 1
            j -= 1
    print(ans)
    return


if __name__ == "__main__":
    main()

Solution (Python):
s = input()
t = input()
S = len(s)
T = len(t)
dp=[[-1]*(T+1) for _ in range(S+1)]

for i in range(S+1):
    for j in range(T+1):
        if i==0 or j==0:
            dp[i][j] = 0


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=""
i=S
j=T
while  dp[i][j]!=0:
    if s[i-1]==t[j-1]:
        ans = s[i-1]+ans
        i-=1
        j-=1
    else:
        if dp[i][j]==dp[i-1][j]:
            i-=1
        else:
            j-=1

print(ans)

Solution (Python):
def main():
    s = input()
    t = input()
    dp = [[0]*(len(s)+1) for _ in range((len(t)+1))]
    ans = ""
    for i in range(len(t)):
        for j in range(len(s)):
            tmp1 = dp[i+1][j]
            tmp2 = dp[i][j+1]
            tmp3 = dp[i][j]
            if t[i] == s[j]:
                tmp3 += 1
            dp[i+1][j+1] = max(tmp1,tmp2,tmp3)
    i = len(t)
    j = len(s)
    while i > 0 and j > 0:
        if dp[i-1][j-1]+1 == dp[i][j] and t[i-1] == s[j-1]:
            ans += t[i-1]
            i -= 1
            j -= 1
        elif dp[i-1][j] == dp[i][j]:
            i -= 1
        else:
            j -= 1
    print(ans[::-1])

if __name__ == '__main__':
    main()

Solution (Python):
s = input()
t = input()
LENs = len(s)
LENt = len(t)
dp = [[0 for i in range(LENt+1)] for j in range(LENs+1)]
for i in range(LENs+1):
    for j in range(LENt+1):
        if i+1 <= LENs:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if j+1 <= LENt:
            dp[i][j+1] = max(dp[i][j+1],dp[i][j])
        if i+1 <= LENs and j+1<=LENt:
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+1

ans = ''
x = LENs
y = LENt
while True:
    if len(ans)==dp[-1][-1]:
        break
    if dp[x-1][y] ==dp[x][y]:
        x = x-1
    elif dp[x][y] == dp[x][y-1]:
        y = y-1
    elif dp[x-1][y-1]+1== dp[x][y]:
        ans =s[x-1] + ans
        x = x-1
        y = y-1
        continue



print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(200000)
s = input()
t = input()
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

def backtrack(dp, s, t, i, j):
    if i == 0 or j == 0:
        return ''
    if s[i-1] == t[j-1]:
        return backtrack(dp, s, t, i-1, j-1) + s[i-1]
    if dp[i][j-1] > dp[i-1][j]:
        return backtrack(dp, s, t, i, j-1)
    return backtrack(dp, s, t, i-1, j)

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] = max(dp[i][j], dp[i-1][j-1] + 1)
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])
print(backtrack(dp, s, t, len(s), len(t)))

Solution (Python):
s = input()
t = input()

table = [[0 for j in range(len(t) + 1)] for i in range(len(s) + 1)]

for i, si in enumerate(s):
    table_pre = table[i]
    table_cur = table[i + 1]
    for j, tj in enumerate(t):
        if si == tj:
            table_cur[j + 1] = table_pre[j] + 1
        else:
            table_cur[j + 1] = max(table_cur[j], table_pre[j + 1])

ls, lt = len(s), len(t)
ans = ''
while ls and lt:
    if table[ls][lt] == table[ls][lt - 1]:
        lt -= 1
    elif table[ls][lt] == table[ls - 1][lt]:
        ls -= 1
    else:
        ans = s[ls - 1] + ans
        ls -= 1
        lt -= 1
print(ans)

Solution (Python):
INF = 10**10 - 1 
SMAX = 3000 + 10


s1 = input()
s2 = input()

'''
dpの初期化
s1の文字列位置を一次軸、s2の文字列位置を二次軸に取り
その値として：LCSの最長値として更新していく
　　　　　　　初期値はすべて０
'''
dp = [ [0] * (SMAX) for i in range(SMAX)]

for s1pos in range(1,len(s1)+1):
    s1s = s1[s1pos-1:s1pos]
    for s2pos in range(1,len(s2)+1):
        s2s = s2[s2pos-1:s2pos]
        if s1s == s2s:
            dp[s1pos][s2pos] = dp[s1pos-1][s2pos-1] + 1
        dp[s1pos][s2pos] = max(dp[s1pos][s2pos],dp[s1pos][s2pos-1],dp[s1pos-1][s2pos])
    



res = ""
s1pos = len(s1)
s2pos = len(s2)
while (s1pos > 0 and s2pos > 0):
    
    if (dp[s1pos][s2pos] == dp[s1pos-1][s2pos]):
        s1pos -= 1 
    
    elif (dp[s1pos][s2pos] == dp[s1pos][s2pos-1]):
        s2pos -= 1 
    
    else:
        res = s1[s1pos-1:s1pos] + res 
        s1pos -= 1 
        s2pos -= 1 

print(res)

Solution (Python):
s = input()
t = input()

def solve(S, T):
    L1 = len(S)
    L2 = len(T)
    dp = [[0]*(L2+1) for i in range(L1+1)]

    for i in range(L1-1, -1, -1):
        for j in range(L2-1, -1, -1):
            r = max(dp[i+1][j], dp[i][j+1])
            if S[i] == T[j]:
                r = max(r, dp[i+1][j+1] + 1)
            dp[i][j] = r

    

    
    res = []
    i = 0; j = 0
    while i < L1 and j < L2:
        if S[i] == T[j]:
            res.append(S[i])
            i += 1; j += 1
        elif dp[i][j] == dp[i+1][j]:
            i += 1
        elif dp[i][j] == dp[i][j+1]:
            j += 1
    return "".join(res)

print(solve(s,t))

Solution (Python):
s = input()
t = input()
S = len(s)
T = 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])

ans = ""
while S and T:
    if dp[S][T] == dp[S-1][T]:
        S -= 1
    elif dp[S][T] == dp[S][T-1]:
        T -= 1
    else:
        ans = s[S-1]+ans
        S -= 1
        T -= 1
print(ans)

Solution (Python):

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+1][j], dp[i][j+1])

ans = ''
n = len(S)
m = len(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:
        
        n -= 1
        m -= 1
        
        ans = S[n] + ans
print(ans)

Solution (Python):
s = input()
t = 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+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])

ans = ''
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 += s[i-1]
        i -= 1
        j -= 1

print(ans[::-1])

Solution (Python):
S=input()
T=input()
s=len(S)
t=len(T)

dp=[[0]*(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]=max(dp[i][j]+1, dp[i][j])
        else:
            dp[i+1][j+1]=max(dp[i+1][j], dp[i][j+1])
ans=''
while s>0 and t>0:
    if dp[s][t]==dp[s-1][t]:
        s-=1
    elif dp[s][t]==dp[s][t-1]:
        t-=1
    else:
        s-=1
        t-=1
        ans+=T[t]
ans=ans[::-1]
print(ans)

Solution (Python):
def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            if dp[i+k]>dp[i]+abs(H[i+k]-H[i]):
                dp[i+k] = dp[i]+abs(H[i+k]-H[i])
    ans = dp[-1]
    print(ans)
    return

def examC():
    N = I()
    A = [0]*N; B = [0]*N; C = [0]*N
    for i in range(N):
        A[i],B[i],C[i] = LI()
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + A[i]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
    ans = max(dp[N])
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    
    
    def maxBy(f, x, y):
        if f(x) > f(y):
            return x
        else:
            return y
    def lcs(xs, ys, table):
        if (xs, ys) in table:
            return table[(xs, ys)]
        ret = ""
        if xs == "" or ys == "":
            ret = ""
        elif xs[-1] == ys[-1]:
            ret = lcs(xs[:-1], ys[:-1], table) + xs[-1]
        else:
            ret = maxBy(len,
                        lcs(xs[:-1], ys, table),
                        lcs(xs, ys[:-1], table))
        table[(xs, ys)] = ret
        return ret

    S = SI(); N = len(S)
    T = SI(); M = len(T)

    dp = [[0] * (M + 1) for _ in range(N + 1)]
    ans = []

    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][j+1])

    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.append(S[i-1])
            i -= 1
            j -= 1
    print("".join(ans[::-1]))
    return

def examG():

    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""

"""

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


def main():
    s = S()
    t = S()
    s_len = len(s)
    t_len = len(t)
    dp = [[0] * (t_len+1) for i in range(s_len+1)]
    ans = []

    for i in range(s_len):
        for j in range(t_len):
            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])

    
    i = s_len
    j = t_len
    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(''.join(ans[::-1]))

if __name__ == '__main__':
    main()

Solution (Python):
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(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])


lcs_str = ''
i, j = len_s-1, len_t-1
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        lcs_str += s[i]
        i -= 1
        j -= 1
    else:
        if dp[i][j+1] > dp[i+1][j]:
            i -= 1
        else:
            j -= 1
print(lcs_str[::-1])

Solution (Python):

s = input()
t = input()
dp = [[0]*(1+len(t)) for _ in range(1+len(s))]
def match(s_,t_,i,j):
    if s_[i] == t_[j]:
        return 1
    else: return 0




traceback =[[-1]*(1+len(t)) for _ in range(1+len(s))]
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
            traceback[i+1][j+1] = 3
        elif dp[i][j+1] >= dp[i+1][j]:
            dp[i+1][j+1] = dp[i][j+1]
            traceback[i+1][j+1] = 1
        else:
            dp[i+1][j+1] = dp[i+1][j]
            traceback[i+1][j+1] = 2
        




x,y = len(s),len(t)
"""for i in range(1+len(s)):
    
    print(traceback[i])
"""
output = []
while True:
    if traceback[x][y] == 3:
        output.append(s[x-1])
        
    x_ = x
    y_ = y
    x -= traceback[x_][y_] % 2 
    y -= traceback[x_][y_] // 2
    
    if x == 1 and y == 1:
        if traceback[x][y] == 3:
            output.append(s[x-1])
        break
    if x == 0 or y == 0:
        break
for i in range(len(output)-1,-1,-1):
    print(output[i],end="")
print()

Solution (Python):
s = input()
t = input()

dp = [[0] * (len(s) + 1) for _ in range(len(t) + 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[j][i] = max(dp[j][i-1], dp[j-1][i], dp[j-1][i-1] + 1)
    else:
      dp[j][i] = max(dp[j][i-1], dp[j-1][i], dp[j-1][i-1])

ans = ""
x = len(s)
y = len(t)
d = dp[-1][-1]
while True:
  if d == 0:
    break
  if dp[y - 1][x] == d:
    y -= 1
  elif dp[y][x - 1] == d:
    x -= 1
  else:
    ans += t[y - 1]
    x -= 1
    y -= 1
    d -= 1
print(ans[::-1])

Solution (Python):
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])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

s=ss()
t=ss()
def lcs(str1, str2):
    '''文字列str1, str2の最長共通部分列(Lowest Common Subsequence, LCS)を求める
    計算量O(len(str1)*len(str2))  
    '''
    dp = [[0]*(len(str2) + 1) for _ in range(len(str1) + 1)]
    for i in range(len(str1)):
        for j in range(len(str2)):
            if str1[i] == str2[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])
 
    '''復元を実行
    最長の長さを求めるなら return dp[len(str1)][len(str2)] をするとよい
    '''
    res = ''
    i, j = len(str1), len(str2)
    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 = str1[i-1] + res
            i -= 1
            j -= 1
    return res
print(lcs(s,t))

Solution (Python):

import numpy as np
S = np.array([ord(i)-97 for i in input()], dtype=int)
T = np.array([ord(i)-97 for i in input()], dtype=int)
Ns = len(S)
Nt = len(T)
equal = np.equal.outer(S, T).astype(int)

dp = [np.zeros(Nt + 1, dtype=int)]
for i in range(Ns):
    x = dp[-1].copy()
    newDP = x.copy()
    newDP[1:] = np.maximum(x[:-1] + equal[i], newDP[1:])
    np.maximum.accumulate(newDP, out=newDP)
    dp.append(newDP)


ans = ""
i, j = Ns, Nt
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans += chr(S[i-1]+97)
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1

print(ans[::-1])

Solution (Python):


s=input()
t=input()

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=""
i=ls
j=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:
        i-=1
        j-=1
        ans+=s[i]
        


print(ans[::-1])

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(input()) 
def ifn(): return float(input()) 
def isn(): return input().split() 
def imn(): return map(int, input().split()) 
def fmn(): return map(float, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, input().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def add_mod(a,b): return (a+b) % MOD

s = input()
t = input()

sl =len(s)
tl =len(t)

dp = [[0 for _ in range(tl+1)] for _ in range(sl+1)]


for i in range(sl):
    for j in range(tl):
        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])
ans = ''
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] + ans
        sl -= 1
        tl -= 1
print(ans)