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 math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(input()) 
def ifn(): return float(input()) 
def isn(): return input().split() 
def imn(): return map(int, input().split()) 
def fmn(): return map(float, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, input().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
MOD = 10**9+7

s = input()
t = input()

sl = len(s)
tl = len(t)

dp = [[0 for _ in range(tl+1)]for _ in range(sl+1)]

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

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

Solution (Python):
def LCS(X,Y):
    m,n=len(X),len(Y)
    MAP=[[0 for i in range(m)] for j in range(n)]
    for i in range(1,n):
        for j in range(1,m):
            if Y[i]==X[j]:
                MAP[i][j]=MAP[i-1][j-1]+1
            else:
                MAP[i][j]=max(MAP[i][j-1],MAP[i-1][j])

    i,j=n-1,m-1
    ans=""
    while MAP[i][j]!=0:
        if MAP[i][j]==MAP[i-1][j]:i -=1
        elif MAP[i][j]==MAP[i][j-1]:j -=1
        else:
            ans +=Y[i]
            i -=1
            j -=1
    return ans[::-1]

print(LCS(" "+input()," "+input()))

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(input()) 
def ifn(): return float(input()) 
def isn(): return input().split() 
def imn(): return map(int, input().split()) 
def fmn(): return map(float, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, input().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
MOD = 10**9+7

s = input()
t = input()

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

for i in range(sl):
    for j in range(tl):
        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 = ''
while sl > 0 and tl > 0:
    if dp[sl][tl-1] == dp[sl][tl]:
        tl -= 1
    elif dp[sl-1][tl] == dp[sl][tl]:
        sl -= 1
    else:
        ans = s[sl-1] + ans
        sl -= 1
        tl -= 1
print(ans)

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(input()) 
def isn(): return input().split() 
def imn(): return map(int, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 

s = input()
t = input()
sl = len(s)
tl = len(t)

dp = [[0 for _ in range(tl+1)] for _ in range(sl+1)]

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

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

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

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

    ans = ''
    i, j = len_s, len_t
    while 0 < i and 0 < j:
        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])


if __name__ == '__main__':
    solve()

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

ans = ''

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

print(ans[::-1])

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

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

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

s = len(S)
t = len(T)
ans = ""
while(s and t):
    if (S[s-1]==T[t-1]) and (li[t][s]-1==li[t-1][s-1]):
        ans = S[s-1]+ans
        s-=1
        t-=1
    elif li[t-1][s] >= li[t][s-1]:
        t-=1
    elif li[t-1][s] < li[t][s-1]:
        s-=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]) 


"""
LCSの長さを求めるなら以下で正解
print(dp[-1][-1])
"""



ans = ""
while True:
    if n == 0 or m == 0: 
        break
    if dp[n][m] == dp[n-1][m]:
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    else: 
        n,m = n-1,m-1 
        ans = s[n] + ans 

print(ans)

Solution (Python):
S = input()
T = input()
 
lenS = len(S)
lenT = len(T)
 
lcs = [[0 for i in range(lenT + 1)] for j in range(lenS + 1)]
 
for i in range(lenS):
  for j in range(lenT):
    if S[i] == T[j]:
      lcs[i + 1][j + 1] = lcs[i][j] + 1
    else:
      lcs[i + 1][j + 1] = max(lcs[i + 1][j], lcs[i][j + 1])



i, j = lenS, lenT
answer = ""
while i != 0 and j != 0:
  if lcs[i - 1][j] == lcs[i][j] - 1:
    if lcs[i][j - 1] == lcs[i][j] - 1:
      answer += S[i - 1]
      i -= 1
    j -= 1
  else:
    i -= 1
  
print(answer[::-1])

Solution (Python):
import unittest


class TestF(unittest.TestCase):
    def test_1(self):
        self.assertEqual(
            len(think('axyb', 'abyxb')),
            3
        )

    def test_2(self):
        self.assertEqual(
            len(think('aa', 'xayaz')),
            2
        )

    def test_3(self):
        self.assertEqual(
            len(think('a', 'z')),
            0
        )

    def test_4(self):
        self.assertEqual(
            len(think('abracadabra', 'avadakedavra')),
            7
        )


def solve():
    s, t = read()
    result = think(s, t)
    write(result)


def read():
    s = read_line()
    t = read_line()
    return s, t


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


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

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

    for i in range(1, len(s)):
        for j in range(1, 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]
                )

    return restore_lcs(s, t, dp)


def write(result):
    print(result)


def restore_lcs(s, t, dp):
    lcs = ''
    i, j = len(s), len(t)

    while i >= 0 and j >= 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
            continue
        if dp[i][j] == dp[i][j - 1]:
            j -= 1
            continue
        lcs += s[i - 1]
        i -= 1
        j -= 1

    return lcs[::-1]


if __name__ == '__main__':
    
    solve()

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

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

for i in range(n):
  for j in range(m):
    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)

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

dp = [[0] * (len(T)+1) for i in range(len(S)+1)]
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])

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

print(ans[::-1])

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

dp = [[0] * (len(T)+1) for i in range(len(S)+1)]
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])

ans = []
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.append(S[i-1])
    i -= 1
    j -= 1

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

Solution (Python):
def lcs(x, y):
    dp = [[0]* (len(y)+1) for _ in range(len(x)+1)]
    

    for r in range(len(x)+1):
        for c in range(len(y)+1):
            if r == 0 or c == 0:
                dp[r][c] = 0
            elif x[r-1] == y[c-1]:
                dp[r][c] = dp[r-1][c-1] + 1
            else:
                dp[r][c] = max(dp[r-1][c], dp[r][c-1])
    
    
    lcs = []
    r = len(x)
    c = len(y)
    
    while r>0 and c>0:
        if x[r-1] == y[c-1]:
            lcs.append(x[r-1])
            r-=1
            c-=1
        elif dp[r-1][c] > dp[r][c-1]:
            r-=1
        else:
            c-=1
    print(''.join(lcs[::-1]))

x = input()
y = input()
lcs(x, y)

Solution (Python):
def lcs(s, t):
    ls = len(s)
    lt = len(t)
    d = [[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]:
                d[i][j] = d[i - 1][j - 1] + 1
            else:
                d[i][j] = max(d[i - 1][j], d[i][j - 1])

    res = ""
    i, j = ls, lt
    while i > 0 < j:
        if s[i - 1] == t[j - 1]:
            i -= 1
            j -= 1
            res += s[i]
        elif d[i - 1][j] > d[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return res[::-1]


def main():
    s = input()
    t = input()
    return lcs(s, t)


print(main())

Solution (Python):
S = list(input())
T = list(input())
MAX_LEN = 3007
dp = [[0] * MAX_LEN for _ in range(MAX_LEN)]

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

            dp[ii][jj] = max(dp[ii - 1][jj],
                             dp[ii][jj - 1]
                             )

i = len(S)
j = len(T)
from collections import deque

ans = deque(maxlen=dp[i][j])
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.appendleft(S[i - 1])
        i -= 1
        j -= 1
print(*ans, sep='')

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

s_len = len(s)
t_len = len(t)

dp = [[0 for _ in range(t_len+1)] for _ in range(s_len+1)]

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

ans = ''
x = s_len
y = t_len

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 = ans + s[x]

ans = ans[::-1]
print(ans)

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

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

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

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

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

print(ans)

Solution (Python):

s = input().strip()
t = input().strip()
ls = len(s)
lt = len(t)

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

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

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

print(ans)

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

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

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

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

print(ans)

Solution (Python):
s = " " + input().strip()
t = " " + input().strip()
LS, LT = len(s), len(t)
dp = [[0]*LT for _ in range(LS)]
for i in range(1, LS):
    for j in range(1, LT):
        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])
a, b = (LS-1, LT-1)
r = ""
while a > 0 and b > 0:
    if s[a] == t[b]:
        r+=s[a]
        a, b = a-1, b-1
    elif dp[a][b] == dp[a-1][b]:
        a -= 1
    else:
        b -= 1

print(r[::-1])

Solution (Python):
s = input().strip()
t = input().strip()
LS, LT = len(s), len(t)
dp = [[0]*(LT+1) for _ in range(LS+1)]
dp2 = [[(0, 0)]*(LT+1) for _ in range(LS+1)]
for i in range(LS):
    for j in range(LT):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
            dp2[i+1][j+1] = (i, j)
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
            if dp[i][j+1] > dp[i+1][j]:
                dp2[i+1][j+1] = (i, j+1)
            else:
                dp2[i+1][j+1] = (i+1, j)
bb = []
a, b = (LS, LT)
while a > 0 and b > 0:
    if s[a-1] == t[b-1]:
        bb.append(s[a-1])
    a, b = dp2[a][b]

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

Solution (Python):
def LCS(s, t): 
    A = []
    for i in range(len(s)+1):
        A.append([0]*(len(t)+1))
    for i in range(1, len(s)+1):
        for j in range(1, len(t)+1): 
            if s[i-1] == t[j-1]:
                A[i][j] =max(1 + A[i-1][j-1], A[i-1][j], A[i][j-1])
            else: 
                A[i][j] = max(A[i-1][j], A[i][j-1])
    dlugosc = A[-1][-1]
    i = len(s)
    j = len(t)
    odp = []
    while dlugosc > 0: 
        if s[i-1]==t[j-1] and A[i-1][j-1]+1== A[i][j]:
            odp.append(s[i-1])
            i -= 1
            j -= 1
            dlugosc -= 1
        else: 
            if A[i-1][j] == A[i][j]:
                i -= 1
            else: 
                j -= 1
    return ''.join(odp [::-1])
        
def LCS_zadanie(): 
    s = input()
    t = input()
    print(LCS(s,t))

LCS_zadanie()

Solution (Python):
def main():
    S, T = input(), input()
    L_S, L_T = len(S), len(T)
    dp = [[(0, (0, 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] = (dp[i][j][0] + 1, (-1, -1))
            else:
                dp[i+1][j+1] = max((dp[i+1][j][0], (0, -1)), (dp[i][j+1][0], (-1, 0)))
    i, j = L_S, L_T
    ans = []
    while i > 0 and j > 0:
        di, dj = dp[i][j][1]
        if di != 0 and dj != 0:
            ans.append(S[i-1])
        i, j = i + di, j + dj
    print(''.join(ans[::-1]))



if __name__ == '__main__':
    main()

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

S = input()
T = input()





lcs = [[0 for _ in range(len(T)+1)] for __ in range(len(S)+1)]

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




lcs_string = ""

i, j = len(S), len(T)

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

print(lcs_string)

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

S = input()
T = input()





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




lcs_string = ""

i, j = len(S), len(T)

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

print(lcs_string)

Solution (Python):

import sys
INF = float("inf")


def solve(S: str, T: str):
    lenS, lenT = len(S), len(T)
    DP = [[0]*(lenT+1) for _ in range(lenS+1)]
    for i in range(lenS):
        for j in range(lenT):
            if S[i] == T[j]:
                DP[i+1][j+1] = max(DP[i][j]+1, DP[i+1][j+1])
            DP[i+1][j+1] = max(DP[i+1][j], DP[i][j+1], DP[i+1][j+1])

    ans = ""
    i, j = lenS, lenT
    while i > 0 and j > 0:
        if DP[i][j] == DP[i-1][j]:
            i -= 1
        elif DP[i][j] == DP[i][j-1]:
            j -= 1
        else:
            ans = S[i-1] + ans
            i -= 1
            j -= 1
    print(ans)
    return


def main():

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


if __name__ == '__main__':
    main()

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

s_len = len(s)
t_len = len(t)

dp = [[0] * (t_len+1) for _ in range(s_len+1)]

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

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

print(ans)

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

ss = len(s)
tt = len(t)

dp = [[0 for _ in range(tt+1)] for __ in range(ss+1)]

for i in range(1, ss+1):
    for j in range(1, tt+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 = ss
j = tt
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][j] == dp[i-1][j]:
            i -= 1
        else:
            j -= 1

print(''.join(reversed(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] = max(dp[i-1][j-1]+1, dp[i][j-1], dp[i-1][j])
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])
            
ans = ""
i = len(s)
j = len(t)
while i > 0 and j > 0:
    if s[i-1] == t[j-1] and dp[i][j] == dp[i-1][j-1]+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
    else:
        i -= 1
        j -= 1
        
print(ans)

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

s = input().split()[0]
t = input().split()[0]

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

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

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

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

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

ans = []
i = len(s) - 1
j = len(t) - 1
while True:
    if i < 0 or j < 0:
        break
    if dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    elif dp[i+1][j+1] == dp[i][j+1]:
        i -= 1
    elif dp[i+1][j+1] == dp[i][j] + 1:
        ans.append(t[j])
        i -= 1
        j -= 1

print("".join(ans)[::-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+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])

ans = ""
row = len(S)
col = len(T)
while row > 0 and col > 0:
    if dp[row][col] == dp[row-1][col]:
        row -= 1
    elif dp[row][col] == dp[row][col-1]:
        col -= 1
    else:
        ans += S[row - 1]
        row -= 1
        col -= 1

print(ans[::-1])

Solution (Python):
def main():
    s = input()
    sl = len(s)
    t = input()
    tl = len(t)

    
    dp = [[(0) for _ in range(tl + 1)] for _ in range(sl + 1)]

    for si in range(sl):
        for ti in range(tl):
            if s[si] == t[ti]:
                dp[si + 1][ti + 1] = dp[si][ti] + 1
            else:
                dp[si + 1][ti + 1] = max(dp[si + 1][ti], dp[si][ti + 1])

    
    

    ret = []
    si, ti = sl, tl
    while 0 < si and 0 < ti:
        if dp[si][ti] == dp[si - 1][ti]:
            si -= 1
        elif dp[si][ti] == dp[si][ti - 1]:
            ti -= 1
        else:
            ret.insert(0, s[si - 1])
            si -= 1
            ti -= 1

    print("".join(ret))


main()

Solution (Python):
s = input().rstrip("\n")
t = input().rstrip("\n")


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


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

print(answer)

Solution (Python):
s = list(input())
t = list(input())
a = len(s)
b = len(t)
dp = [[0]*(b+1) for _ in range(a+1)]
ans = ""

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])
i = a
j = b
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]+ans
    i -= 1
    j -= 1
print(ans)

Solution (Python):
from subprocess import*
call(('pypy3','-c',"""
s=input()
t=input()
n,m=len(s),len(t)
dp=[[0]*(m+1) for i in range(n+1)]
dp[0][0]=1
for i in range(n+1):
    for j in range(m+1):
        dp[i][j]=max(dp[i][j-1],dp[i-1][j])
        if i*j!=0 and s[i-1]==t[j-1]:
            dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j])
ans=""
i,j=n,m
while 0<i and 0<j:
    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()
n,m=len(s),len(t)
dp=[[0]*(m+1) for i in range(n+1)]
dp[0][0]=1

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

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

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

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(lenS):
  for j in range(lenT):
    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]

ans = ''
n = lenS
m = lenT
while (n>0 and m>0):
  if S[n-1] != T[m-1]:
    if dp[n-1][m] >= dp[n][m-1]: n -= 1
    else: m -= 1
  else:
    ans += S[n-1]
    n -= 1
    m -= 1
print(ans[::-1])

Solution (Python):
import sys
input = sys.stdin.readline
s = list(input())[: -1]
t = list(input())[: -1]
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
mx = 0
res = []
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 + 1])
      mx = max(mx, dp[i + 1][j + 1])
    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
    dp[i][j + 1] = max(dp[i][j + 1], dp[i][j])
for i in range(len(s), 0, -1):
  for j in range(len(t), 0, -1):
    if dp[i - 1][j - 1] + 1 == dp[i][j]:
      if dp[i][j] == mx and (s[i - 1] == t[j - 1]):
        res += s[i - 1]
        mx -= 1
        break


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

Solution (Python):



def main():
    s = list(input())
    n = len(s)
    t = list(input())
    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 + 1][j], dp[i][j + 1])

    ans = ''
    i = n
    j = 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:
            ans = s[i - 1] + ans
            i -= 1
            j -= 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
S = input()
T = input()
ls = len(S)
lt = len(T)
dp = [[0] * (lt+1) for i in range(ls+1)]

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

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
  else:
    ans = S[ls-1] + ans
    ls -= 1
    lt -= 1

print(ans)