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

Solution (Python):
def main():

    s = str(input())
    t = str(input())

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

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

    i = len(s)
    j = len(t)
    ans = []
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans.append(s[i-1])
            i -= 1
            j -= 1
    ans.reverse()
    print(''.join(ans))

if __name__ == '__main__':
    main()

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

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

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

i = len(s)
j = len(t)
ans = []
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans.append(s[i-1])
        i -= 1
        j -= 1
ans.reverse()
print(''.join(ans))

Solution (Python):
string1 = input()
string2 = input()

dp = [[0 for i in range(len(string1) + 1)] for j in range(len(string2) + 1)]
substring = ""
for i in range(len(string2) + 1):
    for j in range(len(string1) + 1):
        if i == 0 or j == 0:
            dp[i][j] = 0
        elif string2[i - 1] == string1[j - 1]:
            dp[i][j] = 1 + dp[i - 1][j - 1]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

def recon(dp, string1, string2):
    string = ""
    i, j = len(dp) - 1, len(dp[0]) - 1
    while i != 0 and j != 0:
        if dp[i][j] > max(dp[i - 1][j], dp[i][j - 1]):
            string += string2[i - 1]
            i -= 1
            j -= 1
        else:
            if dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1

    return string

print(recon(dp, string1, string2)[::-1])

Solution (Python):
s=input()
t=input()
S,T=len(s),len(t)
dp=[[0]*(T+1) for _ in range(S+1)]
for i in range(S):
    for j in range(T):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])

l=dp[S][T]
x,y=S,T
ans=[0]*l
while l>0:
    if s[x-1]==t[y-1]:
        ans[l-1]=s[x-1]
        l-=1
        x-=1
        y-=1
    else:
        if dp[x][y]==dp[x-1][y]:x-=1
        else:y-=1
print("".join(ans))

Solution (Python):

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

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



if __name__ == '__main__':
    main()

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

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

len=dp[S][T]
x,y=S-1,T-1
ans=[0]*len
while len>0:
    if s[x]==t[y]:
        ans[len-1]=s[x]
        x-=1
        y-=1
        len-=1
    else:
        if dp[x+1][y+1]==dp[x][y+1]: x-=1
        else: y-=1

print("".join(ans))

Solution (Python):






S = input()
T = input()

ls = len(S)
lt = len(T)

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

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

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

print(ans)

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

    len_s = len(s)
    len_t = len(t)

    
    dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
    for i in range(1, len_s + 1):
        for j in range(1, len_t + 1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    i, j = len_s, len_t
    ans = ''
    while dp[i][j] > 0:
        while dp[i-1][j] == dp[i][j]:
            i -= 1
        while dp[i][j-1] == dp[i][j]:
            j -= 1

        ans += s[i-1]
        i -= 1
        j -= 1

    print(ans[::-1])

main()

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

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

ans = ''
x = len(t)
y = len(s)
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:
        ans += s[y-1]
        x -= 1
        y -= 1
print(ans[::-1])

Solution (Python):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():


    s = "
    t = "

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

    for i in range(len(t)-1):
        for j in range(len(s)-1):
            if t[i+1] == s[j+1]:
                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 = ""
    now = dp[len(t)-1][len(s)-1]
    zahyo = [len(t)-1, len(s)-1]
    while now != 0:
        while dp[zahyo[0]][zahyo[1]-1]==now:
            zahyo[1]-=1
        while dp[zahyo[0]-1][zahyo[1]]==now:
            zahyo[0]-=1

        ans += t[zahyo[0]]

        now -= 1
        zahyo = [zahyo[0]-1, zahyo[1]-1]

    ans = ans[::-1]

    print(ans)

main()

Solution (Python):
s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0] * (tlen+1) for i in range(slen+1)]
for i in range(slen):
    for j in range(tlen):
        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])
stlen = dp[slen][tlen]
ans = [0]*stlen
i = slen
j = tlen
while stlen > 0:
    if s[i-1] == t[j-1]:
        ans[stlen-1] = s[i-1]
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1
    stlen = dp[i][j]
print(''.join(ans))

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

ssize = len(s)
tsize = len(t)


dp = [[0] * (tsize+1) for _ in range(ssize+1)]

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

i, j = ssize, tsize

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

print(ans)

Solution (Python):
s = input()
t = input()
n_s = len(s)
n_t = len(t)

dp = [[0]*(n_t+1) for _ in range(n_s+1)]


for i in range(n_s+1):
    for j in range(n_t+1):
        if i == 0 or j == 0:
            continue
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        if s[i-1] == t[j-1]:
            dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)

sna = ""
while n_s > 0 and n_t > 0:
    if dp[n_s][n_t] == dp[n_s-1][n_t]:
        n_s -= 1
    elif dp[n_s][n_t] == dp[n_s][n_t-1]:
        n_t -= 1
    else:
        sna += s[n_s-1]
        n_s -= 1
        n_t -= 1
ans = ""
for i in range(len(sna))[::-1]:
    ans += sna[i]
print(ans)

Solution (Python):
''' ===============================
    -- @uthor : Kaleab Asfaw
    -- Handle : kaleabasfaw2010
    -- Bio    : High-School Student
    ==============================='''


import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file): self._fd = file.fileno(); self.buffer = BytesIO(); self.writable = "x" in file.mode or "r" not in file.mode; self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b: break
            ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0; return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)); self.newlines = b.count(b"\n") + (not b); ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1; return self.buffer.readline()
    def flush(self):
        if self.writable: os.write(self._fd, self.buffer.getvalue()); self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file): self.buffer = FastIO(file); self.flush = self.buffer.flush; self.writable = self.buffer.writable; self.write = lambda s: self.buffer.write(s.encode("ascii")); self.read = lambda: self.buffer.read().decode("ascii"); self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout); input = lambda: sys.stdin.readline().rstrip("\r\n")



mod = 10**9+7
def lcm(x, y): return (x * y) / (gcd(x, y))
def fact(x, mod=mod):
	ans = 1
	for i in range(1, x+1): ans = (ans * i) % mod
	return ans
def arr2D(n, m, default=0):
	lst = []
	for i in range(n): temp = [default] * m; lst.append(temp)
	return lst
def sortDictV(x): return {k: v for k, v in sorted(x.items(), key = lambda item : item[1])}

def solve(st1, st2):
	n, m = len(st1), len(st2)
	dp = arr2D(n+1, m+1)

	for i in range(1, n+1):
		for j in range(1, m+1):
			if st1[i-1] == st2[j-1]:
				dp[i][j] = dp[i-1][j-1] + 1
			else:
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])

	lcs = ""
	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:
			lcs += st1[i-1]
			i -= 1
			j -= 1
	return lcs[::-1]
		
st1 = input()
st2 = input()
print(solve(st1, st2))

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

Solution (Python):
import numpy as np
s = np.array(list(input()))
t = np.array(list(input()))
dp = np.zeros((len(s)+1, len(t)+1), dtype=int)

equal = s[:, None] == t[None, :]

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

i = len(s)
j = len(t)
ans = []

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

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

Solution (Python):


s = input()
l_s = len(s)
t = input()
l_t = len(t)

dp = list([0 for _ in range(l_t+1)] for _ in range(l_s+1))

for i in range(l_s):
    for j in range(l_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][j], dp[i+1][j] , dp[i][j+1])

ans = []
l = dp[-1][-1]
i = l_s
j = l_t
while l != 0:
    if s[i-1] == t[j-1]:
        ans.append(s[i-1])
        i -= 1
        j -= 1
        l -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1

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

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

S = len(s)
T = len(t)

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

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

ans = ''

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

Solution (Python):
from copy import copy

def getval():
    s = input()
    t = input()
    return s,t

def main(s,t):
    dp = ["" for i in range(len(t)+1)]
    for i in range(len(s)):
        temp = [""]
        for j in range(len(t)):
            prev = dp[j+1]
            last = temp[-1]
            if len(prev)>len(last):
                temp.append(prev)
            elif len(prev)<len(last):
                temp.append(last)
            elif s[i]==t[j]:
                temp.append("".join([dp[j],s[i]]))
            else:
                temp.append(prev)
        dp = copy(temp)
        
    print(dp[len(t)])
                    
if __name__=="__main__":
    s,t = getval()
    main(s,t)

Solution (Python):

def main():
    s = input()
    t = input()
    len_s = len(s)
    len_t = len(t)
    dp = [[0] * len_t for i in range(len_s)]

    for j in range(len_t):
        if s[0] == t[j]:
            for k in range(j, len_t):
                dp[0][k] = 1
            break

    for i in range(len_s):
        if s[i] == t[0]:
            for k in range(i, len_s):
                dp[k][0] = 1
            break
    
    for i in range(1, len_s):
        for j in range(1, len_t):
            if s[i] == t[j]:
                dp[i][j]  = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    length = dp[-1][-1]
    i = len_s - 1
    j = len_t - 1
    ans = ''
    while (length > 0):
        if s[i] == t[j]:
            ans = s[i] + ans
            i -= 1
            j -= 1
            length -= 1
        elif (j > 0 and dp[i][j - 1] == dp[i][j]) or i == 0:
            j -= 1
        else:
            i -= 1
            
    
    
    
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
s = input()
t = input()
slen = len(s)
tlen = len(t)

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

length = dp[slen][tlen]

ans = ''
i,j = slen,tlen
while length>0:
    if s[i-1] == t[j-1]:
        ans += s[i-1]
        i -= 1
        j -= 1
        length -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        i -= 1
print(ans[::-1])

Solution (Python):
import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)



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

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


length = dp[len(s)][len(t)]
_debug(length)

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

Solution (Python):
S = input()
T = input()
ls = len(S)
lt = len(T)

DP = [[0] * (lt + 1) for _ in range(ls + 1)]
Ans = []
for i, s in enumerate(S, 1):
    for j, t in enumerate(T, 1):
        if s == t:
            DP[i][j] = DP[i - 1][j - 1] + 1
        else:
            DP[i][j] = max(DP[i - 1][j], DP[i][j - 1])
cnts = ls
cntt = lt

while DP[cnts][cntt]:
    while DP[cnts][cntt] == DP[cnts][cntt - 1]:
        cntt -= 1
    while DP[cnts][cntt] == DP[cnts - 1][cntt]:
        cnts -= 1
    cnts -= 1
    cntt -= 1
    Ans.append(S[cnts])
print(''.join(Ans[::-1]))

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

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



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

ansl = dp[sl][tl]
i = sl
j = tl
ans = [""]*ansl
while(ansl>0):
    if s[i-1] == t[j-1]:
        ans[ansl-1] = s[i-1]
        i -= 1
        j -= 1
        ansl -= 1
    elif dp[i][j]==dp[i-1][j]:
        i -= 1
    else:
        j -= 1

print("".join(ans))

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

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

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

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

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

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

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

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

print("".join(ans))

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

Solution (Python):



def lcs_len(s1,s2):
    n1,n2 = len(s1),len(s2)
    dp = [ [0]*(n2+1) for _ in range(n1+1) ]
    for i in range(1,n1+1):
        for j in range(1,n2+1):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 
            if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]+1
    return dp[-1][-1]


def lcs_str(s1,s2):
    n1,n2 = len(s1),len(s2)
    dp = [ [0]*(n2+1) for _ in range(n1+1) ]
    for i in range(1,n1+1):
        for j in range(1,n2+1):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 
            if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]+1
    ansr = []
    i,j = n1,n2
    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: 
            ansr.append(s1[i-1])
            i -= 1
            j -= 1
    ans = ansr[::-1]
    return ''.join(ans)


s1 = input()
s2 = input()
ans = lcs_str(s1,s2)
print(ans,flush=True)

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


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

Solution (Python):


def lcs(X, Y, m, n): 
	L = [[0 for x in range(n+1)] for x in range(m+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]) 

	
	index = L[m][n] 

	
	lcs = [""] * (index+1) 
	lcs[index] = "" 

	
	
	i = m 
	j = n 
	while i > 0 and j > 0: 

		
		
		if X[i-1] == Y[j-1]: 
			lcs[index-1] = X[i-1] 
			i-=1
			j-=1
			index-=1

		
		
		elif L[i-1][j] > L[i][j-1]: 
			i-=1
		else: 
			j-=1

	print (''.join(lcs))



s=input()
t=input()
m = len(s) 
n = len(t) 
lcs(s, t, m, n)

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

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

        i-=1
print(''.join(an))

Solution (Python):
def edu_dp_f_lcs():
    s = input()
    t = input()
    slen = len(s)
    tlen = len(t)
    dp = [[0] * (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] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

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

edu_dp_f_lcs()

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

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


for v in range(1,m+1):
    
    for w in range(1,n+1):
        
        if s[v-1] == t[w-1]:
            dp[v][w] = dp[v-1][w-1] + 1
        
        else:
            dp[v][w] = max(dp[v-1][w],dp[v][w-1])





res = []


i = m
j = n
while (i>0 and j>0):
    
    if (dp[i][j] == dp[i-1][j]):
        
        i -= 1
    else:
        
        if (dp[i][j] == dp[i][j-1]):
            
            j -= 1
        
        else:
            
            res.append(s[i-1])
            
            i -= 1
            j -= 1
            

ans = list(reversed(res))
print(''.join(ans))

Solution (Python):
from itertools import combinations
s = input()
n = len(s)
t = input()
m = len(t)

dp = [[0 for i in range(m+1)] for j 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] = max(dp[i][j],dp[i-1][j-1] + 1)
        elif s[i-1] != t[j-1]:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

i = n
j = m
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
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
print(ans)

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

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

dp = [[0 for a in range(3300)] for b in range(3300)]

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

        dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1])

rewsna = ""

while n >= 0 and m >= 0:
    if dp[n][m] == dp[n-1][m]:
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    else:
        rewsna += s[n-1]
        n -= 1
        m -= 1

print(rewsna[::-1])

Solution (Python):
s=input()
t=input()
lens=len(s)
lent=len(t)
dp=[[0 for _ in range(lent+1)] for _ in range(lens+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][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
  else:
    
    ans+=s[i-1]
    i-=1
    j-=1
    
    
print(ans[::-1])

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

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

for i in range(1,m+1) :
    for j in range(1,n+1):
        if t[i-1] == s[j-1] :
            ans[i][j]='match' 
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=dp[i-1][j-1]
            ans[i][j]='lu'
            if dp[i-1][j]>=dp[i][j] :
                dp[i][j]=dp[i-1][j]
                ans[i][j]='u' 
            
            if dp[i][j-1]>=dp[i][j] :
                dp[i][j]=dp[i][j-1]
                ans[i][j]='l' 
for i in range(m+1):
    ans[i][0]='u'
for j in range(n+1):
    ans[0][j]='l'


answer=[]
i=m ; j=n 
while (i>=0 and j>=0):
    if ans[i][j]=='match' :
        answer.append(s[j-1])
        i-=1
        j-=1
    elif ans[i][j]=='l' :
        j-=1
    elif ans[i][j]=='lu':
        i-=1
        j-=1
    else:
        i-=1


answer.reverse()
print(''.join(answer))

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


if __name__ == '__main__':
    main()

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

S=len(s)+1
T=len(t)+1

dp=[[0]*T for i in range(S)]

for i in range(1,S):
  for j in range(1,T):
    if s[i-1]==t[j-1]:
      dp[i][j] = max(dp[i][j],dp[i-1][j-1] + 1)
    dp[i][j] = max(dp[i][j],dp[i-1][j]) 
    dp[i][j] = max(dp[i][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 numpy as np
s = np.array(list(input()))
t = np.array(list(input()))
slen = len(s)
tlen = len(t)

dp = np.zeros((slen+1,tlen+1),dtype=int)

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

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

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