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):
x = input()
y = input()
lx = len(x)
ly = len(y)

chars = [[''] * (ly + 1) for _ in range(lx + 1)]
length = [[0] * (ly + 1) for _ in range(lx + 1)]
prev = [[0b00] * (ly + 1) for _ in range(lx + 1)]

for i_x in range(lx):
    for i_y in range(ly):
        if x[i_x] == y[i_y]:
            length[i_x+1][i_y+1] = length[i_x][i_y] + 1
            chars[i_x+1][i_y+1] = x[i_x]
            prev[i_x+1][i_y+1] = 0b11
        elif length[i_x+1][i_y] > length[i_x][i_y+1]:
            length[i_x+1][i_y+1] = length[i_x+1][i_y]
            prev[i_x+1][i_y+1] = 0b01
        else:
            length[i_x+1][i_y+1] = length[i_x][i_y+1]
            prev[i_x+1][i_y+1] = 0b10

lcs = [''] * length[-1][-1]
i_x, i_y = lx, ly
i = 1
while i_x and i_y:
    if prev[i_x][i_y] == 0b11:
        lcs[-i] = chars[i_x][i_y]
        i += 1
    i_x, i_y = i_x - ((prev[i_x][i_y] & 0b10) >> 1), i_y - (prev[i_x][i_y] & 0b01)

print(''.join(lcs))

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

Solution (Python):
s = input()
t = input()
s_num = len(s)
t_num = len(t)
dp = [[0] * (t_num + 1) for _ in range(s_num + 1)]

for i in range(s_num):
    for j in range(t_num):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i][j] + 1, dp[i + 1][j], dp[i][j + 1])
        else:
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
ans = ""
i = s_num
j = t_num
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)

Solution (Python):
sList, tList = list(input()), list(input())

dp = [[0] * (len(tList) + 1) for _ in range(len(sList) + 1)]
for i, s in enumerate(sList, start=1):
    sameNum = 0
    for j, t in enumerate(tList, start=1):
        num = dp[i-1][j]
        if s == t:
            sameNum = max(num, dp[i-1][j-1] + 1)
        dp[i][j] = max(num, sameNum)

ans = ""

while(i > 0, j > 0):
    num = dp[i][j]
    if num == 0:
        break
    if sList[i-1] == tList[j-1]:
        ans = sList[i-1] + ans
        i -= 1
        j -= 1
    else:
        if dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1

print(ans)

Solution (Python):

sList, tList = input(), input()

dp = [[0] * (len(tList) + 1) for _ in range(len(sList)+1)]



for i, s in enumerate(sList, start=1):
    for j, t in enumerate(tList, start=1):
        dp[i][j] = max([dp[i][j - 1], dp[i-1][j],
                        dp[i-1][j-1] + 1 if s == t else 0])
m = dp[i][j]
ans = ""

cnt = 0
while i + j != 0:
    if dp[i - 1][j - 1] == m - 1 and tList[j-1] == sList[i-1]:
        ans = tList[j-1] + ans
        i -= 1
        j -= 1
        m -= 1
    else:
        if dp[i - 1][j] == m:
            i -= 1
        elif dp[i][j-1] == m:
            j -= 1
    cnt += 1
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 = 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] + ans
        i -=1
        j -=1

print(ans)

Solution (Python):
s, t = [input() for _ in range(2)]

dp = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]
for i, si in enumerate(s):
    for j, tj in enumerate(t):
        if si == tj:
            dp[i + 1][j + 1] = 1 + dp[i][j]
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

ans = ""
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
        ans += s[x]

print(ans[::-1])

Solution (Python):
from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

s = stdin.readline().rstrip()
t = stdin.readline().rstrip()

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



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

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


"""
print('      ', end='')
print(*t, sep=''  '')
ss = ' ' + s
for i in range(len(dp)):
    print(ss[i], end=' ')
    print(dp[i])
"""





res = ""
while s_len and t_len:
    if dp[s_len][t_len] == dp[s_len-1][t_len]:
        s_len -= 1
    elif dp[s_len][t_len] == dp[s_len][t_len-1]:
        t_len -= 1
    else:
        
        res = s[s_len-1] + res
        s_len -= 1
        t_len -= 1

print(res)

Solution (Python):
s = input()
t = input()
n,m = len(s),len(t)
dp = [[0]*(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+1][j],dp[i][j+1])
res = ''
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:
        res = s[n-1]+res
        n -= 1
        m -= 1
print(res)

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

point = [ [0 for t in range(len(T) + 1)] for _ in range(len(S) + 1)]
path = [ [0 for t in range(len(T) + 1)] for _ in range(len(S) + 1)] 


for s_index in range(len(S)):
    for t_index in range(len(T)):
        if S[s_index] == T[t_index]:
            point[s_index + 1][t_index + 1] = point[s_index][t_index] + 1
            path[s_index + 1][t_index + 1] = 1
        elif point[s_index + 1][t_index] > point[s_index][t_index + 1] :
            point[s_index + 1][t_index + 1] = point[s_index + 1][t_index]
            path[s_index + 1][t_index + 1] = 3
        else:
            point[s_index + 1][t_index + 1] = point[s_index][t_index + 1]
            path[s_index + 1][t_index + 1] = 2



last_s = len(S) 
last_t = len(T)

ret = ''
while(last_s != 0 and last_t != 0):
    if path[last_s][last_t] == 1:
        ret += S[last_s-1]
        last_s -= 1
        last_t -= 1
    elif path[last_s][last_t] == 2:
        last_s -= 1
    else:
        last_t -= 1

print(ret[::-1])

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

s = input()
t = input()

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

ansl = []
cnt = dp[-1][-1]
def tami(i,j):
  global cnt
  if cnt == 0:
    return
  if s[i-1] == t[j-1]:
    cnt -= 1
    ansl.append(i-1)
  if dp[i-1][j-1]==cnt:
    tami(i-1,j-1)
  elif dp[i][j-1]==cnt:
    tami(i,j-1)
  elif dp[i-1][j]==cnt:
    tami(i-1,j)

tami(len(s),len(t))

ans = ""
for i in ansl:
  ans += s[i]
print(ans[::-1])

Solution (Python):
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
    else:
        if dp[i-1][j] > dp[i][j-1]:
            i -=1
        else:
            j -=1
print(ans[::-1])

Solution (Python):
S=input()
T=input()
a=[ord(i) for i in S]
b=[ord(i) for i in T]
N=len(a);M=len(b)
X=[[0 for j in range(M+1)] for i in range(N+1)]
Y=[[0 for j in range(M+1)] for i in range(N+1)]
for i in range(N):
    for j in range(M):
        if a[i]==b[j]:
            X[i+1][j+1]=X[i][j]+1
            Y[i+1][j+1]=0
        elif X[i+1][j]<X[i][j+1]:
            X[i+1][j+1]=X[i][j+1]
            Y[i+1][j+1]=+1
        else:
            X[i+1][j+1]=X[i+1][j]
            Y[i+1][j+1]=-1
c=[]
i=N;j=M
while(i>0 and j>0):
    if Y[i][j]>0:
        i-=1
    elif Y[i][j]<0:
        j-=1
    else:
        c.append(a[i-1])
        i-=1
        j-=1
print("".join([chr(i) for i in c[::-1]]))

Solution (Python):
s = input()
t = input()
n, m = len(s), len(t)

T = [[0] * (m + 1) for i in range(n + 1)]
k = 0
for j in range(m):
    if s[0] == t[j]:
        k = 1
    T[0][j] = k

k = 0
for i in range(n):
    if s[i] == t[0]:
        k = 1
    T[i][0] = k

for i in range(n - 1):
    for j in range(m - 1):
        if s[i + 1] == t[j + 1]:
            T[i + 1][j + 1] = T[i][j] + 1
        else:
            T[i + 1][j + 1] = max(T[i][j + 1], T[i + 1][j])


i, j = n - 1, m - 1
ans = ''
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        ans += s[i]
        i, j = i - 1, j - 1
    else:
        if T[i - 1][j] > T[i][j - 1]:
            i -= 1
        else:
            j -= 1

print(ans[::-1])

Solution (Python):


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

    dp = [[0 for i in range(len(t) + 1)] for j in range(len(s) + 1)]
    for i, sc in enumerate(s):
        for j, tc in enumerate(t):
            if sc == tc:
                dp[i+1][j+1] = dp[i+1][j+1] if dp[i+1][j+1] > dp[i][j] + 1 else dp[i][j] + 1
            dp[i+1][j+1] = dp[i+1][j+1] if dp[i+1][j+1] > dp[i+1][j] else dp[i+1][j]
            dp[i+1][j+1] = dp[i+1][j+1] if dp[i+1][j+1] > dp[i][j+1] else 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
        else:
            ans += s[i-1]
            i -= 1
            j -= 1

    print(ans[::-1])


if __name__ == '__main__':
    main()

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

max_len = dp[-1][-1]


prev = max_len

ans = ""

i = ls
j = lt

for l in range(max_len):
    while dp[i-1][j] == max_len - l:
        i -= 1
    while dp[i][j-1] == max_len - l:
        j -= 1
    ans += s[i-1]
    i -= 1
    j -= 1
print(ans[::-1])

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

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

print(ans[::-1])

Solution (Python):
import sys

s = sys.stdin.readline().strip()
t = sys.stdin.readline().strip()

s_len = len(s)
t_len = len(t)
dp = [[0 for x in range(t_len + 1)] for y in range(s_len + 1)]


for i in range(1, s_len+1):
    for j in range(1, t_len+1):
        if t[j-1] == s[i-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_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 += s[i - 1]
        i -= 1
        j -= 1

print(ans[::-1])

Solution (Python):
import sys


input = sys.stdin.readline


S = input()
T = input()

def chmax(a, b):
    if a >= b:
        return a
    else:
        return b


def lcs(s, t):
    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)):
            if S[i] == T[j]:
                dp[i+1][j+1] = chmax(dp[i+1][j+1], dp[i][j] + 1)
            dp[i+1][j+1] = chmax(dp[i+1][j+1], dp[i+1][j])
            dp[i+1][j+1] = chmax(dp[i+1][j+1], 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
        else:
            ans += s[i-1] 
            i -= 1
            j -= 1
    
    print(ans[::-1])

        
lcs(S, T)

Solution (Python):
s=list(input())
t=list(input())
n = len(s)
m = len(t)
dp=[[0 for i in range(m+1)] for j in range(n+1)]
for i in range(n+1):
    for j in range(m+1):
        if i<n and j<m and s[i]==t[j]:
            dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j+1])
        if j<m:
            dp[i][j+1]=max(dp[i][j],dp[i][j+1])
        if i<n:
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
ans=[]
while(n>0 and m>0):
    if dp[n][m]==dp[n-1][m]:
        n-=1
        continue
    if dp[n][m]==dp[n][m-1]:
        m-=1
        continue
    ans.append(s[n-1])
    n-=1
    m-=1
print("".join(ans[::-1]))

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

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

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

for i in range(n+1):
    for j in range(m+1):
        if i < n and j < m and s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        if i < n:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j < m:
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])

i = n
j = m
ans = ''
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
        continue
    if dp[i][j] == dp[i][j-1]:
        j -= 1
        continue
    i -= 1
    j -= 1
    ans += s[i]

print(ans[::-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**8)

S = input()
T = input()

N,M = len(S),len(T)

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

for i,s in enumerate(S):
    for j,t in enumerate(T):
        if s==t:
            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 = ''
def rec(i,j):
    if i==0 or j==0: return
    if S[i-1] == T[j-1]:
        global ans
        ans += S[i-1]
        rec(i-1,j-1)
    elif dp[i-1][j] >= dp[i][j-1]:
        rec(i-1,j)
    else:
        rec(i,j-1)
rec(N,M)
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] = 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 = 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
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(3003)
def main():
    s = " "+input()
    N = len(s)-1

    t = " "+input()
    M = len(t)-1
    if N < M:
        N, M = M, N
        s, t = t, s
    
    dp = [[-1]*(M+1) for i in range(N+1)]
    dp[0] = [0]*(N+1)
    for i in range(N+1):
        dp[i][0] = 0
    for i in range(1, N+1):
        for j in range(1, M+1):
            
            if s[i] == t[j]:
                dp[i][j] = dp[i-1][j-1]+1
            elif s[i] != t[j]:
                if dp[i-1][j] > dp[i][j-1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1]
    print(get(s, t, N, M, dp))

def get(s, t, i, j, dp):
    if i == 0 or j == 0:
        return ""

    if s[i]==t[j]:
        return get(s, t, i-1, j-1, dp) + s[i]
    elif s[i] != t[j]:
        if dp[i-1][j] > dp[i][j-1]:
            return get(s, t, i-1, j, dp)
        else:
            return get(s, t, i, j-1, dp)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

s = [ord(a)-97 for a in list(sys.stdin.readline().rstrip())]
t = [ord(b)-97 for b in list(sys.stdin.readline().rstrip())]
len_s = len(s)
len_t = len(t)

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

strings = []
while len_s > 0 and len_t > 0:
    if s[len_s-1] == t[len_t-1]:
        len_s -= 1
        len_t -= 1
        strings.insert(0,chr(s[len_s]+97))
    elif dp[len_s][len_t-1] > dp[len_s-1][len_t]:
        len_t -= 1
    else:
        len_s -= 1

print("".join(strings))

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

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

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

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

dp = [[0 for _ 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] = 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 = 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 = s[i-1] + ans;
        i -= 1
        j -= 1

print(ans)

Solution (Python):
s,t=input(),input()
a,b=len(s),len(t)
DP=[[0]*(b+1) for _ in range(a+1)]
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+1][j],DP[i][j+1])
ans=''
while a and b:
    if DP[a][b]==DP[a-1][b]:
        a-=1
    elif DP[a][b]==DP[a][b-1]:
        b-=1
    else:
        ans=s[a-1]+ans
        a-=1
        b-=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] = 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 = 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
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1

print(ans)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007


def A():
    """
    N個の足場があります。足場には1,2,…,Nと番号が振られています。 
    各i (1≤i≤N) について、足場 i の高さは hi です。
    最初、足場 1 にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。
    足場 i にいるとき、足場 i+1 または i+2 へジャンプする。
    このとき、ジャンプ先の足場を j とすると、コスト |hi−hj| を支払う。
    カエルが足場 N に辿り着くまでに支払うコストの総和の最小値を求めてください。

    制約
        入力はすべて整数である。
    2≤N≤10**5
    1≤hi≤10**4
    """
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]))
    print(dp[n-1])
    return


def B():
    n, K = LI()
    h = LI()
    dp = [float("INF") for i in range(n + K + 1)]
    dp[0] = 0
    for i in range(n):
        for k in range(1, K + 1):
            if i + k >= n:
                break
            dp[i + k] = min(dp[i + k], dp[i] + abs(h[i] - h[i + k]))
    print(dp[n-1])
    return


def C():
    n = II()
    abc = LIR(n)
    dp = [0 for i in range(3 * n + 1)]
    dp[0] = abc[0][0]
    dp[1] = abc[0][1]
    dp[2] = abc[0][2]
    for i in range(1,n):
        dp[3 * i] = max(dp[3 * i], dp[3 * (i - 1) + 1] + abc[i][0], dp[3 * (i - 1) + 2] + abc[i][0])
        dp[3 * i + 1] = max(dp[3 * i + 1], dp[3 * (i - 1) + 2] + abc[i][1], dp[3 * (i - 1)] + abc[i][1])
        dp[3 * i + 2] = max(dp[3 * i + 2], dp[3 * (i - 1) + 1] + abc[i][2], dp[3 * (i - 1)] + abc[i][2])
    dp[3 * n] = max(dp)
    print(dp[3*n])

    return


def D():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**5
    1≤wi≤W
    1≤vi≤10**9"""
    n, w = LI()
    wv = LIR(n)
    dp = [[0 for k in range(w + 1)] for i in range(n + 2)]
    for i in range(1,n + 1):
        for j in range(w + 1):
            if j < wv[i-1][0]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i - 1][0]] + wv[i - 1][1])
    print(dp[n+1][w])

    
    return


def E():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**9
    1≤wi≤W
    1≤vi≤10**3"""
    n, w = LI()
    wv = LIR(n)
    dp = [[float("INF") for i in range(10 ** 5 + 1)] for k in range(n + 1)]
    dp[0][0] = 0
    for i in range(n):
        for k in range(10 ** 5 + 1):
            if k < wv[i][1]:
                dp[i + 1][k] = dp[i][k]
            else:
                dp[i + 1][k] = min(dp[i][k], dp[i][k - wv[i][1]] + wv[i][0])
    ans = 0
    for i in range(10 ** 5 + 1):
        if dp[n][i] <= w:
            ans = i
    print(ans)

    return


def F():
    s = S()
    t = S()
    dp = [[0 for i in range(len(t)+1)] for k 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:
                if dp[i][j + 1] < dp[i + 1][j]:
                    dp[i + 1][j + 1] = dp[i + 1][j]
                else:
                    dp[i + 1][j + 1] = dp[i][j + 1]
    ss = len(s)
    tt = len(t)
    ans = ""
    si = ss
    ti = tt
    while si > 0 and ti > 0:
        if dp[si][ti] == dp[si - 1][ti]:
            si -= 1
        elif dp[si][ti] == dp[si][ti - 1]:
            ti -= 1
        else:
            si -= 1
            ti -= 1
            ans = s[si]+ans


    print(ans)
    return


def G():
    n, m = LI()
    xy = LIR_(m)
    edge = [[] for i in range(n)]
    for x,y in xy:
        edge[x].append(y)
    dp = [0 for i in range(n)]
    def ans(dp, i):
        
        if dp[i] != 0:
            return dp[i]
        else:
            if len(edge[i]) == 0:
                return 0
            ansb = 0
            for k in edge[i]:
                
                ansb = max(ansb, ans(dp, k) + 1)
                dp[i] = max(ansb, dp[i])
                
            return ansb
            
    for i in range(n):
        dp[i] = ans(dp, i)
    print(max(dp))
    return


def H():
    h, w = LI()
    a = SR(h)
    dp = [[0 for i in range(w)] for k in range(h)]
    for i in range(w):
        if a[0][i] == "
            break
        dp[0][i] = 1
    for i in range(h):
        if a[i][0] == "
            break
        dp[i][0] = 1
    for i in range(1,w):
        for k in range(1, h):
            
            if a[k - 1][i] == ".":
                if a[k][i - 1] == ".":
                    dp[k][i] = dp[k - 1][i] + dp[k][i - 1] % mod
                else:
                    dp[k][i] = dp[k - 1][i]
            else:
                if a[k][i - 1] == ".":
                    dp[k][i] = dp[k][i - 1]
    print(dp[h-1][w-1] % mod)

    return


def I():
    n = II()
    p = LF()
    dp = [[0 for k in range(n+1)] for i in range(n+1)]
    dp[1][1] = p[0]
    dp[1][0] = 1-p[0]
    for i in range(2,n+1):
        for k in range(i + 1):
            if k == 0:
                
                dp[i][k] = dp[i-1][k] * (1 - p[i-1])
            else:
                dp[i][k] = dp[i - 1][k - 1] * p[i - 1] + dp[i - 1][k] * (1 - p[i - 1])
    
    print(sum(dp[n][n//2+1:]))
    return 

def J():
    n = II()
    a = LI()
























if __name__ == '__main__':
    F()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


def A():
    n = I()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n-2):
        dp[i+1] = min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
        dp[i+2] = min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
    dp[n-1] = min(dp[n-1],dp[n-2]+abs(h[n-1]-h[n-2]))
    print(dp[n-1])

def B():
    n,k = LI()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,min(n-i,k+1)):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
    print(dp[n-1])


def C():
    n = I()
    v = LIR(n)
    dp = [[0,0,0] for i in range(n+1)]
    for i in range(n):
        dp[i+1][0] = max(dp[i+1][0],dp[i][1]+v[i][0],dp[i][2]+v[i][0])
        dp[i+1][1] = max(dp[i+1][1],dp[i][2]+v[i][1],dp[i][0]+v[i][1])
        dp[i+1][2] = max(dp[i+1][2],dp[i][0]+v[i][2],dp[i][1]+v[i][2])
    print(max(dp[n]))


def D():
    n,W = LI()
    g = LIR(n)
    dp = [[0 for i in range(W+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(W+1)[::-1]:
            w,v = g[i]
            if j >= w:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
            else:
                dp[i+1][j] = max(dp[i+1][j],dp[i][j])
    print(max(dp[n]))

def E():
    n,W = LI()
    g = LIR(n)
    V = 100000
    dp = [[float("inf") for i in range(V+1)] for j in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(V+1)[::-1]:
            w,v = g[i]
            if j >= v:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
            else:
                dp[i+1][j] = min(dp[i+1][j],dp[i][j])

    for i in range(V+1)[::-1]:
        if dp[n][i] <= W:
            print(i)
            quit()


def F():
    s = S()
    t = S()
    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)):
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i][j]+1,dp[i+1][j],dp[i][j+1])
            else:
                dp[i+1][j+1] = max(dp[i+1][j],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:
            i -= 1
            j -= 1
            ans = s[i]+ans
    print(ans)

def G():
    n,m = LI()
    e = LIR(m)
    dp = [0 for j in range(m+1)]
    for i in range(m):
        x,y = e[i]
        dp[i+1][y] = max(dp[i][y],dp[i][x]+1)
    ans = 0
    for i in range(m+1):
        ans = max(dp[i])
    print(ans)

def H():
    return


if __name__ == "__main__":
    F()

Solution (Python):
s = input()
t = input()
dp = []
for i in range(len(s)+1):
  L = [0]*(len(t)+1)
  dp.append(L)
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])
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:
    n -= 1
    m -= 1
    ans = s[n]+ans
print(ans)

Solution (Python):

s=input()
t=input()

dp=[[0]*len(s) for i in range(len(t))]
dp[0][0]=0

for i in range(len(t)):
    for j in range(len(s)):
        if s[j]==t[i]:
            if i==0 or j==0:
                dp[i][j]=1
            else:
                dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i][j-1],dp[i-1][j])
ans=""
j=len(t)-1
i=len(s)-1

while 1:
    if j==0:
        if dp[0][i]==1:
            ans+=t[0]
        break
    if i==0:
        if dp[j][0]==1:
            ans+=s[0]
        break
    else:
        if dp[j][i]==dp[j-1][i]:
            j-=1
        elif dp[j][i]==dp[j][i-1]:
            i-=1
        else:
            ans+=t[j]
            j-=1
            i-=1
print(ans[::-1])

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

Solution (Python):
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 = s[n] + res
print(res)