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]*(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][j-1],dp[i-1][j])
sna=[]
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
        sna.append(s[n])
ans=list(reversed(sna))
print("".join(ans))

Solution (Python):


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

D = [[0] * n for i in range(m)]
D[0][0] = int(s[0] == t[0])

for i in range(1, m):
    D[i][0] = D[i-1][0] | int(s[i] == t[0])
for i in range(1, n):
    D[0][i] = D[0][i-1] | int(s[0] == t[i])

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


maxl = max([max(D[i]) for i in range(m)])


ans = []
for i in range(m):
    for j in range(n):
        if D[i][j] == maxl:
            r = i
            c = j
            break

while maxl > 0:
    while c >= 1 and D[r][c-1] == maxl:
        c -= 1
    while r >= 1 and D[r-1][c] == maxl:
        r -= 1
    
    ans.append(t[c])
    c -= 1
    r -= 1
    maxl -= 1
print("".join(ans[::-1]))

Solution (Python):

from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
import sys
sys.setrecursionlimit(10**6)

s = input()
t = input()
N = len(s)
M = len(t)
ans = []

def print_lcs(dp,i,j):
    global ans
    if i == 0 or j == 0:
        return
    if s[i-1] == t[j-1]:
        print_lcs(dp,i-1,j-1)
        ans.append(s[i-1])
    else:
        if dp[i-1][j] >= dp[i][j-1]:
            print_lcs(dp,i-1,j)
        else:
            print_lcs(dp,i,j-1)


def main():
    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])
    
    print_lcs(dp,N,M)
    print(''.join(ans))

if __name__ == "__main__":
    main()

Solution (Python):

import os
import operator
import sys
from io import BytesIO, IOBase

def inar():
    return [int(k) for k in input().split()]
def main():
    s=input()
    t=input()
    dp=[]
    arrow=[]
    for i in range(len(t)+1):
        lis=[0 for k in range(len(s)+1)]
        lis1=["" for l in range(len(s)+1)]
        dp.append(lis)
        arrow.append(lis1)
    for i in range(1,len(t)+1):
        for j in range(1,len(s)+1):
            if t[i-1]==s[j-1]:
                dp[i][j]=dp[i-1][j-1]+1
                arrow[i][j]="C"
            else:
                if dp[i][j-1]>dp[i-1][j]:
                    dp[i][j]=dp[i][j-1]
                    arrow[i][j]="L"
                else:
                    dp[i][j]=dp[i-1][j]
                    arrow[i][j]="U"
    res=""
    i=len(t)
    j=len(s)
    
    
    while 1:
        if i==0 or j==0:
            break
        if arrow[i][j]=="C":
            res+=s[j-1]
            i-=1
            j-=1
        elif arrow[i][j]=="U":
            i-=1
        else:
            j-=1
    print(res[::-1])



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

if __name__ == "__main__":
    main()

Solution (Python):
a=input()
b=input()
dp=[[0 for i in range(len(a)+1)] for j in range(len(b)+1)]
for i in range(1,len(b)+1):
  for j in range(1,len(a)+1):
    if a[j-1]==b[i-1]:
      dp[i][j]=dp[i-1][j-1]+1
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])

res=''

j=len(a)
i=len(b)
while j>0 and i>0:
 
    if dp[i][j]==dp[i-1][j]:
        i-=1
  
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    elif dp[i][j]==dp[i-1][j-1]+1:

        res+=a[j-1]
        i-=1
        j-=1
    
print(res[::-1])

Solution (Python):
def LCS(s1,s2):
    l1, l2 = len(s1), len(s2)
    if l1 == 0 or l2 == 0:
        return ''
    
    dp = [[0 for i in range(l2+1)] for j in range(l1+1)]

    for i in range(l1):
        for j in range(l2):
            if s1[i] == s2[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            dp[i+1][j+1] = max(max(dp[i+1][j+1],dp[i][j+1]),dp[i+1][j])
    
    lcs_str = ''
    i,j = l1,l2
    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_str += s[i-1]
            i -= 1
            j -= 1
    
    return lcs_str[::-1]

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

Solution (Python):

def resolve():
    S = input()
    T = input()

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

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

    ans = ""

    i, j = len(S), 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)


if __name__ == "__main__":
    resolve()

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


s = "." + s; t = "." + t;

a = len(s)
b = len(t)

dp = [['']*(b) for _ in range(2)]


for i in range(1, a):
    for j in range(1, b):
        if s[i] == t[j]:
            if len(dp[i&1][j]) < len(dp[(i+1)&1][j-1]) + 1:
                dp[i&1][j] = dp[(i+1)&1][j-1] + s[i]
        else:
            for adja in [[i-1, j-1], [i-1, j], [i, j-1]]:
                if len(dp[i&1][j]) < len(dp[adja[0]&1][adja[1]]):
                    dp[i&1][j] = dp[adja[0]&1][adja[1]]

print(dp[(a+1)&1][b-1])

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

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

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

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

S = readline().rstrip()
T = readline().rstrip()

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


x = len(S)
y = len(T)
ans = ""
while y > 0 and x > 0:
  if dp[x][y] == dp[x][y - 1] + 1 == dp[x - 1][y] + 1:
    ans += T[y - 1]
    y -= 1
    x -= 1
  else:
    if dp[x][y - 1] == dp[x][y]:
      y -= 1
    else:
      x -= 1
  
print(ans[::-1])

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

dp=[[-1]*(len(t)+1) for x in range(len(s)+1)]
arr = ""
for i in range(len(s),-1,-1):
    for j in range(len(t),-1,-1):
        if i>=(len(s)) or j>=(len(t)):
            dp[i][j] = 0
        else:
            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])

l=dp[0][0]
i,j=0,0
while len(arr)!=l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>=dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
l = 3010
def main():
    s = input().strip()
    t = input().strip()
    dp = [[0] * l for i in range(l)]
    rdp = [[0] * l for i in range(l)]
    for i in range(len(s)):
        for j in range(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
                rdp[i][j] = (i-1, j-1)
            else:
                if dp[i-1][j] < dp[i][j-1]:
                    dp[i][j] = dp[i][j-1]
                    rdp[i][j] = (i, j-1)
                else:
                    dp[i][j] = dp[i-1][j]
                    rdp[i][j] = (i-1, j)

    
    ans = ''
    p, q = len(s)-1, len(t)-1
    while True:
        if p == -1 or q == -1:
            break
        nextp, nextq = rdp[p][q]
        if nextp != p and nextq != q:
            ans += s[p]
        p = nextp
        q = nextq

    print(''.join(reversed(ans)))
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)

    dp = [[0]*(M+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            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:
            res = S[N-1] + res
            N -= 1
            M -= 1
    print(res)


if __name__ == '__main__':
    main()

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

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



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()
sl=len(s)
tl=len(t)
dp=[[0]*(sl+1) for _ in range(tl+1)]
for i in range(1,tl+1):
  for j in range(1,sl+1):
    if(t[i-1]==s[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=tl
j=sl
ans=[]
while i>0 and j>0:
  if(t[i-1]==s[j-1]):
    ans.append(t[i-1])
    i=i-1
    j=j-1
  else:
    if(dp[i-1][j]+1>dp[i][j-1]):
      i=i-1
    else:
      j=j-1

ans.reverse()
print(''.join(ans))

Solution (Python):

S=input()
T=input()

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


for i in range(1,t+1):
  for j in range(1,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])
  
arr=[]
while(i>0 and j>0):
  if S[j-1]==T[i-1]:
    arr+=[j-1]
    j-=1
    i-=1
  else:
    if dp[i-1][j]>dp[i][j-1]:
      i-=1
    else:
      j-=1
arr.sort()
for i in arr:
  print(S[i],end="")

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):
    s = S[i-1]
    for j in range(1,M+1):
        t = T[j-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])
ans = []
while N and M:
    if dp[N][M] > max(dp[N-1][M],dp[N][M-1]):
        ans.append(S[N-1])
        N -= 1
        M -= 1
    elif dp[N][M] == dp[N-1][M]:
        N -= 1
    else:
        M -= 1

ans = ans[::-1]

ans = "".join(ans)
print(ans)

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 and j:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        res.append(S[i - 1])
        i -= 1
        j -= 1

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

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 = []
stack = [(len(S), len(T))]

while stack:
    x, y = stack.pop()
    if dp[x][y] == 0:
        break
    if x - 1 >= 0 and dp[x][y] == dp[x - 1][y]:
        stack.append((x - 1, y))
    elif y - 1 >= 0 and dp[x][y] == dp[x][y - 1]:
        stack.append((x, y - 1))
    else:
        res.append(S[x - 1])
        stack.append((x - 1, y - 1))

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

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

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

data = [[0 for _ in range(n)] for _ in range (m)]

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

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

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

Solution (Python):

import sys
import re
"""
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)
"""

def solve(S, T):
    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

    

    
    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 "".join(res)

def main():
    input = sys.stdin.readline
    
    
    

    S = input().strip()
    T = input().strip()
    lcs = solve(S, T)
    print(lcs)
    """
    s = [ord(c) - 97 for c in input()]
    t = [ord(c) - 97 for c in input()]
    dp = {}
    memo = {}
    for i in range(len(s)+1):
        for j in range(len(t)+1):
            if i == 0 or j == 0:
                dp[(i, j)] = 0
            else:
                if s[i - 1] == t[j - 1]:
                    dp[(i, j)] = dp[(i - 1, j - 1)] + 1
                    memo[(i, j)] = (i - 1, j - 1)
                else:
                    if dp[(i - 1, j)] < dp[(i, j - 1)]:
                        dp[(i, j)] = dp[(i, j - 1)]
                        memo[(i, j)] = (i, j - 1)
                    else:
                        dp[(i, j)] = dp[(i - 1, j)]
                        memo[(i, j)] = (i - 1, j)
   
    lcs = []
    while dp[i, j] > 0:
        i, j = memo[(i, j)]
        if s[i] == t[j]:
            lcs.insert(0, chr(s[i] + 97))

    print("".join(lcs))
    """


if __name__ == '__main__':
    main()

Solution (Python):
def lcs(str1, str2):
    """文字列str1, str2の最長共通部分列(Longest Common Subsequence, LCS)を求める。
    計算量 O(|str1||str2|)
    """
    dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]
    for i in range(len(str1)):
        for j in range(len(str2)):
            if str1[i] == str2[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 = ''
    i, j = len(str1), len(str2)
    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 = str1[i - 1] + res
            i -= 1
            j -= 1

    return res


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

Solution (Python):
import sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f
from copy import *
from bisect import *	
from heapq import *
from math import *
from itertools import permutations 
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 

if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
def li():
	return [int(x) for x in input().split()]
def gi():	
	return [x for x in input().split()]
def fi():
	return int(input())
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())	
def gh():
	sys.stdout.flush()
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)
def bo(i):
	return ord(i)-ord('a')
		


tt=1



while tt>0:
	tt-=1
	s=si()
	t=si()
	n=len(s)
	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 i==1 and j==1:
					dp[i][j]=int(s[i-1]==t[j-1])
			elif i==1:
				
					dp[i][j]=max([dp[i][j],dp[i][j-1],int(s[i-1]==t[j-1])])
			elif j==1:
				dp[i][j]=max([dp[i][j],dp[i-1][j],int(s[i-1]==t[j-1])])
			else:
				dp[i][j]=max([dp[i][j],dp[i-1][j-1]+int(s[i-1]==t[j-1]),dp[i][j-1],\
					dp[i-1][j]])	
	i=n
	j=m
	ans=""
	tle=0
	
	
	while i>0 or j>0:
		if dp[i][j]==0:
			break
		if i>0 and dp[i-1][j]==dp[i][j]:
			i-=1
		elif j>0 and dp[i][j-1]==dp[i][j]:
			j-=1		
		elif i>0 and j>0 and dp[i][j]-dp[i-1][j-1]==1:
			ans+=s[i-1]
			i-=1
			j-=1
		
		else:
			if i>0 and j>0:
				if dp[i-1][j]>dp[i][j-1]:
					i-=1
				else:
					j-=1	
				
			elif j>0:	
				j-=1
			else:
				i-=1	
		tle+=1
		
		if tle>n+m:
			break
	if dp[i][j]>0:
		ans+=s[0]			
	print(ans[::-1])

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(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 DP[i][j]:
        if DP[i - 1][j] < DP[i][j] and DP[i][j - 1] < DP[i][j]:
            ans += s[i - 1]
            i -= 1
            j -= 1
        else:
            if DP[i - 1][j] ==  DP[i][j]:
                i -= 1
            if DP[i][j - 1] == DP[i][j]:
                j -= 1

    print(ans[::-1])


if __name__ == '__main__':
    main()

exit()

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(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 DP[i][j]:
        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])


if __name__ == '__main__':
    main()

exit()

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

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

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

y = len(s)
x = len(t)

moji = ""

while(True):
  while(y > 0 and table[y-1][x] == table[y][x]):
    y -= 1
  
  while(x > 0 and table[y][x-1] == table[y][x]):
    x -= 1
  if(x > 0 and y > 0):
    moji = s[y-1] + moji
    x -= 1
    y -= 1
  else:
    break

print(moji)

Solution (Python):

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

ans = []
x = lt
y = ls
while x > 0 and y > 0:
    if dp[x][y] == dp[x-1][y]:
        x -= 1
    elif dp[x][y] == dp[x][y-1]:
        y -= 1
    else:
        x -= 1
        y -= 1
        ans.append(t[x])
ans = reversed(ans)
print("".join(ans))

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


from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  


def debug(*x):
    print(*x)


def solve(S, T):
    sizeS = len(S)
    sizeT = len(T)
    m = [[0] * (sizeT + 1) for _i in range(sizeS + 1)]
    for i in range(1, sizeS + 1):
        for j in range(1, sizeT + 1):
            m[i][j] = max(
                m[i - 1][j],
                m[i][j - 1],
                m[i - 1][j - 1] + 1 if S[i - 1] == T[j - 1] else 0
            )
    result = []
    i = sizeS
    j = sizeT
    while i > 0 and j > 0:
        if m[i][j] == m[i - 1][j]:
            i -= 1
        elif m[i][j] == m[i][j - 1]:
            j -= 1
        else:
            result.append(chr(S[i - 1]))
            i -= 1
            j -= 1
    print("".join(reversed(result)))


def main():
    S = input().strip()
    T = input().strip()
    solve(S, T)


def _test():
    """
    >>> solve("axyb", "abyxb")
    axb
    """
    global chr
    import doctest
    def chr(x): return x
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):


s = input()
t = input()

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

q = []

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

i = len(t)-1
j = len(s)-1

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

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

Solution (Python):
s=input()
t=input()
l1=len(s)
l2=len(t)
dp=[[0 for _ in range(l1)] for _ in range(l2)]
flg=False
for i in range(l1):
    if flg or t[0]==s[i]:
        flg=True
        dp[0][i]=1
flg=False
for i in range(l2):
    if flg or s[0]==t[i]:
        flg=True
        dp[i][0]=1
for i in range(1,l2):
    for j in range(1,l1):
        if t[i]==s[j]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
ans=''
i=l2-1
j=l1-1
while i>=0 and j>=0:
    if s[j]==t[i]:
        ans+=s[j]
        i-=1
        j-=1
    else:
        if i==0:
            j-=1
        elif j==0:
            i-=1
        elif dp[i-1][j]>dp[i][j-1]:
            i-=1
        else:
            j-=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(1, len(s)+1):
    for j in range(1, len(t)+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)
        dp[i][j] = max(dp[i][j], dp[i][j-1])
        dp[i][j] = max(dp[i][j], 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:
        ans += t[j-1]
        i -= 1
        j -= 1
   
print(ans[::-1])

Solution (Python):

import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

def lcs(X,Y):
    m,n = len(X),len(Y)
    L = [[0]*(n+1) for i in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            if 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])
    size = L[m][n] 
    lcs = []
    i,j = m,n
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]: 
            lcs.append(X[i-1]) 
            i-=1
            j-=1
        elif L[i-1][j] > L[i][j-1]: 
            i-=1
        else: 
            j-=1
    return ''.join(lcs[::-1])

s = input().strip()
t = input().strip()
ans = lcs(s,t)
print(ans)

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

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

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

for i in range(m+1):
    for j in range(n+1):

        if i == 0 or j == 0:
            dp[i][j] = 0

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



final = dp[m][n]

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

i = m
j = n

while i > 0 and j > 0:
    if s[i-1] == t[j-1]:
        lcs[final-1] = s[i-1]
        i -= 1
        j -= 1
        final -= 1

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


print("".join(lcs))

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

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

for i in range(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])
            

x = len(s)
y = len(t)
res = ''
while(dp[x][y]):
    if dp[x][y-1]==dp[x][y]: 
        y -= 1
    elif dp[x-1][y]==dp[x][y]: 
        x -= 1
    else:
        res = s[x-1] + res
        x -= 1
        y -= 1

print(res)

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


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

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


ans = ""
while ls > 0 and lt > 0:
    if dp[ls][lt] == dp[ls-1][lt]:
        ls -= 1
    elif dp[ls][lt] == dp[ls][lt-1]:
        lt -= 1
    elif dp[ls][lt] == dp[ls-1][lt-1] + 1:
        ans += s[ls-1]
        ls -= 1
        lt -= 1
print(ans[::-1])

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

dp = [[-1 for i in range(tlen + 1)] for j in range(slen + 1)]

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


ans = ""
i, j = 0, 0

while i < slen and j < tlen:
    if dp[i][j] == dp[i + 1][j]:
        i += 1
    elif dp[i][j] == dp[i][j + 1]:
        j += 1
    else:
        ans += s[i]
        i += 1
        j += 1

print(ans)