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



Sample input:
axyb
abyxb


Sample output:
axb

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# Input#
# n = int(input())
# n, k = map(int, input().split())
# a = list(map(int, input().split()))

s = input()
t = input()

memo = [[-1 for i in range(len(t) + 1)] for j in range(len(s) + 1)]

for i in range(len(s) + 1):
    memo[i][0] = 0

for i in range(len(t) + 1):
    memo[0][i] = 0


def dp(i, j):
    if memo[i][j] == -1:
        if s[i - 1] == t[j - 1]:
            memo[i][j] = dp(i - 1, j - 1) + 1
        else:
            memo[i][j] = max(dp(i - 1, j), dp(i, j - 1))

    return memo[i][j]


for i in range(len(s)):
    tmp = dp(i, len(t))

for i in range(len(t)):
    tmp = dp(len(s), i)

max = dp(len(s), len(t))

ans = ""

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

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

print("{}".format(ans))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# Input#
# n = int(input())
# n, k = map(int, input().split())
# a = list(map(int, input().split()))

s = input()
t = input()

memo = [[-1 for i in range(len(t) + 1)] for j in range(len(s) + 1)]

for i in range(len(s) + 1):
    memo[i][0] = 0

for i in range(len(t) + 1):
    memo[0][i] = 0


def dp(i, j):
    if memo[i][j] == -1:
        if s[i - 1] == t[j - 1]:
            memo[i][j] = dp(i - 1, j - 1) + 1
        else:
            memo[i][j] = max(dp(i - 1, j), dp(i, j - 1))

    return memo[i][j]


for i in range(min(len(s), len(t))):
    tmp = dp(i, i)

max = dp(len(s), len(t))

ans = ""

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

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

print("{}".format(ans))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# Input#
# n = int(input())
# n, k = map(int, input().split())
# a = list(map(int, input().split()))

s = input()
t = input()

memo = [[-1 for i in range(len(t) + 1)] for j in range(len(s) + 1)]

for i in range(len(s) + 1):
    memo[i][0] = 0

for i in range(len(t) + 1):
    memo[0][i] = 0


def dp(i, j):
    if memo[i][j] == -1:
        if s[i - 1] == t[j - 1]:
            memo[i][j] = dp(i - 1, j - 1) + 1
        else:
            memo[i][j] = max(dp(i - 1, j), dp(i, j - 1))

    return memo[i][j]


for i in range(len(s)):
    tmp = dp(i, min(i, len(t)))

max = dp(len(s), len(t))

ans = ""

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

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

print("{}".format(ans))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# Input#
# n = int(input())
# n, k = map(int, input().split())
# a = list(map(int, input().split()))

s = input()
t = input()

memo = [[-1 for i in range(len(t) + 1)] for j in range(len(s) + 1)]

for i in range(len(s) + 1):
    memo[i][0] = 0

for i in range(len(t) + 1):
    memo[0][i] = 0


def dp(i, j):
    if memo[i][j] == -1:
        if s[i - 1] == t[j - 1]:
            memo[i][j] = dp(i - 1, j - 1) + 1
        else:
            memo[i][j] = max(dp(i - 1, j), dp(i, j - 1))

    return memo[i][j]


max = dp(len(s), len(t))

ans = ""

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

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

if len(ans) > 0:
    print("{}".format(ans))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# Input#
# n = int(input())
# n, k = map(int, input().split())
# a = list(map(int, input().split()))

s = input()
t = input()

memo = [[-1 for i in range(len(t) + 1)] for j in range(len(s) + 1)]

for i in range(len(s) + 1):
    memo[i][0] = 0

for i in range(len(t) + 1):
    memo[0][i] = 0


def dp(i, j):
    if memo[i][j] == -1:
        if s[i - 1] == t[j - 1]:
            memo[i][j] = dp(i - 1, j - 1) + 1
        else:
            memo[i][j] = max(dp(i - 1, j), dp(i, j - 1))

    return memo[i][j]


max = dp(len(s), len(t))

ans = ""

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

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


print("{}".format(ans))

Submission status: Runtime Error

Solution code:
from subprocess import*
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
# import numpy as np
starttime = time.time()
# import numpy as np
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    # sys.setrecursionlimit(int(pow(10,6)))
    # sys.stdin = open("input.txt", "r")
    # sys.stdout = open("../output.txt", "w")
except:
    pass
call(('pypy3','-c',"""
s=input()
t=input()
a=len(s)
b=len(t)
dp=[[0]*(b+1) for i in range(a+1)]
for i in range(a):
  for j in range(b):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
res=''
while a!=0 and b!=0:
  if dp[a][b]==dp[a-1][b]:
    a-=1
  elif dp[a][b]==dp[a][b-1]:
    b-=1
  else:
    a-=1
    b-=1
    res=s[a]+res
print(res)
"""))

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
# import numpy as np
starttime = time.time()
# import numpy as np
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    # sys.setrecursionlimit(int(pow(10,6)))
    sys.stdin = open("input.txt", "r")
    # sys.stdout = open("../output.txt", "w")
except:
    pass


s=input()
t=input()
global x,ans
x=[]
ans=[]
def rec(i,j):
    global x,ans
    if len(x)>len(ans):
        ans=x[::]

    if i>=len(s) or j>=len(t):
        return
    if s[i]==t[j]:
        x.append(s[i])
        rec(i+1,j+1)
        x.pop()
        return
    rec(i+1,j)
    rec(i,j+1)
rec(0,0)
print("".join(ans))


endtime = time.time()
# print(f"Runtime of the program is {endtime - starttime}")

Submission status: Runtime Error

Solution code:
def lcs(X , Y): 
    # find the length of the strings 
    m = len(X) 
    n = len(Y) 
  
    # declaring the array for storing the dp values 
    L = [[None]*(n+1) for i in xrange(m+1)] 
  
    """Following steps build L[m+1][n+1] in bottom up fashion 
    Note: L[i][j] contains length of LCS of X[0..i-1] 
    and Y[0..j-1]"""
    for i in range(m+1): 
        for j in range(n+1): 
            if i == 0 or j == 0 : 
                L[i][j] = 0
            elif X[i-1] == Y[j-1]: 
                L[i][j] = L[i-1][j-1]+1
            else: 
                L[i][j] = max(L[i-1][j] , L[i][j-1]) 
  
    # L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1] 
    return L[m][n] 
print(lcs(input(),input()))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(3009)
s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for j in range(m+1)] for i in range(n+1)]
def lcs(i,j):
	if dp[i][j]!=0:
		return dp[i][j]
	if i*j==0:
		return 0
	if s[i-1]==t[j-1]:
		r=lcs(i-1,j-1)+1
	else:
		r=max(lcs(i,j-1),lcs(i-1,j))
	dp[i][j]=r
	return r
		
		

lcs(n,m)

i=n
j=m
st=""
while dp[i][j]:
	while dp[i-1][j]==dp[i][j]:
		i-=1
	while dp[i][j-1]==dp[i][j]:
		j=j-1
	j-=1
	st+=s[i-1]
	i-=1
print(st[::-1])

Submission status: Runtime Error

Solution code:
s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for j in range(m+1)] for i in range(n+1)]
def lcs(i,j):
	if dp[i][j]!=0:
		return dp[i][j]
	if i*j==0:
		return 0
	if s[i-1]==t[j-1]:
		r=lcs(i-1,j-1)+1
	else:
		r=max(lcs(i,j-1),lcs(i-1,j))
	dp[i][j]=r
	return r
		
		

lcs(n,m)

i=n
j=m
st=""
while dp[i][j]:
	while dp[i-1][j]==dp[i][j]:
		i-=1
	while dp[i][j-1]==dp[i][j]:
		j=j-1
	j-=1
	st+=s[i-1]
	i-=1
print(st[::-1])

Submission status: Runtime Error

Solution code:
s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for j in range(m+2)] for i in range(n+2)]
for i in range(1,n+1):
	for j in range(1,m+1):
		if s[i-1]==t[j-1]:
			dp[i][j]=dp[i-1][j-1]+1
		else:
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])
i=n
j=m
st=""
while i>0 and j>0:
	while dp[i-1][j]==dp[i][j]:
		i-=1
	while dp[i][j-1]==dp[i][j]:
		j=j-1
	j-=1
	st+=s[i-1]
	i-=1
print(st[::-1])

Submission status: Runtime Error

Solution code:
from functools import lru_cache

text1 = input()
text2 = input()

@lru_cache(maxsize=None)
def helper(ptr1, ptr2):
    if ptr1 == len(text1) or ptr2 == len(text2):
        return " "
    elif text1[ptr1] == text2[ptr2]:
        return text1[ptr1] + helper(ptr1+1, ptr2+1)
    else:
        a = helper(ptr1+1, ptr2) 
        b = helper(ptr1, ptr2+1)
        return a if len(a) > len(b) else b
        
print(helper(0, 0))

Submission status: Runtime Error

Solution code:
from functools import lru_cache

text1 = input()
text2 = input()

@lru_cache(maxsize=None)
def helper(ptr1, ptr2):
    if ptr1 == len(text1) or ptr2 == len(text2):
        return ""
    elif text1[ptr1] == text2[ptr2]:
        return text1[ptr1] + helper(ptr1+1, ptr2+1)
    else:
        a = helper(ptr1+1, ptr2) 
        b = helper(ptr1, ptr2+1)
        return a if len(a) > len(b) else b
        
print(helper(0, 0))

Submission status: Runtime Error

Solution code:
text1 = input()
text2 = input()
n, m = len(text1), len(text2)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    if text1[i] == text2[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])
return dp[-1][-1]

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(3009)
s=input()
n=len(s)
t=input()
m=len(t)
def lcs(x,y):
	if min(x,y)==-1:
		return ""
	if s[x]==t[y]:
		return lcs(x-1,y-1)+s[x]
	a=lcs(x-1,y)
	b=lcs(x,y-1)
	if len(a)>len(b):
		return a
	else:
		return b
print(lcs(n-1,m-1))

Submission status: Runtime Error

Solution code:
def lcs(X , Y):  
    m = len(X) 
    n = len(Y) 
  
    L = [[None]*(n+1) for i in xrange(m+1)] 
  
    for i in range(m+1): 
        for j in range(n+1): 
            if i == 0 or j == 0 : 
                L[i][j] = ""
            elif X[i-1] == Y[j-1]: 
                L[i][j] = L[i-1][j-1]+ X[i-1]
            else: 
                L[i][j] = max(L[i-1][j] , L[i][j-1]) 
  
    # L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1] 
    return L[m][n] 
#end of function lcs 
  
  
# Driver program to test the above function 
X = str(input())
Y = str(input())
print(lcs(X, Y))

Submission status: Runtime Error

Solution code:
s=['']+list(input())
t=['']+list(input())
ans=''

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

for i in range(s+1):
  for j in range(t+1):
    if s[i]!=t[j]:
      dp[i+1][j]=dp[i][j]
      
    else:
      if dp[i][j]<=dp[i][j-1]+1:
        ans+=s[i]
      
print(dp[-1][-1])

Submission status: Runtime Error

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

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


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

Submission status: Runtime Error

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

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

i, j = n, m

ans = []

while 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])
        i -= 1
        j -= 1

print(reversed(ans))

Submission status: Runtime Error

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

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

i, j = n, m

ans = []

while 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])
        i -= 1
        j -= 1

print(ans)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


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



ans = ""
while si >= 0 or ti >= 0:
    if dp[si][ti] == dp[si - 1][ti - 1] + 1:
        si -= 1
        ti -= 1
        ans = s[si] + ans
    elif dp[si][ti] == dp[si - 1][ti]:
        si -= 1
    else:
        ti -= 1


if len(ans) == 0:
    print("")
else:
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np


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

dp = np.array([[""]*(lt+2)]*(ls+2), dtype=object)
dp2 = np.zeros(((ls+2), (lt+2)))

for i in range(ls):
    flag = 0
    for j in range(lt):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + s[i]
            dp2[i+1][j+1] = dp2[i][j] + 1
        else:
            if dp2[i][j+1] > dp2[i+1][j]:
                dp[i+1][j+1] = dp[i][j+1]
                dp2[i+1][j+1] = dp2[i][j+1]
            else:
                dp[i+1][j+1] = dp[i+1][j]
                dp2[i+1][j+1] = dp2[i+1][j]
print(dp[ls][lt])

Submission status: Runtime Error

Solution code:
import numpy as np


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

dp = np.array([[""]*(ls+2)]*(lt+2), dtype=object)
dp2 = np.zeros(((ls+2), (lt+2)))

for i in range(ls):
    flag = 0
    for j in range(lt):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + s[i]
            dp2[i+1][j+1] = dp2[i][j] + 1
        else:
            if dp2[i][j+1] > dp2[i+1][j]:
                dp[i+1][j+1] = dp[i][j+1]
                dp2[i+1][j+1] = dp2[i][j+1]
            else:
                dp[i+1][j+1] = dp[i+1][j]
                dp2[i+1][j+1] = dp2[i+1][j]
print(dp[ls][lt])

Submission status: Runtime Error

Solution code:
# LCS: Longest common subsequence
# dp[i][j]: Sのi-1番目まで, Tのj-1番目まででの最長共通文字列
# dp[0][0] = 0 長さ0の文字列
# dp[0][1] = 0 長さ1の文字列と長さ0の文字列
# dp[1][0] = 0 長さ0の文字列と長さ1の文字列
# dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (S[i] != T[j])
# dp[i][j] = max(
#                dp[i-1][j-1]+1  (共通文字列を利用する),
#                dp[i-1][j]        (共通文字列を利用しない),
#                dp[i][j-1]        (共通文字列を利用しない),
#            )


dp = [[0 for _ in range(3001)] for _ in range(3001)]


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

    result = solve(S, T)
    print(result)


def solve(S, T):
    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], dp[i][j - 1], dp[i-1][j-1])
            else:
                dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i - 1][j], dp[i][j - 1])
    result = ""
    i = len(S)
    j = len(T)
    while dp[i][j] != 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            result += S[i]
            i -= 1
            j -= 1
    return "".join(reversed(result))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# LCS: Longest common subsequence
# dp[i][j]: Sのi-1番目まで, Tのj-1番目まででの最長共通文字列
# dp[0][0] = 0 長さ0の文字列
# dp[0][1] = 0 長さ1の文字列と長さ0の文字列
# dp[1][0] = 0 長さ0の文字列と長さ1の文字列
# dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (S[i] != T[j])
# dp[i][j] = max(
#                dp[i-1][j-1]+1  (共通文字列を利用する),
#                dp[i-1][j]        (共通文字列を利用しない),
#                dp[i][j-1]        (共通文字列を利用しない),
#            )


dp = [[0 for _ in range(1001)] for _ in range(1001)]

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

    result = solve(S, T)
    print(result)


def solve(S, T):
    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], dp[i][j-1])
            else:
                dp[i][j] = max(dp[i-1][j-1] + 1, dp[i-1][j], dp[i][j-1])
    result = ''
    i = len(S)
    j = len(T)
    while i > 0 and j >0:
        if i >= 1 and j >=1 and dp[i][j] == dp[i-1][j-1] + 1:
            result += S[i-1]
            i -= 1
            j -= 1
        elif i >= 1 and dp[i][j] == dp[i-1][j]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(result))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# LCS: Longest common subsequence
# dp[i][j]: Sのi-1番目まで, Tのj-1番目まででの最長共通文字列
# dp[0][0] = 0 長さ0の文字列
# dp[0][1] = 0 長さ1の文字列と長さ0の文字列
# dp[1][0] = 0 長さ0の文字列と長さ1の文字列
# dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (S[i] != T[j])
# dp[i][j] = max(
#                dp[i-1][j-1]+1  (共通文字列を利用する),
#                dp[i-1][j]        (共通文字列を利用しない),
#                dp[i][j-1]        (共通文字列を利用しない),
#            )


dp = [[[0, ''] for _ in range(1001)] for _ in range(1001)]

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

    result = solve(S, T)
    print(result[1])



def solve(S, T):
    for i, s in enumerate(S, start=1):
        for j, t in enumerate(T, start=1):
            if s != t:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1], key=lambda x: x[0])
            else:
                a = dp[i-1][j-1][0]
                b = dp[i-1][j][0]
                c = dp[i][j-1][0]
                if a >= b and a >= c:
                    dp[i][j] = [dp[i-1][j-1][0] + 1, dp[i-1][j-1][1] + s]
                elif b>=a and b>= c:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1]
    return dp[len(S)][len(T)]


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])
      
def fun(S1,S2,n,m,dp):
    if n == 0 or m == 0:
        return ""
    if dp.get((n,m),-1) != -1:
        return dp[(n,m)]
    else:
        if S1[n-1] == S2[m-1]:
            dp[(n,m)] =  S1[n-1] + fun(S1,S2,n-1,m-1,dp)
        else:
            a = fun(S1,S2,n-1,m,dp)
            b= fun(S1,S2,n,m-1,dp)
            if len(a) > len(b):
                dp[(n,m)] = a
            else:
                dp[(n,m)] = b
        return dp[(n,m)]

S1 = input()
S2 = input()
n = len(S1)
m = len(S2)
s = ""
dp = {}
print(fun(S1,S2,n,m,dp)[::-1])

Submission status: Runtime Error

Solution code:
dp = []
def maior(a, b):
    if len(a) > len(b):
        return a
    else:
        return b

def lcs(i, j, a, b):
    global dp
    if i >= len(a) or j >= len(b):
        return ''

    if dp[i][j] is not None:
        return dp[i][j]

    if a[i] == b[j]:
        dp[i][j] = a[i] + lcs(i + 1, j + 1, a, b)
        return dp[i][j]
    
    dp[i][j] = maior(lcs(i + 1, j, a, b),
                     lcs(i, j + 1, a, b))
    return dp[i][j]

def main():
    global dp
    a = input()
    b = input()
    
    dp = [[None]*len(b) for _ in range(len(a))]

    print(lcs(0, 0, a, b))

main()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

int main(){
     string a,b;
     cin >> a >> b;
     int n = a.size(),m = b.size();
     ll dp[n+1][m+1];
     for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) dp[i][j] = 0;
     for(int i=1;i<=n;i++)
          for(int j=1;j<=m;j++)
               if(a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
               else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
     string ans = "";
     int i = n ,j = m;
     while(i > 0 && j > 0){
          if(dp[i][j] == dp[i-1][j-1] + 1){
            ans += a[i-1];
            i--;
            j--;
          }
          else if(dp[i][j] == dp[i-1][j]) i--;
          else j--;
          
     }
     reverse(ans.begin(),ans.end());
     cout << ans << endl;
     return 0;
}

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
s, t = input(), input()
n, m = len(s), len(t)
dp = [[0]*-~m for _ in [0]*-~n]
for i in range(n):
  for j in range(m):
    dp[i+1][j+1] = dp[i][j] + 1 if s[i] == t[j] else max(dp[i][j+1], dp[i+1][j])
R = ""
while n and m:
  n -= dp[n][m] != dp[n][m-1]
  m -= dp[n][m] != dp[n-1][m]
  R = s[n] + R
print(R)

Submission status: Runtime Error

Solution code:
def LCS(s, t):
    res = ''
    m, n = len(s), len(t)

    def rec(cur, i, j):
        nonlocal res, s, t, m, n
        if i == m or j == n:
            res = max(''.join(cur), res, key=len)
            return

        if s[i] == t[j]:
            cur.append(s[i])
            rec(cur, i+1, j+1)
            cur.pop()
        else:
            rec(cur, i+1, j)
            rec(cur, i, j+1)

    rec([], 0, 0)

    return res


if __name__ == '__main__':

    s = input()
    t = input()

    print(LCS(s, t))

Submission status: Runtime Error

Solution code:
def LCS(s, t):
    res = ''
    m, n = len(s), len(t)

    def rec(cur, i, j):
        nonlocal res, s, t, m, n
        if i == m or j == n:
            res = max(''.join(cur), res, key=len)
            return

        if s[i] == t[j]:
            cur.append(s[i])
            rec(cur, i+1, j+1)
            cur.pop()
        else:
            rec(cur, i+1, j)
            rec(cur, i, j+1)

    rec([], 0, 0)

    return res


s = input()
t = input()

print(LCS(s, t))

Submission status: Runtime Error

Solution code:
import sys


def resolve():
    def max2(a: int, b: int):
        """
        入力された2つの整数a,bの大きいほうを返す
        Parameters
        ----------
        a, b : int
            比較したい整数
        Returns
        -------
        a or b : int
            大きいほうの整数
        """
        if a >= b:
            return a
        else:
            return b
    
    read = sys.stdin.read

    s, t = read().split('\n')
    
    # 配るDP
    # dp[i + 1][j + 1]はsのi文字目までとtのj文字目までのLCSの長さ
    # LCS=最長共通部分列問題
    dp = [[0] * (len(t) + 1) for _ in [0] * (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] = max2(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])

    # LCSを求めたDPから部分文字列を復元
    res = ''
    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:
            res += s[i - 1]
            i -= 1
            j -= 1
    print(res[::-1])


resolve()

Submission status: Runtime Error

Solution code:
import sys


def resolve():
    read = sys.stdin.read

    s, t = read().split('\n')
    
    # 配るDP
    # dp[i + 1][j + 1]はsのi文字目までとtのj文字目までのLCSの長さ
    # LCS=最長共通部分列問題
    dp = [[0] * (len(t) + 1) for _ in [0] * (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])

    # LCSを求めたDPから部分文字列を復元
    res = ''
    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:
            res += s[i - 1]
            i -= 1
            j -= 1
    print(res[::-1])


resolve()

Submission status: Runtime Error

Solution code:
import sys


def resolve():
    read = sys.stdin.read

    s, t = read().split('\n')
    
    # 配るDP
    # dp[i + 1][j + 1]はsのi文字目までとtのj文字目までのLCSの長さ
    # LCS=最長共通部分列問題
    dp = [[0] * (len(t) + 1) for _ in [0] * (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])

    # LCSを求めたDPから部分文字列を復元
    res = ''
    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:
            res += s[i - 1]
            i -= 1
            j -= 1
    print(res[::-1])
    

resolve()

Submission status: Runtime Error

Solution code:
import sys

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


def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)
    txt = ""
    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])

    while lt != 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
            txt = txt + s[ls]

    print(txt[::-1])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

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