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()
N,M=len(s),len(t)
dp=[[0]*(M+1) for i in range(N+1)]
dp2=[[0]*(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]=dp[i][j]+1
            dp2[i+1][j+1]=3
        elif dp[i][j+1]<dp[i+1][j]:
            dp[i+1][j+1]=dp[i+1][j]
            dp2[i+1][j+1]=1
        else:
            dp[i+1][j+1]=dp[i][j+1]
            dp2[i+1][j+1]=2
a=[]
while i>=0 and j>=0:
    if dp2[i+1][j+1]==1:
        j-=1
    elif dp2[i+1][j+1]==2:
        i-=1
    else:
        a.append(s[i])
        i-=1
        j-=1
print(*reversed(a),sep='')

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

dp = [[0 for i in range(3010)] for j in range(3010)]

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][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):
s = list(input())
t = list(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 != 0 and m != 0:
	if dp[n][m] == dp[n - 1][m]:
		n -= 1
	elif dp[n][m] == dp[n][m - 1]:
		m -= 1
	else:
		n -= 1
		m -= 1
		res.append(s[n])

print(''.join(res[::-1]))

Solution (Python):

import sys


def solve(s: str, t: str):
    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])

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

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



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  
    t = next(tokens)  
    solve(s, t)


if __name__ == '__main__':
    main()

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

for i in range(1,lent+1):
    x = t[i-1]
    for j in range(1,lens+1):
        y = s[j-1]
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        if x == y:
            dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1)

m = lent
n = lens
ans = ""
while m>0 and n>0:
    if dp[m][n] == dp[m-1][n]:
        m -= 1
        continue
    if dp[m][n] == dp[m][n-1]:
        n -= 1
        continue
    m -= 1
    n -= 1
    ans = t[m]+ans

print(ans)

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

s = ns()
t = ns()
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 + 1][j], dp[i][j + 1])

rest = []
m = 0
i, j = lenS, lenT
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        rest.append(s[i - 1])
        i -= 1
        j -= 1

print(*rest[::-1], sep="")

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

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

s = list(input())
t = list(input())
n = len(s)-1
m = len(t)-1
value = [[0]*(m+1) for i in range(n+1)]


for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
        elif value[i][j + 1] > value[i + 1][j]: 
            value[i + 1][j + 1] = value[i][j + 1]
        else:  
            value[i + 1][j + 1] = value[i + 1][j]
i = n-1
j = m-1
ans=""
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        ans = s[i] + ans
        i -= 1
        j -= 1
    elif value[i][j + 1] > value[i + 1][j]:
        i -= 1
    else:
        j -= 1
print(ans)

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

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

ans = ""
count = 0
while count != dp[-1][-1]:
    if dp[m][n] == dp[m-1][n]:
        m -= 1
    elif dp[m][n] == dp[m][n-1]:
        n -= 1
    else:
        ans += t[m-1]
        count += 1
        m -= 1
        n -= 1

print(ans[::-1])

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

print(ans[::-1])

Solution (Python):
s=str(input())
t=str(input())
n,m=len(s),len(t)
ans=''
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]=max(dp[i][j]+1,dp[i+1][j+1])
    else:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
while m>0 and n>0:
  if s[n-1]==t[m-1]:ans=s[n-1]+ans;n-=1;m-=1
  elif dp[n][m]==dp[n-1][m]:n-=1
  else:m-=1
print(ans)

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+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])
ans = ""
i = n
j = m
while i > 0 or j > 0:
    if i > 0 and dp[i][j] == dp[i-1][j]:
        i -= 1
    elif j > 0 and dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        i -= 1
        j -= 1
        ans = s[i] + ans
print(ans)

Solution (Python):

def main():
    s = input()
    t = input()
    dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
    for i, cs in enumerate(s, start=1):
        for j, ct in enumerate(t, start=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])
    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:
            i -= 1
            j -= 1
            ans = s[i] + ans

    print(ans)


if __name__ == "__main__":
    main()

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

DP=[[0 for _ in range(T+1)] for _ in range(S+1)]
for i in range(1,S+1):
    for j in range(1,T+1):
        if s[i-1]==t[j-1]:DP[i][j]=DP[i-1][j-1]+1
        else:DP[i][j]=max(DP[i-1][j],DP[i][j-1])

ans=""
x,y=S,T
while DP[x][y]!=0:
    if DP[x][y]==DP[x-1][y]:x -=1
    elif DP[x][y]==DP[x][y-1]:y -=1
    else:
        ans +=s[x-1]
        x -=1
        y -=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+1][j], dp[i][j+1])

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

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

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

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

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.append(s[n])
print(''.join(res[::-1]))

Solution (Python):
s=raw_input().strip()
t=raw_input().strip()
n=len(s)
m=len(t)
z=[[0]*(m+1) for _ in xrange(n+1)]
for i in xrange(n):
    for j in xrange(m):
        if s[i]==t[j]:
            z[i+1][j+1]=z[i][j]+1
        else:
            z[i+1][j+1]=max(z[i+1][j],z[i][j+1])
i=n-1
j=m-1
a=[]
while i>=0 and j>=0:
    if s[i]==t[j]:
        a.append(s[i])
        i-=1
        j-=1
    elif z[i][j+1]>z[i+1][j]:
        i-=1
    else:
        j-=1
print ''.join(a[::-1])

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

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

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

ans = ''
i = len(s)
j = len(t)

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

print(ans[::-1])

Solution (Python):
import numpy as np

S = np.array([ord(i) for i in input()], dtype=np.int8)
T = np.array([ord(i) for i in input()], dtype=np.int8)
LS = len(S)
LT = len(T)
equal = np.equal.outer(S, T).astype(int)

dp = [np.zeros(LT + 1, dtype=int)]
for i in range(LS):
    ndp = dp[-1].copy()
    np.maximum(ndp[:-1] + equal[i], ndp[1:], out=ndp[1:])
    np.maximum.accumulate(ndp, out=ndp)
    dp.append(ndp)


ans = []
i, j = LS, LT
while i > 0 and j > 0:
    if S[i - 1] == T[j - 1]:
        ans.append(chr(S[i - 1]))
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1
ans.reverse()
print("".join(ans))

Solution (Python):
s=list(input())
t=list(input())
dp=[[0]*(3030) for j in range(3030)]

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


answer=[]
i,j=len(s),len(t)
d=dp[i-1][j-1]
while i>=0 and j>=0:

    if dp[i-1][j]==dp[i][j]:
        i-=1
    elif dp[i][j-1]==dp[i][j]:
        j-=1
    else:
        answer.append(s[i - 1])
        i -= 1
        j -= 1
print("".join(reversed(answer)))

Solution (Python):
s=list(input())
t=list(input())
dp=[[0]*(3030) for j in range(3030)]
ans=[]
memo=-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
             if memo < i:
                 ans.append(t[j])
                 memo = i

        else:
            dp[i+1][j+1] =max(dp[i][j+1],dp[i+1][j])


answer=[]
i,j=len(s),len(t)
d=dp[i-1][j-1]
while i>=0 and j>=0:

    if dp[i-1][j]==dp[i][j]:
        i-=1
    elif dp[i][j-1]==dp[i][j]:
        j-=1
    else:
        answer.append(s[i - 1])
        i -= 1
        j -= 1
print("".join(reversed(answer)))

Solution (Python):
import numpy as np

S = np.array([ord(i) for i in input()], dtype=int)
T = np.array([ord(i) 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()
    ndp = x.copy()
    ndp[1:] = np.maximum(x[:-1] + equal[i], ndp[1:])
    np.maximum.accumulate(ndp, out=ndp)
    dp.append(ndp)


ans = []
i, j = NS, NT
while i > 0 and j > 0:
    if S[i - 1] == T[j - 1]:
        ans.append(chr(S[i - 1]))
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1
ans.reverse()
print("".join(ans))

Solution (Python):
import bisect
import collections
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = readline().rstrip()
T = readline().rstrip()
if len(S) < len(T):
    S, T = T, S


def pretty(ss):
    buf = []
    while ss is not None:
        s, ss = ss
        buf.append(s)
    buf.reverse()
    return "".join(buf)


def solve():
    index = collections.defaultdict(list)
    for i, sc in enumerate(S):
        index[sc].append(i)
    dp = [None] * len(T)
    for i, tc in enumerate(T):
        if tc not in index:
            continue
        dn = list(dp)
        ii = index[tc]
        if dn[0] is None or dn[0][0] > ii[0]:
            dn[0] = (ii[0], [chr(tc), None])
        for j in range(1, len(T)):
            if dp[j - 1] is None:
                break
            k = bisect.bisect_right(ii, dp[j - 1][0])
            if k < len(ii) and (dn[j] is None or dn[j][0] > ii[k]):
                dn[j] = (ii[k], [chr(tc), dp[j - 1][1]])
        dp = dn
    for i in range(len(T) - 1, -1, -1):
        if dp[i] is not None:
            return pretty(dp[i][1])
    return ""


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

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

Solution (Python):
s,t=input(),input()
m,n=len(s),len(t)
c=[[0]*(n+1) for _ in range(m+1)]
fro=[['']*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        if s[i-1]==t[j-1]:
            c[i][j]=c[i-1][j-1]+1
            fro[i][j]='upper_left'
        elif c[i-1][j]>=c[i][j-1]:
            c[i][j]=c[i-1][j]
            fro[i][j]='above'
        else:
            c[i][j]=c[i][j-1]
            fro[i][j]='left'
x=''
a,b=m,n
while a>0 and b>0:
    if fro[a][b]=='upper_left':
        x+=s[a-1]
        a-=1;b-=1
    elif fro[a][b]=='above':
        a-=1
    else:
        b-=1
print(x[::-1])

Solution (Python):
s = input()
t = input()
len_s = len(s)
len_t = len(t)


dp = [[0]*(len_t+1) for i in range(len_s+1)]

prevs = [[0]*(len_t+1) for i in range(len_s+1)]
prevt = [[0]*(len_t+1) for i in range(len_s+1)]
for i in range(len_s+1) :
    for j in range(len_t+1) :
        
        if i == 0 or j == 0 :
            dp[i][j] = 0
            continue
        
        if s[i-1] == t[j-1] :
            dp[i][j] = dp[i-1][j-1] + 1
            prevs[i][j] = -1
            prevt[i][j] = -1
        
        else : 
            if dp[i-1][j] >= dp[i][j-1] :
                if dp[i-1][j] > dp[i][j] :
                    dp[i][j] = dp[i-1][j]
                    prevs[i][j] = -1
            else :
                if dp[i][j-1] > dp[i][j] :
                    dp[i][j] = dp[i][j-1]
                    prevt[i][j] = -1

ans = 0
si = len_s
ti = len_t
ans = ['' for i in range(dp[len_s][len_t])]
index = dp[len_s][len_t] - 1

for i in range(10**18) :
    if prevs[si][ti] == -1 and prevt[si][ti] == -1 :
        ans[index] = s[si-1]
        index -= 1
    st = si ; tt = ti
    si += prevs[st][tt] ; ti += prevt[st][tt]
    if si == st and ti == tt :
        break

print(*ans, sep='')

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



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

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



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

print(res)

Solution (Python):
import sys
from io import StringIO
import unittest

def resolve():
    s = list(input())
    t = list(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] = 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 += 1
    j += 1

    
    while i >= 0 and j >= 0:
        if dp[i][j] == dp[i - 1][j - 1]:
            i -= 1
            j -= 1
        elif dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            ans = s[i - 1] + ans
            i -= 1
            j -= 1

    print(ans)

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """axyb
abyxb"""
        output = """axb"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """aa
xayaz"""
        output = """aa"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """a
z"""
        output = """"""
        self.assertIO(input, output)
    def test_入力例_4(self):
        input = """abracadabra
avadakedavra"""
        output = """aaadara"""
        self.assertIO(input, output)

if __name__ == "__main__":
    
    resolve()

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

maxLength = [[0 for i in range(len(s)+2)] for j in range(len(t)+2)] 

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

str = ''
i, j = len(t), len(s)

while( i > 0 and j > 0) :
	if maxLength[i][j] == maxLength[i-1][j] :
		i -= 1

	elif maxLength[i][j] == maxLength[i][j-1] :
		j -= 1

	else :
		str = s[j-1] + str 
		i -= 1
		j -= 1

print(str)

Solution (Python):
s=input()
t=input()
ns,nt=len(s),len(t)

dp=[[0]*(nt+1) for _ in range(ns+1)]

for i in range(ns):
      for j in range(nt):
            if s[i]==t[j]:
                  dp[i+1][j+1]=dp[i][j]+1
            dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j],dp[i][j+1])
lg=dp[-1][-1]
ans=[]

i,j=ns,nt
while i>0 and j>0:
      if dp[i][j]==dp[i][j-1]:
            j-=1
      elif dp[i][j]==dp[i-1][j]:
            i-=1
      else:
            i-=1
            j-=1
            ans.append(s[i])
s=''
for _ in range(lg):
      s+=ans.pop()
print(s)

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

def LCS(S, T) :
  dp = [[0 for t in range(len(T)+1)] for s in range(len(S)+1)]
  for s in range(1, len(S)+1) :
    for t in range(1, len(T)+1) : 
      if S[s-1] == T[t-1] : dp[s][t] = dp[s-1][t-1] + 1
      else : dp[s][t] = max(dp[s-1][t], dp[s][t-1])

  
  

  res = ''
  s, t = len(S), len(T)
  while s > 0 and t > 0 :
    if S[s-1] == T[t-1] : 
      res = S[s-1] + res
      s, t = s-1, t-1
    else :
      if dp[s][t-1] > dp[s-1][t] : t -= 1
      else : s -= 1
  
  print res

LCS(S, T)

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

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

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


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


ret = ['']*dp[-1][-1]
id = dp[-1][-1]
i = len(s) - 1
j = len(t) - 1
while(i >= 0 and j >= 0):
    
    if s[i] == t[j]:
        id -= 1
        ret[id] = s[i]
        i -= 1
        j -= 1
        
    else:
        if i > 0 and dp[i-1][j] >= dp[i][j-1]:
            i -= 1
        else:
            j -= 1

print(''.join(ret))

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

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

Solution (Python):
import numpy as np

s = np.array(list(input()))
t = np.array(list(input()))

equal = (s[:, None] == t[None, :])
ls, lt = len(s), len(t)
dp = np.zeros((ls + 1, lt + 1), dtype=int)

for i in range(ls):
    dp[i + 1][1:] = np.maximum(dp[i][1:], dp[i][:-1] + equal[i])
    dp[i + 1] = np.maximum.accumulate(dp[i + 1])

ans = ''
i, j = ls, lt
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        ans = s[i - 1] + ans
        i -= 1
        j -= 1
print(ans)

Solution (Python):
def main():
    from bisect import bisect_left as bl, bisect_right as br, insort
    import sys
    import heapq
    
    from collections import defaultdict as dd, deque
    def data():
        return sys.stdin.readline().strip()

    def mdata():
        return map(int, data().split())

    out = sys.stdout.write
    
    INF = int(10e9)

    s = data()
    t = data()
    dp = [[0] * (len(s) + 1) for i in range(len(t) + 1)]
    for i in range(1, len(t) + 1):
        for j in range(1, len(s) + 1):
            if s[j - 1] == t[i - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    m = max(max(dp))
    ans = ''
    for i in range(len(t) - 1, -1, -1):
        for j in range(len(s) - 1, -1, -1):
            if dp[i + 1][j + 1] == m and s[j] == t[i]:
                ans = s[j] + ans
                m -= 1
                break
    out(ans+'\n')


if __name__ == '__main__':
    main()

Solution (Python):
s = input()
t = input()
s_length = len(s)
t_length = len(t)
dp = [[0] * (s_length + 1) for i in range(t_length + 1)]
for i in range(1, t_length + 1):
    for j in range(1, s_length + 1):
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        if t[i - 1] == s[j - 1]:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + 1)
        
        
    

answer = ""

while s_length >= 0 and t_length >= 0:
    if dp[t_length][s_length] == dp[t_length - 1][s_length]:
        t_length -= 1
        continue
    elif dp[t_length][s_length] == dp[t_length][s_length-1]:
        s_length -= 1
        continue
    else:
        answer += s[s_length-1]
        s_length -= 1
        t_length -= 1

print(answer[::-1])

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

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

dp = [[0 for _ in range(lt + 1)] for __ in range(ls + 1)]

for ns in range(ls):
    for nt in range(lt):
        if s[ns] == t[nt]:
            dp[ns + 1][nt + 1] = max(dp[ns][nt] + 1, dp[ns + 1][nt + 1])
        dp[ns + 1][nt + 1] = max(dp[ns + 1][nt + 1], dp[ns + 1][nt], dp[ns][nt + 1])

ans = ''
i, j = ls, lt
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        ans = s[i - 1] + ans
        i -= 1
        j -= 1
print(ans)

Solution (Python):
from sys import stdin



def chmax(a,b):
    if a < b: return b
    else: return a


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    s =     _in[0]   
    t =     _in[1]   
    S, T = len(s), len(t)
    
    dp = [[0] * (T+1) for _ in range(S+1)]  
    
    dp[0][0] = 0  

    
    for i,_s in enumerate(s):
        for j,_t in enumerate(t):
            if _s == _t:
                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, j = S, 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):
s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0 for _ in range(ls + 1)] for _ in range(lt + 1)]
for i in range(1, lt+1):
    for j in range(1, ls+1):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        if s[j-1] == t[i-1]:
            dp[i][j] = max(dp[i-1][j-1] + 1, dp[i][j-1])
ans = ''

while ls > 0 and lt > 0:
    if dp[lt][ls] == dp[lt-1][ls]:
        lt -= 1
    elif dp[lt][ls] == dp[lt][ls-1]:
        ls -= 1
    else:
        ans += s[ls-1]
        lt -= 1
        ls -= 1

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

path=[]

lens=len(s)
lent=len(t)
while lens>-1 and lent>-1 :
    if dp[lens][lent]==dp[lens-1][lent]:
        lens-=1
    elif dp[lens][lent]==dp[lens][lent-1]:
        lent-=1
    else:
        path.append(lens)
        lens-=1
        lent-=1

path.sort()
if path==[]:
    print("")
else:
    for i in path:
    	print(s[i-1],end="")

Solution (Python):
s=list(input())
t=list(input())
x=len(s)
y=len(t)
dp=[[0]*(y+1) for i 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][j+1],dp[i+1][j])


v=dp[-1][-1]

ans=''
while x>0 and y>0:
    
    if dp[x][y]==dp[x][y-1]:
        y-=1
    
    elif dp[x][y]==dp[x-1][y]:
        x-=1
    
    else:
        x-=1
        y-=1
        ans=t[y]+ans
print(ans)

Solution (Python):
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq

from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(int, data().split())
out=sys.stdout.write

INF=int(10e9)


s=data()
t=data()
dp=[[0]*(len(s)+1) for i in range(len(t)+1)]
for i in range(1,len(t)+1):
    for j in range(1,len(s)+1):
        if s[j-1]==t[i-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
m=max(max(dp))
ans=''
for i in range(len(t)-1,-1,-1):
    for j in range(len(s)-1,-1,-1):
        if dp[i+1][j+1]==m and s[j]==t[i]:
            ans=s[j]+ans
            m-=1
            break
print(ans)