Problem:
 Score : 100 points    Problem Statement You are given strings s and t .
Find one longest string that is a subsequence of both s and t .      Notes A subsequence of a string x is the string obtained by removing zero or more characters from x and concatenating the remaining characters without changing the order.      Constraints  s and t are strings consisting of lowercase English letters.  1 \leq |s|, |t| \leq 3000         Input Input is given from Standard Input in the following format:  s  t       Output Print one longest string that is a subsequence of both s and t .
If there are multiple such strings, any of them will be accepted.        Sample Input 1 axyb
abyxb      Sample Output 1 axb  The answer is axb or ayb ; either will be accepted.       Sample Input 2 aa
xayaz      Sample Output 2 aa       Sample Input 3 a
z      Sample Output 3   The answer is (an empty string).       Sample Input 4 abracadabra
avadakedavra      Sample Output 4 aaadara

Solution (Python):
import numpy as np
def LCS(s,t,rec=False):
  S=np.array(list(s))
  T=np.array(list(t))
  LS,LT=len(S),len(T)
  dp=np.zeros((LS+1,LT+1))
  for n in range(1,LS+1):
    dp[n,1:]=dp[n-1,:-1]+(S[n-1]==T)
    np.maximum(dp[n],dp[n-1],out=dp[n])
    np.maximum.accumulate(dp[n],out=dp[n])
  if rec:
    tmp=[]
    while LS>0 and LT>0:
      if S[LS-1]==T[LT-1]:
        LS,LT=LS-1,LT-1
        tmp.append(S[LS])
      elif dp[LS,LT]==dp[LS-1,LT]:
        LS-=1
      else:
        LT-=1
    return ''.join(reversed(tmp))
  else:
    return dp[LS][LT]
s=input()
t=input()
print(LCS(s,t,True))

Solution (Python):
s=input()
t=input()
ls=len(s)
lt=len(t)
INF=float('inf')

dp=[[0 for i in range(lt+1)] for j in range(ls+1)]
R=[[INF for i in range(lt+1)] for j in range(ls+1)]
for i in range(1,ls+1):
  for j in range(1,lt+1):
    if s[i-1]==t[j-1]:
      dp[i][j]=dp[i-1][j-1]+1
    else:
      dp[i][j]=max(dp[i][j-1],dp[i-1][j])

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

Solution (Python):
import sys
import numpy as np

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

def longest_common_subsequence(S, T):
    """compute table dp satisfying: 
    dp[i,j] = LCS(S[:i], T[:j])"""
    LS, LT = len(S), len(T)
    dp = np.zeros((LS + 1, LT + 1), np.int32)
    for n in range(1, LS + 1):
        dp[n, 1:] = dp[n - 1, :-1] + (S[n - 1] == T)  
        np.maximum(dp[n], dp[n - 1], out=dp[n])  
        np.maximum.accumulate(dp[n], out=dp[n])  
    return dp

def reconstruct_LCS(S, T, dp):
    tmp = []
    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if S[i - 1] == T[j - 1]:
            i, j = i - 1, j - 1
            tmp.append(S[i])
        elif dp[i, j] == dp[i - 1, j]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(tmp))

S = np.array(list(readline().decode()), 'U1')[:-1]
T = np.array(list(readline().decode()), 'U1')[:-1]

dp = longest_common_subsequence(S, T)

print(reconstruct_LCS(S, T, dp))

Solution (Python):
s=input()
t=input()
m,n=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[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+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]
a,b=m,n
tmp=''
while a and b:
    if s[a-1]==t[b-1]:
        a-=1
        b-=1
        tmp+=s[a]
    elif dp[a][b]==dp[a-1][b]:
        a-=1
    else:
        b-=1
print(tmp[::-1])

Solution (Python):
from collections import deque

def mymax(a:int, b:int, c:int):
    if a > b:
        if c > a:
            return c
        else:
            return a
    else:
        if c > b:
            return c
        else:
            return b


def main():
    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):
            dp[i][j] = mymax(
                dp[i-1][j-1] + (s[i-1] == t[j-1]),
                dp[i-1][j],
                dp[i][j-1]
            )
    
    string = deque([])
    i = lens; j = lent
    for _ in range(lens+lent+1):
        if s[i-1] == t[j-1]:
            string.appendleft(s[i-1])
            i -= 1
            j -= 1
        else:
            if dp[i-1][j] > dp[i][j-1]:
                i -= 1
            else:
                j -= 1
        if i <= 0 or j <= 0:
            break
    print(''.join(string))

if __name__ == "__main__":
    main()

Solution (Python):
def lcs(s,t):
    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] = 1+ dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    
    
    substr = ""
    i,j = m,n
    while i>0 and j>0:
        if s[i-1] == t[j-1]:
            substr+=s[i-1]
            i-=1
            j-=1
        elif dp[i][j-1]>dp[i-1][j]:
            j-=1
        else:
            i-=1
    return substr[::-1]
    
    





s = input()
t = input()
print(lcs(s,t))

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

Solution (Python):


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase




from bisect import bisect_right as br
from bisect import bisect







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


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)







mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  


def out(var): sys.stdout.write(str(var))  


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count


def ifvalid(i):
    if i < 0:
        return False
    return True


def solve():
    s = inp()
    t = inp()
    a = len(s)
    b = len(t)
    dp = [[0 for _ in range(b + 5)] for i in range(a + 5)]
    for i in range(1, a + 1):
        for j in range(1, b + 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 = a
    j = b
    ans = ""
    while (i > 0 and j > 0):
        if s[i - 1] == t[j - 1]:
            ans += s[i - 1]
            i -= 1
            j -= 1
        else:
            if dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1
    print(ans[::-1])


solve()

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

s = input()[:-1]
t = input()[:-1]
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 i>0 and j>0:
    if s[i-1]==t[j-1]:
        ans.append(s[i-1])
        i -= 1
        j -= 1
    else:
        if dp[i-1][j]>dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    
ans.reverse()
print(''.join(ans))

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

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

print(''.join(ans))

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10**7)
s,t=input(),input()
dp=[[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<len(s):
            dp[i+1][j]=max(dp[i+1][j],dp[i][j])
        if j<len(t):
            dp[i][j+1]=max(dp[i][j+1],dp[i][j])
        if i<len(s) and j<len(t):
            dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+(s[i]==t[j]))
ans=""
def move(i,j):
    global dp,ans
    if i==0 or j==0:
        return
    elif dp[i][j]>dp[i-1][j-1] and s[i-1]==t[j-1]:
        ans=s[i-1]+ans
        move(i-1,j-1)
    else:
        if dp[i][j]==dp[i][j-1]:
            move(i,j-1)
        else:
            move(i-1,j)
move(len(s),len(t))
print(ans)

Solution (Python):
s=input()
t=input()
b=len(t)
a=len(s)


dp=[[0 for i in range(a+1)] for j in range(b+1)]
for i in range(b+1):
	for j in range(a+1):
		if(i==0 or j==0):
			continue
		if(t[i-1]==s[j-1]):
			dp[i][j]=1+dp[i-1][j-1]
		else:
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])
i=b
j=a
l=[]
while(i>0 and j>0):
	if(t[i-1]==s[j-1]):
		l.append(t[i-1])
		i=i-1
		j=j-1
	else:
		if(dp[i-1][j]>dp[i][j-1]):
			i=i-1
		else:
			j=j-1
for i in reversed(l):
    print(i,end='')

Solution (Python):
s1 = input()
s2 = input()
arra = ["-"]
arrb = ["-"]
for i in s1:
    arra.append(i)
for i in s2:
    arrb.append(i)
n1 = len(s1)
n2 = len(s2)
temparr = [0 for i in range(n2 + 1)]
dp = [temparr[::] for i in range(n1 + 1)]

for i in range(1, n1 + 1):
    for j in range(1 , n2 + 1):
        if arra[i] != arrb[j]:
            dig = dp[i -1][j-1]
            upp = dp[i - 1][j]
            left = dp[i][j - 1]
            dign = dig
            uppn = upp
            leftn = left
            if dign >= uppn and dign >= leftn:
                dp[i][j] = dig
            elif uppn >= dign and uppn >= leftn:
                dp[i][j] = upp
            else:
                dp[i][j] = left
        else:
            dig = dp[i -1][j-1]
            upp = dp[i - 1][j]
            left = dp[i][j - 1]
            dig = dig + 1
            
            
            dign = dig
            uppn = upp
            leftn = left
            if dign >= uppn and dign >= leftn:
                dp[i][j] = dig
            elif uppn >= dign and uppn >= leftn:
                dp[i][j] = upp
            else:
                dp[i][j] = left



ans = ""

while n2 != 0 and n1 != 0 :
    
    if arra[n1] == arrb[n2]:
        ans += arra[n1]
        n2 -= 1 
        n1 -= 1 
        continue 
    else:
        if dp[n1 - 1][n2] >= dp[n1][n2 - 1]:
            n1 -= 1 
        else:
            n2 -=1 
print(ans[::-1])

Solution (Python):
a = input()
b = input()
dp = [[0 for j in range(len(b)+1)] for i in range(len(a)+1)]
for i in range(1, len(a)+1):
    for j in range(1, len(b)+1):
        if a[i-1] == b[j-1] :
            dp[i][j] = dp[i-1][j-1] + 1
            continue
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
m = dp[-1][-1]
ans = ''
i,j=-1,-1
while(len(ans)<m):
    if a[i] == b[j]:
        ans = a[i] + ans
        i-=1
        j-=1
    elif dp[i-1][j] > dp[i][j-1]:
        i-=1
    else:
        j-=1
print(ans)

Solution (Python):
'''
from sys import stdin, setrecursionlimit as srl
from threading import stack_size, Thread
srl(int(1e9)+7)
stack_size(int(1e8))

def solve():
    t = int ( input () )
    for _ in range ( t ) :
        


Thread(target=solve).start()
solve()
'''

a = input()
b = input()
dp = [[0 for j in range(len(b)+1)] for i in range(len(a)+1)]
for i in range(1, len(a)+1):
    for j in range(1, len(b)+1):
        if a[i-1] == b[j-1] :
            dp[i][j] = dp[i-1][j-1] + 1
            continue
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
m = dp[-1][-1]
ans = ''
i,j=-1,-1
while(len(ans)<m):
    if a[i] == b[j]:
        ans = a[i] + ans
        i-=1
        j-=1
    elif dp[i-1][j] > dp[i][j-1]:
        i-=1
    else:
        j-=1
print(ans)

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

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

l1,l2 = len(s),len(t)

dp = [[0]*(l2+1) for _ in range(l1+1)]
memo = [['']*(l2+1) for _ in range(l1+1)]

for i in range(1,l1+1):
  for j in range(1,l2+1):
    if s[i-1]==t[j-1]:
      dp[i][j] = dp[i-1][j-1] + 1
      memo[i][j] = s[i-1]
    else:
      if dp[i-1][j] >= dp[i][j-1]:
        dp[i][j] = dp[i-1][j]
        memo[i][j] = (i-1,j)
      else:
        dp[i][j] = dp[i][j-1]
        memo[i][j] = (i,j-1)
      
i,j = l1,l2
ans = []
while i > 0 and j > 0:
  if len(memo[i][j]) == 2:
    i, j = memo[i][j]
  else:
    ans.append(memo[i][j])
    i, j = i-1, j-1
    
print(''.join(ans[::-1]))

Solution (Python):
import sys
input=sys.stdin.readline
def main():
    s=tuple(input())
    t=tuple(input())
    n=len(s)
    m=len(t)
    dp=[[0 for i in range(m+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(m):
            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+1][j]
                else:
                    dp[i+1][j+1]=dp[i][j+1]
    p=dp[n][m]
    ans=['' for _ in range(p)]
    n-=1
    m-=1
    while p>0:
        if s[n]==t[m]:
            ans[p-1]=s[n]
            n-=1
            m-=1
            p-=1
        elif dp[n+1][m+1]==dp[n][m+1]:
            n-=1
        else:
            m-=1
    print(''.join(ans)) 
if __name__=='__main__':
    main()

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)
"""))
"""
from subprocess import*
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time

starttime = time.time()

mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    
    
    
except:
    pass

"""

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.buffer.readline

'''
dp[i,j]=部分文字列が一致する最長 s[:i],t[:j]文字目まで考慮したとき

chmax(dp[i+1,j],dp[i,j])
chmax(dp[i,j+1],dp[i,j])
if s[i]==t[j]:
    chmax(dp[i+1,j+1],dp[i,j]+1)

完成したdpテーブルの終端からからやればおk
s[i]とv[j]が同じ文字だったら斜め上(i-1,j-1)にもどってそれ以外はdp[i-1,j]ordp[i,j-1]のうちにdp[i,j]と値が同じ方に戻ることにする
'''

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)

S = array(list(read()[:-1]))
T = array(list(read()[:-1]))

from numba import njit


@njit('(i8[:],i8[:],)', cache=True)
def solve(S, T):
    s = len(S)
    t = len(T)
    dp = np.zeros((len(S) + 1, len(T) + 1))
    for i in range(1, s + 1):
        for j in range(1, t + 1):
            dp[i, j] = max(dp[i, j], dp[i - 1, j])
            dp[i, j] = max(dp[i, 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)
    
    i, j = s, t
    ans = []
    while dp[i, j] != 0:
        if S[i - 1] == T[j - 1]:
            ans.append(S[i - 1])
            i -= 1
            j -= 1
            continue
        if dp[i, j] == dp[i - 1, j]:
            i -= 1
        else:
            j -= 1
    return ans


ret = solve(S, T)
print(''.join(map(chr, ret[::-1])))

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

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

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

ans = ''

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

print(ans[::-1])

Solution (Python):
s= input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0 for _ in range(lt+1) ]  for _ in range(ls+1)] 
for ids in range(1,ls+1):
    for idt in range(1,lt + 1):
        
        if s[ids-1] == t[idt-1]:
            dp[ids][idt] =dp[ids-1][idt-1] + 1
        
        elif s[ids-1] != t[idt-1]:
            if dp[ids][idt-1] >= dp[ids-1][idt]:
                dp[ids][idt] = dp[ids][idt-1]
            else:
                dp[ids][idt] = dp[ids-1][idt]
ans = ''
num=dp[-1][-1]
ids = ls;idt=lt
while num:
    if dp[ids][idt] == dp[ids][idt-1]:
        idt -= 1
    elif dp[ids][idt] == dp[ids-1][idt]:
        ids -=1
    elif dp[ids][idt] ==dp[ids-1][idt-1] + 1:
        ans += s[ids-1]
        num -=1
        idt -= 1
        ids -=1
print(ans[::-1])

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

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

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

x_index=len(t)-1
y_index=len(s)-1

if  dp[y_index][x_index]==0:
    print()
    exit()

while True:
    if t[x_index]==s[y_index]:
        ans.append(t[x_index])
        if dp[y_index][x_index]==1:
            break
        else:
            x_index-=1
            y_index-=1
            continue

    else:
        if dp[y_index][x_index]==dp[y_index][x_index-1]:
            x_index-=1
        else:
            y_index-=1


X=reversed(ans)
print(''.join(X))

Solution (Python):
s = list(input())
s = [''] + s
t = list(input())
t = [''] + t
dp = [[0] * (len(t)) for _ 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]) 

answer_len = dp[len(s)-1][len(t)-1]


answer = [0] * answer_len
i = len(s) -1
j = len(t) -1

while True:
    if dp[i][j] - dp[i-1][j-1] == 1 and dp[i][j] - dp[i][j-1] == 1 and dp[i][j] - dp[i-1][j] == 1:
        answer[answer_len-1] = s[i]
        answer_len -= 1
        i -= 1
        j -= 1
        if answer[0] != 0:
            break
    elif dp[i][j] - dp[i][j-1] == 1 and dp[i][j] - dp[i-1][j] != 1:
        i -= 1
    elif dp[i][j] - dp[i][j-1] != 1 and dp[i][j] - dp[i-1][j] == 1:
        j -= 1
    else:
        j -= 1

    if j == 0:
        j += 1
        i -= 1
    
    if i == 0:
        break
 
print(''.join(answer))

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

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

for i in range(1,len(s)+1):
    for u in range(1,len(t)+1):
        if s[i-1]==t[u-1]:
            dp[u][i]=dp[u-1][i-1]+1
        else:
            dp[u][i]=max(dp[u-1][i],dp[u][i-1])
lenth=dp[-1][-1]
i=len(s)
j=len(t)
ans=""
while lenth>0:
    if s[i-1]==t[j-1]:
        ans=s[i-1]+ans
        i-=1
        j-=1
        lenth-=1
    elif dp[j][i]==dp[j-1][i]:
        j-=1
    else:
        i-=1
    lenth=dp[j][i]
print(ans)

Solution (Python):
import sys


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


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

for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            dp[i+1][j+1] = dp[i][j]+1
        else:
            if dp[i+1][j] >= dp[i][j+1]:
                dp[i+1][j+1] = dp[i+1][j]

            elif dp[i+1][j] < dp[i][j+1]:
                dp[i+1][j+1] = dp[i][j+1]
X, Y = len(S), len(T)
ans = []
while dp[X][Y]:
    if S[X-1] == T[Y-1]:
        ans.append(S[X-1])
        X -= 1
        Y -= 1
    else:
        if dp[X-1][Y] >= dp[X][Y-1]:
            X -= 1
        else:
            Y -= 1
            continue
ans.reverse()
print("".join(ans))

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

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

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

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

ans=''

i=m
j=n
while i>0 and j>0:
    if s[i-1]==t[j-1]:
        ans=str(s[i-1])+ans
    i,j=trans[i][j]

print(ans)

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

ans = []
i, j = ns, nt
while dp[i][j]:
    while dp[i - 1][j] == dp[i][j]:
        i -= 1
    while dp[i][j - 1] == dp[i][j]:
        j -= 1
    ans.append(s[i - 1])
    i -= 1
    j -= 1
ans.reverse()
print("".join(ans))

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

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


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

Solution (Python):


INF = float('inf')


def tc():
    s = input()
    t = input()
    n, m = len(s), len(t)

    
    dp = [[0] * (m + 1) for _ 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])

    i, j = n, m
    ans = ''
    while dp[i][j]:
        me = dp[i][j]
        l = dp[i][j - 1]
        u = dp[i - 1][j]
        d = dp[i - 1][j - 1]
        if d > l and d > u:
            ans += s[i - 1]
            i -= 1
            j -= 1
        elif d == l and d == u:
            if d < me:
                ans += s[i - 1]
                i -= 1
                j -= 1
            else:
                i -= 1
        elif l >= u:
            j -= 1
        elif u > l:
            i -= 1

    print(''.join(reversed(ans)))


tc()

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

    res = []
    x,y = len(S),len(T)
    v = dp[x][y]
    while v > 0:
        if dp[x-1][y] == v:
            x -= 1
        elif dp[x][y-1] == v:
            y -= 1
        else:
            res.append(S[x-1])
            x -= 1
            y -= 1
        v = dp[x][y]
    return ''.join(reversed(res))


import sys
input = sys.stdin.readline

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

Solution (Python):
import sys

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

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def LCS(S, T, f=False):

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

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

    if not f:
        return dp[0][0]

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

    return (dp[0][0], ''.join(res))


def main():

    s = in_s()
    t = in_s()

    _, ans = LCS(s, t, True)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def longest_common_subsequence(S, T):
    LS = len(S); LT = len(T)
    dp = [[0] * (LT + 1) for _ in range(LS + 1)]
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if s == t:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
    return dp
    

def reconstruct_LCS(S, T, dp):
    tmp = []
    i, j = len(S), len(T)
    while i and j:
        if S[i - 1] == T[j - 1]:
            i, j = i - 1, j - 1
            tmp.append(S[i])
        elif dp[i][j] == dp[i - 1][j]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(tmp))


s,t=input(), input()
print(reconstruct_LCS(s, t, longest_common_subsequence(s, t)))

Solution (Python):
import numpy as np

def longest_common_subsequence(S, T):
    """compute table dp satisfying: 
    dp[i,j] = LCS(S[:i], T[:j])"""
    LS, LT = len(S), len(T)
    dp = np.zeros((LS + 1, LT + 1), np.int32)
    for n in range(1, LS + 1):
        dp[n, 1:] = dp[n - 1, :-1] + (S[n - 1] == T)  
        np.maximum(dp[n], dp[n - 1], out=dp[n])  
        np.maximum.accumulate(dp[n], out=dp[n])  
    return dp

def reconstruct_LCS(S, T, dp):
    tmp = []
    i, j = len(S), len(T)
    while i and j:
        if S[i - 1] == T[j - 1]:
            i, j = i - 1, j - 1
            tmp.append(S[i])
        elif dp[i, j] == dp[i - 1, j]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(tmp))

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

print(reconstruct_LCS(s, t, longest_common_subsequence(s, t)))