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):
s = input()
t = input()
dp = [[0 for _ in range(len(s)+1)] for _ in range(len(t) + 1)]

for i,c1 in enumerate(s,1):
    for j,c2 in enumerate(t,1):
        if c1 == c2:
            dp[j][i] = dp[j-1][i-1] + 1
        else:
            dp[j][i] = max(dp[j-1][i],dp[j][i-1])

i1,i2 = len(s),len(t)


    
        
    
        

rev_ans = ""
while i1 != 0:
    lru = dp[i2-1][i1-1]
    now = dp[i2][i1]
    dup = now - dp[i2-1][i1]
    dleft = now - dp[i2][i1-1]
    dupleft = now - lru
    
    if dupleft == 1 and dleft == 1 and dup == 1:
        rev_ans += t[i2-1]
        i2 -= 1
        i1 -= 1
    elif dleft == 1:
        i2 -= 1
    else:
        i1 -= 1

for c in reversed(rev_ans):
    print(c,end='')

Solution (Python):
def make_lcs(a,b):
    a_size = len(a)
    b_size = len(b)
    lcs = [[0 for _ in range(a_size+1)] for _ in range(b_size+1)]
    for i in range(1,b_size+1):
        for j in range(1,a_size+1):
            if a[j-1] == b[i-1]:
                match = 1
            else:
                match = 0
            lcs[i][j] = max(lcs[i-1][j-1]+match, lcs[i-1][j], lcs[i][j-1])
    

    
    res = ''
    i,j = b_size,a_size
    while((i>0) & (j>0)):
        if lcs[i][j] == lcs[i-1][j]:
            i -= 1
        elif lcs[i][j] == lcs[i][j-1]:
            j -= 1
        else:
            res = b[i-1] + res
            i -= 1
            j -= 1
    return res

def main():
    a = list(input())
    b = list(input())
    print(make_lcs(a,b))

if __name__ == "__main__":
    main()

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

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

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

Solution (Python):
s = input()
t = input()
ls, lt = len(s), len(t)

ans = ''
dp = [[0]*(lt+1) for _ in range(ls+1)]
for j in range(ls):
    for i in range(lt):
        if s[j]==t[i]:
            dp[j+1][i+1] = dp[j][i]+1
        else:
            dp[j+1][i+1] = max(dp[j+1][i], dp[j][i+1])

if dp[ls][lt] == 0:
    print('')
    exit()

i = lt
j = ls

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

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

Solution (Python):




'''
axyb
abyxb
'''

import sys

sys.setrecursionlimit(4000)
S = input()
T = input()

lcs = [[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]:
            x = 1
        else:
            x = 0
        lcs[i][j] = max(lcs[i - 1][j - 1] + x, lcs[i - 1][j], lcs[i][j - 1])




def print_lcs (S, T, lcs, i, j):
    global ans
    if (i == 0 or j == 0):
        return
    if (S[i - 1] == T[j - 1]):
        print_lcs(S, T, lcs, i - 1, j - 1)
        ans.append(S[i - 1])
    else:
        if lcs[i-1][j] >= lcs[i][j-1]:
            print_lcs(S, T, lcs, i - 1, j)
        else:
            print_lcs(S, T, lcs, i, j - 1)


ans = []
print_lcs(S, T, lcs, len(S), len(T))
print("".join(ans))

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

dp = [[0 for _ in range(len(t)+1)] for __ in range(len(s)+1)]

for i_s in range(1, len(s)+1):
    for i_t in range(1, len(t)+1):
        if s[i_s-1] == t[i_t-1]:
            dp[i_s][i_t] = dp[i_s-1][i_t-1] + 1
        else:
            dp[i_s][i_t] = max(dp[i_s][i_t-1], dp[i_s-1][i_t])

ans = []

i_s = len(s)
i_t = len(t)

while i_s > 0 and i_t > 0:
    if dp[i_s][i_t] == dp[i_s][i_t-1]:
        i_t -= 1
    elif dp[i_s][i_t] == dp[i_s-1][i_t]:
        i_s -= 1
    else:
        ans.append(s[i_s-1])
        i_s -= 1
        i_t -= 1

print("".join(reversed(ans)))

Solution (Python):
def get_lcs_table(s1, s2):
    l1, l2 = len(s1)+1, len(s2)+1
    dp = [[0]*l2 for _ in range(l1)]
    for i in range(l1):
        for j in range(l2):
            dp[i][j] = 0 if i==0 or j==0 else dp[i-1][j-1]+1 if s1[i-1]==s2[j-1] else max(dp[i][j-1], dp[i-1][j])
    return dp


def restore_lcs(s1, s2, dp):
    x, y = len(s1), len(s2)
    l = []
    while x and y:
        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
            l.append(s1[x])
    return "".join(l[::-1])


if __name__ == "__main__":
    s = input()
    t = input()
    dp = get_lcs_table(s, t)
    print(restore_lcs(s, t, dp))

Solution (Python):
def solve(s, t):
    n, m = len(s), len(t)
    dp = [[0] * (m+1) for _ in range(n+1)]
    s, t = ' ' + s, ' ' + t

    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
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    cur = dp[n][m]
    ans = ''
    while n > 0 and m > 0:
        if s[n] == t[m]:
            ans += s[n]
            cur, n, m = cur-1, n-1, m-1
        elif dp[n-1][m] == cur:
            n -= 1
        else:
            m -=1

    return ans[::-1]


def main():
    s = input()
    t = input()
    print(solve(s, t))


if __name__ == '__main__':
    main()

Solution (Python):
s = input()
t = input()
n = len(s)
m = len(t)
LCS = [[0 for _ in range(m+1)] for j in range(n+1)]

for i in range(n+1):
    for j in range(m+1):
        if i==0 or j==0:
            LCS[i][j] = 0
        elif s[i-1] == t[j-1]:
            LCS[i][j] = 1+ LCS[i-1][j-1]
        else:
            LCS[i][j] = max(LCS[i-1][j],LCS[i][j-1])
i = n
j = m
st = []
while i>0 and j>0:
    if s[i-1]==t[j-1]:
        st.append(s[i-1])
        i-=1
        j-=1
    elif LCS[i][j-1]>LCS[i-1][j]:
        j-=1
    else:
        i-=1
ans = st[::-1]
a = ''.join(ans)
print(a)

Solution (Python):
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]




S = input()
T = input()
ls = len(S)+1
lt = len(T)+1
dp = dp2(0, ls, lt)



for i in range(1, lt):
    for j in range(1, ls):
        if S[j-1]==T[i-1]:
            dp[i][j] = dp[i-1][j-1]+1
            
        else:
            if dp[i-1][j] >= dp[i][j-1]:
                dp[i][j] = dp[i-1][j]
                
            else:
                dp[i][j] = dp[i][j-1]
                


ans = ''
i = lt-1
j = ls-1
while i > 0 and j > 0:
    if dp[i][j] > dp[i-1][j-1] and S[j-1]==T[i-1]:
        ans += S[j-1]
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1

print(ans[::-1])

Solution (Python):
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



S = input()
T = input()
ls = len(S)+1
lt = len(T)+1

dp = dp2(0, ls, lt)



for i in range(1, lt):
    for j in range(1, ls):
        if S[j-1]==T[i-1]:
            dp[i][j] = dp[i-1][j-1]+1
            
        else:
            if dp[i-1][j] >= dp[i][j-1]:
                dp[i][j] = dp[i-1][j]
                
            else:
                dp[i][j] = dp[i][j-1]
                


ans = ''
i = lt-1
j = ls-1
while i > 0 and j > 0:
    if dp[i][j] > dp[i-1][j-1] and S[j-1]==T[i-1]:
        ans += S[j-1]
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1

print(ans[::-1])

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

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

    slen = len(s)
    tlen = len(t)
    dp = [[0 for _ in range(tlen + 1)] for _ in range(slen + 1)]

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

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

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

    slen = len(s)
    tlen = len(t)
    dp = [[0 for _ in range(tlen + 1)] for _ in range(slen + 1)]

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

    ans = []
    while slen > 0 and tlen > 0:
        if dp[slen][tlen] == dp[slen - 1][tlen]:
            slen -= 1
        elif dp[slen][tlen] == dp[slen][tlen - 1]:
            tlen -= 1
        else:
            slen -= 1
            tlen -= 1
            ans.append(s[slen])
    print(*ans[::-1], sep='')

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

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

    slen = len(s)
    tlen = len(t)
    dp = [[0 for _ in range(tlen + 1)] for _ in range(slen + 1)]

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

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

if __name__ == '__main__':
    main()

Solution (Python):
s = list(input())
t = list(input())
ls = len(s)
lt = len(t)
ans = []
dp = [[0] * (lt+1) for i in range(ls+1)]
for i in range(ls):
    flag = True
    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][j+1],dp[i+1][j])
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.append(s[i])
print(''.join(reversed(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][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.append(s[i])


print("".join(ans[::-1]))

Solution (Python):
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):
    s = S[i-1]
    for j in range(1,lenT+1):
        t = T[j-1]
        if s==t:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+1)
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])

"""
復元
"""
res = ''
n = lenS
m = lenT
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)

Solution (Python):


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 s[i-1]==t[j-1]:
        ans=s[i-1]+ans
        i-=1
        j-=1
    elif dp[i][j]==dp[i-1][j]:
        i-=1
    else:
        j-=1  
print(ans)

Solution (Python):

s = input()
t = input()


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

for i in range(n):
    for j in range(m):
        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 = ""
while m > 0 and n > 0:
    if dp[n][m] == dp[n-1][m]:
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    elif dp[n][m] == dp[n-1][m-1] + 1:
        ans += t[n-1]
        n -= 1
        m -= 1

print(ans[::-1])

Solution (Python):

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)

Solution (Python):
import numpy as np

t = np.array(list(input()), dtype='U1')
s = np.array(list(input()), dtype='U1')

ls = len(s)
lt = len(t)

eq = s[:, None] == t[None, :]
dp = [np.zeros(lt+1, dtype=np.int16)]


for i in range(ls):
    prev = dp[-1].copy()
    np.maximum(prev[1:], prev[:-1] + eq[i], out = prev[1:])
    np.maximum.accumulate(prev, out = prev)
    dp.append(prev)




l = dp[-1][-1]
res = ''
i, j = ls, lt
while i > 0 and j > 0:
    if eq[i-1][j-1]:
        res += s[i-1]
        i, j = i-1, j-1
        continue
    
    if dp[i-1][j] > dp[i][j-1]:
        i -= 1
    else:
        j -= 1

print(res[::-1])

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

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

for i in range(1, 1+len(S)):
    for j in range(1, 1 + len(T)):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1]
                       [j-1] + (S[i-1] == T[j-1]))




length = dp[-1][-1]
ans = ''
i = len(S)
j = len(T)
while length > 0:
    if S[i-1] == T[j-1]:
        ans = S[i-1] + ans
        i -= 1
        j -= 1
        length -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1

print(ans)

Solution (Python):
def main():
    s = input()
    t = input()
    ls,lt = len(s),len(t)
    
    dp = [[0 for _ in range(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][j+1],dp[i+1][j])

    i += 1;j += 1
    ans = ""
    k = dp[-1][-1]
    while k:
        if dp[i-1][j] == k:
            i -= 1
        elif dp[i][j-1] == k:
            j -= 1
        else:
            k -= 1
            i -= 1
            j -= 1
            ans += s[i]
    
    print(ans[::-1])
    
if __name__ == "__main__":
    main()

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

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().strip()
t = input().strip()

dp = [[0 for _ in range(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])

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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

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

Solution (Python):
s = input()
t = input()
len_s, len_t = len(s), len(t)
dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
for index_s in range(len_s):
  char_s = s[index_s]
  dp_s = dp[index_s]
  dp_ss = dp[index_s + 1]
  for index_t in range(len_t):
    if char_s == t[index_t]:
      dp_ss[index_t + 1] = dp_s[index_t] + 1
    else:
      dp_ss[index_t + 1] = max(dp_s[index_t + 1], dp_ss[index_t])
index_s, index_t = len_s - 1, len_t - 1
lcs_reverse = []
len_lcs = dp_ss[-1]
while len_lcs > 0:
  if s[index_s] == t[index_t]:
    lcs_reverse.append(s[index_s])
    index_s -= 1
    index_t -= 1
    len_lcs -= 1
  elif dp[index_s][index_t + 1] == len_lcs:
    index_s -= 1
  else:
    index_t -= 1
print(''.join(lcs_reverse[::-1]))

Solution (Python):


def lcs(X , Y): 
	
	m = len(X) 
	n = len(Y) 

	
	L = [[None]*(n+1) for i in range(m+1)] 

	"""Following steps build L[m+1][n+1] in bottom up fashion 
	Note: L[i][j] contains length of LCS of X[0..i-1] 
	and Y[0..j-1]"""
	for i in range(m+1): 
		for j in range(n+1): 
			if i == 0 or j == 0 : 
				L[i][j] = 0
			elif X[i-1] == Y[j-1]: 
				L[i][j] = L[i-1][j-1]+1
			else: 
				L[i][j] = max(L[i-1][j] , L[i][j-1]) 

	
	idx = L[m][n]
	ans = [''] * (idx+1)
	ans[idx] = ""

	i, j = m, n
	while i> 0 and j >0:
		if X[i-1] == Y[j-1]:
			ans[idx-1] = X[i-1]
			i-=1
			j-=1
			idx-=1
		elif L[i-1][j] > L[i][j-1]:
			i-=1
		else:
			j-=1

	return "".join(ans)



X = input()
Y = input()

print (lcs(X, Y))

Solution (Python):

from io import StringIO


def get_lcs(str_1: str, str_2: str) -> str:
    dp = [[0] * (len(str_2) + 1) for _ in range(len(str_1) + 1)]
    for i, s in enumerate(str_1):
        for j, t in enumerate(str_2):
            if s == t:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

    i, j = len(str_1), len(str_2)
    buf = StringIO()
    while i and j:
        if str_1[i - 1] == str_2[j - 1]:
            i -= 1
            j -= 1
            buf.write(str_1[i])
            continue
        if dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    buf.seek(0)
    return buf.read()[::-1]


def main():
    S, T = open(0).read().split()
    print(get_lcs(S, T))


if __name__ == "__main__":
    main()

Solution (Python):

def get_lcs(str_1: str, str_2: str):
    dp = [[0] * (len(str_2) + 1) for _ in range(len(str_1) + 1)]
    for i, s in enumerate(str_1):
        for j, t in enumerate(str_2):
            if s == t:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

    i, j = len(str_1), len(str_2)
    reversed_lcs = ""
    while i and j:
        if str_1[i - 1] == str_2[j - 1]:
            i -= 1
            j -= 1
            reversed_lcs += str_1[i]
            continue
        if dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return reversed_lcs[::-1]


def main():
    S, T = open(0).read().split()
    print(get_lcs(S, T))


if __name__ == "__main__":
    main()

Solution (Python):
def get_lcs(S: str, T: str):
    N, M = len(S), len(T)
    dp = [[0] * (M + 1) for _ 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 + 1][j], dp[i][j + 1])

    reversed_lcs = ""
    while N and M:
        if S[N - 1] == T[M - 1]:
            N -= 1
            M -= 1
            reversed_lcs += S[N]
            continue
        if dp[N - 1][M] > dp[N][M - 1]:
            N -= 1
        else:
            M -= 1
    return reversed_lcs[::-1]


def main():
    S, T = open(0).read().split()
    print(get_lcs(S, T))


if __name__ == "__main__":
    main()

Solution (Python):

def lcs(S: str, T: str) -> str:
    
    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] = max(dp[i][j], dp[i - 1][j - 1] + 1)
            else:
                dp[i][j] = max(dp[i][j], dp[i - 1][j], dp[i][j - 1])

    res = ""
    i, j = len(S) - 1, len(T) - 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
        elif dp[i][j] == dp[i - 1][j - 1] + 1:
            res += S[i]
            i -= 1
            j -= 1
    return res[::-1]  


def main():
    S, T = open(0).read().split()
    print(lcs(S, T))


if __name__ == "__main__":
    main()

Solution (Python):


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

    
    
    
    
    

    dp = [[0 for _ in range(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])
    
    
    i = len(s)
    j = len(t)
    ans = ""
    while dp[i][j]:
        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)


submit()

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

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


    check = 0
    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:
            ans = s[i-1] + ans
            i -= 1
            j -= 1
    print(ans)        
if __name__ == "__main__":
    main()

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

slen = len(s)
tlen = len(t)

s = " " + s
t = " " + t

dp = [ [0]*(tlen+1) for _ in range(slen+1) ]

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

anslen = dp[slen][tlen]
i = slen
j = tlen
ans = []

while anslen>0:
    if s[i]==t[j]:
        ans.append(s[i])
        i -= 1
        j -= 1
        anslen -= 1
    else:
        if dp[i][j]==dp[i-1][j]:
            i -= 1
        else:
            j -= 1

ans = "".join(ans)
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])

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]
        i -= 1
        j -= 1

ans = ans[::-1]
print("".join(ans))

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



while ns>-1 and nt>-1:
    
    if s[ns]==t[nt]:
        ans.append(s[ns])
        ns-=1
        nt-=1
    elif dp[ns][nt]==dp[ns+1][nt]:
        ns-=1
    else:
        nt-=1

print("".join(ans[::-1]))

Solution (Python):
s = list(input())
t = list(input())
dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
for j in range(1,len(t)+1):
    for i in range(1,len(s)+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 = []
p = len(s)
q = len(t)
len = dp[p][q]
while len > 0:
    if s[p-1] == t[q-1]:
        ans.append(s[p-1])
        len -= 1
        p -= 1
        q -= 1
    elif dp[p][q] == dp[p-1][q]:
        p -= 1
    else:
        q -= 1
an = ''.join(ans[::-1])
print(an)

Solution (Python):
def main():
  s = input()
  t = input()
  sn, tn = len(s), len(t)
  dp = [[0]*(tn+1) for _ in range(sn+1)]
  for i, si in enumerate(s):
    di, di2 = dp[i], dp[i+1]
    for j, ti in enumerate(t):
      if si == ti:
        di2[j+1] = di[j] + 1
      else:
          if di[j+1] > di[j]:
              di2[j+1] = di[j+1]
          else:
              di2[j+1] = di2[j]
    dp[i+1] = di2
  ans = ""
  while sn and tn:
    di = dp[sn][tn]
    if di == dp[sn][tn-1]:
      tn -= 1
    elif di == dp[sn-1][tn]:
      sn -= 1
    else:
      tn -= 1
      sn -= 1
      ans += s[sn]
      
  print(ans[::-1])

if __name__ == "__main__":
  main()

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

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

for i in range(x):
    for j in range(y):
        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 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:
        res = s[x-1] + res
        x -= 1
        y -= 1
print(res)

Solution (Python):
def lcs(S,T):
    m = len(S)
    n = len(T)
    dp = [[0]*(n+1) for x 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
            else:
                dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])


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

S = input()
T = input()
print(lcs(S,T))

Solution (Python):
from subprocess import*
call(('pypy3','-c',"""
s=input()
t=input()
a=len(s)
b=len(t)
dp=[[0]*(b+1) for i 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][j+1],dp[i+1][j])
res=''
while a!=0 and b!=0:
  if dp[a][b]==dp[a-1][b]:
    a-=1
  elif dp[a][b]==dp[a][b-1]:
    b-=1
  else:
    a-=1
    b-=1
    res=s[a]+res
print(res)
"""))

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