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, t = input(), input()
ls, lt = len(s), len(t)

table = [[0] * (lt+1) for i in range(ls+1)]
for ss in range(ls):
    for st in range(lt):
        table[ss+1][st+1] = table[ss][st] + 1 if s[ss] == t[st] else max(table[ss+1][st], table[ss][st+1] )

ans = ""
ss, st = ls, lt
while ss * st != 0:
    if table[ss][st] == table[ss-1][st]:
        ss -= 1
    elif table[ss][st] == table[ss][st-1]:
        st -= 1

    else:
        ss -= 1
        st -= 1
        ans = s[ss] + 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+1][j+1],dp[i][j]+1)

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


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

Solution (Python):
s=str(input())
t=str(input())
ls=len(s)
lt=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):
    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=""
x=ls
y=lt
while x>0 and y>0:
  if dp[x][y]==dp[x-1][y]:
    x-=1
  elif dp[x][y]==dp[x][y-1]:
    y-=1
  else:
    ans=s[x-1]+ans
    x-=1
    y-=1
print(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])


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()
t = input()
ls = len(s)
lt = len(t)
dp = [[0] * (ls+1) for _ in range(lt+1)]

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

ret = []
while ls > 0 and lt > 0:
    
    
    
    if dp[lt][ls] == dp[lt][ls-1]:
        ls -= 1
    elif dp[lt][ls] == dp[lt-1][ls]:
        lt -= 1
    else:
        ret.append(s[ls-1])
        ls -= 1
        lt -= 1

ret.reverse()
print("".join(ret))

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

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

ret = []
while ls > 0 and lt > 0:
    if dp[lt][ls] == dp[lt][ls-1]:
        ls -= 1
    elif dp[lt][ls] == dp[lt-1][ls]:
        lt -= 1
    else:
        ret.append(s[ls-1])
        ls -= 1
        lt -= 1

ret.reverse()
print("".join(ret))

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

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

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

x = lt
y = ls

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

print(ans)

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

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

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

lst = []

N = i + 1
M = j + 1
while (N - 1) >= 0 and (M - 1) >= 0:
    if S[N - 1] == T[M - 1]:
        lst.append(S[N - 1])
        N -= 1
        M -= 1
    else:
        if dp[N][M] == dp[N - 1][M]:
            N -= 1
        else:
            M -= 1

print (*lst[::-1], sep = '')

Solution (Python):
s = str(input())
t = str(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][j-1], dp[i-1][j])

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

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

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

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


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

print(ans)

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


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

for i, s in enumerate(S):
  for j, t in enumerate(T):
    if s == t:
      dp[i][j] = dp[i-1][j-1] + 1
    else:
      dp[i][j] = max(dp[i][j-1], dp[i-1][j])
ans = []
s = (len(S)-1, len(T)-1)
while True:
  x, y = s
  if x < 0 or y < 0:
    break
  if S[x] == T[y]:
    ans.append(S[x])
    s = (x-1, y-1)
  else:
    if dp[x-1][y] > dp[x][y-1]:
      s = (x-1, y)
    else:
      s = (x, y-1)

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

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

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

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

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

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

print(ans)

Solution (Python):
def main2():
    
    s = input()
    t = input()
    v = [0] * (len(t) + 1)
    dp = [v]
    
    

    

    
    for str1 in s:
        v = v.copy()
        dp.append(v)
        
        ll, ul = 0, 0
        for j, str2 in enumerate(t, 1):
            uu = v[j]
            if str1 == str2:
                v[j] = ll = ul + 1
            elif ll > uu:
                v[j] = ll
            ul = uu
        
            
    
    
    res = ""
    s_len = len(s)
    t_len = len(t)
    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:
            res = s[s_len-1] + res
            s_len -= 1
            t_len -= 1
    print(res)
        
if __name__ == '__main__':
    main2()

Solution (Python):
"""memo
    いつものように，numpyを使いたくなかったので他人のコードを参考にした．
    enumerateは「https://note.nkmk.me/python-enumerate-start/」を参考．
"""

def main2():
    
    s = input()
    t = input()
    v = [0] * (len(t) + 1)
    dp = [v]
    
    

    

    
    for str1 in s:
        v = v.copy()
        
        dp.append(v)
        
        ll, ul = 0, 0
        for j, str2 in enumerate(t, 1):
            uu = v[j]
            if str1 == str2:
                v[j] = ll = ul + 1
            else:
                if ll > uu:
                    v[j] = ll
                else:
                    ll = uu
            ul = uu
        
            
    
    
    res = ""
    s_len = len(s)
    t_len = len(t)
    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:
            res = s[s_len-1] + res
            s_len -= 1
            t_len -= 1
    print(res)

if __name__ == '__main__':
    main2()

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

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

lcs_str = ''
i, j = n, m
while i >= 1 and j >= 1:
    if s[i - 1] == t[j - 1]:
        lcs_str += s[i - 1]
        i -= 1
        j -= 1
    else:
        if dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

print(lcs_str[::-1])

Solution (Python):
import sys
import math
from collections import deque
import copy

input = sys.stdin.readline

s = input()
t = input()

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

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

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

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

s = input(); t = input()
n = len(s); m = len(t)
dp=[[0] * (m+1) for i in range(n+1)]
repair = [[0] * (m+1) for i in range(n+1)]
for i in range(n):
  for j in range(m):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j] + 1
      repair[i+1][j+1] = (i,j)
    else:
      dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
      repair[i+1][j+1] = (i,j+1) if dp[i][j+1] >= dp[i+1][j] else (i+1,j)


M = dp[n][m]
ans = []
i = n; j = m
while i != 0 and j != 0:
  
  ni,nj = repair[i][j]
  if dp[ni][nj] < dp[i][j]:
    ans.append(s[ni])
  i,j = ni,nj
ans.reverse()
print(*ans, sep = "")

Solution (Python):
import sys

def solve(s: str, t: str):
    ls=len(s)
    lt=len(t)
    dp=[[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
            if dp[i+1][j]>dp[i+1][j+1]: dp[i+1][j+1]=dp[i+1][j]
            if dp[i][j+1]>dp[i+1][j+1]: 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
        else:
            ans=s[ls-1]+ans
            ls-=1
            lt-=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()

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

str = ''

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:
        str = s[i-1]+str
        i -= 1
        j -= 1
print(str)

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


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

Solution (Python):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue


Mod = 1000000007
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



        
def main(): 
    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):
            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 = ls
    j = lt
    while dp[i][j] > 0:
        if dp[i-1][j] == dp[i][j]:
            i -= 1
        elif dp[i][j-1] == dp[i][j]:
            j -= 1
        else:
            ans = s[i-1]+ans
            i -= 1
            j -= 1

    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):

def resolve():
    s = input()
    t = input()

    dp = [[""] * (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] + s[i]
            else:
                if len(dp[i][j+1]) >= len(dp[i+1][j]):
                    dp[i+1][j+1] = dp[i][j+1]
                else:
                    dp[i+1][j+1] = dp[i+1][j]

    print(dp[len(s)][len(t)])

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

    
    
    
    res = ""
    i = len(dp) - 1
    j = len(dp[0]) - 1
    while i != 0 and j != 0:
        if dp[i][j] == dp[i - 1][j]: 
            i -= 1 
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res = s[i-1] + res
            i -= 1
            j -= 1

    print(res)

if __name__ == "__main__":
    resolve()

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


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

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


ans = ''
i=ls
j=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(); 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] = 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])
res = ''
i = len(s); j = len(t)
while (i>0) & (j>0):
  if dp[i][j] == dp[i-1][j]: i += -1
  elif dp[i][j] == dp[i][j-1]: j += -1
  else: res = s[i-1] + res; i += -1; j += -1
print(res)

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

def main():
    s=input()
    t=input()
    sl,tl=len(s),len(t)
    lcs=[[0]*(tl+1) for _ in range(sl+1)]
    for i in range(1,sl+1):
        for j in range(1,tl+1):
            if s[i-1]==t[j-1]:
                lcs[i][j]=lcs[i-1][j-1]+1
            else:
                lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1])
    k = lcs[i][j]
    r = ''
    while k:
        if lcs[i - 1][j] == k:
            i -= 1
        elif lcs[i][j - 1] == k:
            j -= 1
        else:
            k -= 1
            i -= 1
            j -= 1
            r += s[i]
    print(r[::-1])

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)):
    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 = ""
n = dp[-1][-1]
i = len(s)
j = len(t)
while n > 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:
        ans = s[i-1] + ans
        n -= 1
        i -= 1
        j -= 1

print(ans)

Solution (Python):





s= input()
t= input()

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for i, si in enumerate(s):
    for j, tj in enumerate(t):
        if si==tj:
            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 =""
n = dp[-1][-1]
i = len(s)
j =len(t)
while n >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:
        ans = s[i-1]+ans
        n-=1
        i-=1
        j-=1

print(ans)

Solution (Python):

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

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

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

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

print(ans)

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


def lcs(s, t)->list:
    sn = len(s)
    tn = len(t)
    dp = [[0 for _ in range(tn+1)] for _ in range(sn+1)]
    for i in range(sn):
        for j in range(tn):
            if s[i] == t[j]: dp[i+1][j+1] = max(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 dp


def restore_str(lcs_dp)->str:
    restore = str()
    i = len(s)
    j = len(t)

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

    return restore


def main():
    lcs_dp = lcs(s, t)
    ans = restore_str(lcs_dp)
    return print(ans)


if __name__ == '__main__':
    main()

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


def lcs(s, t)->list:
    sn = len(s)
    tn = len(t)
    dp = [[0 for _ in range(tn+1)] for _ in range(sn+1)]
    for i in range(sn):
        for j in range(tn):
            if s[i] == t[j]: dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
            else: dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])
    
    return dp


def restore_str(lcs_dp)->str:
    restore = str()
    i = len(s)
    j = len(t)

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

    return restore


def main():
    lcs_dp = lcs(s, t)
    ans = restore_str(lcs_dp)
    return print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

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


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

  if dp[i][j] > dp[i - 1][j] and dp[i][j] > dp[i][j - 1]:
    ans += s[i - 1]
    i -= 1
    j -= 1

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

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

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


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

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

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

Ls = len(S)
Lt = len(T)

dp = [[0] * (Lt + 1) for _ in range(Ls + 1)]

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

match = []
now_row = Ls
now_column = Lt
while now_row > 0 and now_column > 0:
    if dp[now_row][now_column] == dp[now_row-1][now_column]:
        now_row -= 1
    elif dp[now_row][now_column] == dp[now_row][now_column-1]:
        now_column -= 1
    else:
        match.append(T[now_column-1])
        now_column -= 1
        now_row -= 1


match.reverse()
print("".join(match))

Solution (Python):
import numpy as np

def main():
    s = np.array([str(i) for i in input()], dtype=np.unicode)
    t = np.array([str(i) for i in input()], dtype=np.unicode)

    num_s = int(s.shape[0])
    num_t = int(t.shape[0])


    dp = np.zeros((num_s +1, num_t +1), dtype='int64')

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

    for i in range(num_s):
        np.maximum(dp[i, 1:], dp[i, :-1] + eq[i], out=dp[i+1, 1:])
        np.maximum.accumulate(dp[i+1], out=dp[i+1])
    

    res=''
    pos_s = num_s
    pos_t = num_t


    while len(res) < np.max(dp[num_s]):
        temp = dp[pos_s, pos_t]
        
        if dp[pos_s-1, pos_t] == temp:
            pos_s -= 1

        if dp[pos_s, pos_t-1] == temp:
            pos_t -= 1

        if s[pos_s - 1] == t[pos_t - 1]:
            res += s[pos_s-1]
            pos_s -= 1
            pos_t -= 1

        
        
    print(res[::-1])

main()

Solution (Python):




def calc_lcs(s, t):
  dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
  
  for i, si in enumerate(s, 1):
    for j, tj in enumerate(t, 1):
      dp[i][j] = max((dp[i-1][j-1] + 1) if si==tj else 0, dp[i-1][j], dp[i][j-1])

  lcs = ''
  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
    elif dp[i][j] == dp[i-1][j-1]+1:
      lcs = s[i-1] + lcs
      i -= 1
      j -= 1
  return lcs

def main():
  s = input().strip()
  t = input().strip()
  print(calc_lcs(s, t))


if __name__=='__main__':
  main()

Solution (Python):




def calc_lcs(s, t):
  dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
  
  for i, si in enumerate(s, 1):
    for j, tj in enumerate(t, 1):
      dp[i][j] = max((dp[i-1][j-1] + 1) if si==tj else 0, dp[i-1][j], dp[i][j-1])

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

def main():
  s = input().strip()
  t = input().strip()
  print(calc_lcs(s, t))


if __name__=='__main__':
  main()

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

ans = []
p = len(a)
t = len(b)
while p>0 and t>0:
  if a[p-1] == b[t-1]:
    ans.insert(0, a[p-1])
    p = p-1
    t = t-1
  else:
    if dp[p][t-1] > dp[p-1][t]:
      t = t-1
    else:
      p = p-1
print("%s" % ''.join(ans))

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

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

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


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


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

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

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

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


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


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

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

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

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

i = lt
j = ls
while i-1>=0 and j-1>=0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
        continue
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
        continue
    else:

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

print(ans)

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

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


main()

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

    s = readline().rstrip()
    t = readline().rstrip()

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

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

    rest = dp[len(s)][len(t)]

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

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

        
        

    print(ret)


if __name__ == '__main__':
    main()

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

dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
mem_i = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]
mem_j = [[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]:
            dp[i][j] = dp[i - 1][j - 1] + 1
            mem_i[i][j] = i - 1
            mem_j[i][j] = j - 1
        else:
            dp[i][j] = max(
                dp[i - 1][j],
                dp[i][j-1]
            )

            if dp[i - 1][j] < dp[i][j - 1]:
                mem_i[i][j] = i
                mem_j[i][j] = j - 1
            else:
                mem_i[i][j] = i - 1
                mem_j[i][j] = j

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

result = []
while (i > 0 and j > 0):
    prev_i = mem_i[i][j] 
    prev_j = mem_j[i][j]
    if prev_i == i - 1 and prev_j == j - 1:
        _s = s[prev_i]
        result.append(_s)
    i = prev_i
    j = prev_j

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