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:
a=input()
b=input()
dp=[[0 for i in range(len(a+1))] for j in range(len(b+1))]
for i in range(1,en(a+1)):
  for j in range(1,len(b+1)):
    if a[j-1]==b[i-1]:
      dp[i][j]=dp[i-1][j-1]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])+1
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
s=input()
t=input()
dp=[[-1]*(len(t)+1) for x in range(len(s)+1)]
arr = ""
def func(i,j):
    if i>=(len(s)) or j>=(len(t)):
        dp[i][j]=0
        return dp[i][j]
    if dp[i][j]!=-1:
        return dp[i][j]
    if s[i]==t[j]:
        dp[i][j] = func(i+1,j+1)+1
        return dp[i][j]
    dp[i][j] = max(func(i+1,j),func(i,j+1))
    return dp[i][j]
l=func(0,0)

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

Submission status: Runtime Error

Solution code:
s=input()
t=input()
dp=[[-1]*(len(t)+1) for x in range(len(s)+1)]
arr = ""
def func(i,j):
    if i>=(len(s)) or j>=(len(t)):
        dp[i][j]=0
        return dp[i][j]
    if dp[i][j]!=-1:
        return dp[i][j]
    if s[i]==t[j]:
        dp[i][j] = func(i+1,j+1)+1
        return dp[i][j]
    dp[i][j] = max(func(i+1,j),func(i,j+1))
    return dp[i][j]
l=func(0,0)

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


# for i in range(len(s)-1,-1,-1):
#     for j in range(len(t)-1,-1,-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])
# l=dp[0][0]

Submission status: Runtime Error

Solution code:
s=input()
t=input()
dp=[[-1]*(len(t)+1) for x in range(len(s)+1)]
arr = ""
def func(i,j):
    if i>=(len(s)) or j>=(len(t)):
        dp[i][j]=0
        return dp[i][j]
    if dp[i][j]!=-1:
        return dp[i][j]
    if s[i]==t[j]:
        dp[i][j] = func(i+1,j+1)+1
        return dp[i][j]
    dp[i][j] = max(func(i+1,j),func(i,j+1))
    return dp[i][j]
l=func(0,0)

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


# for i in range(len(s)-1,-1,-1):
#     for j in range(len(t)-1,-1,-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])
# l=dp[0][0]

Submission status: Runtime Error

Solution code:
s=input()
t=input()
dp=[[-1]*(len(t)+1) for x in range(len(s)+1)]
arr = ""
def func(i,j):
    if i>=(len(s)) or j>=(len(t)):
        dp[i][j]=0
        return dp[i][j]
    if dp[i][j]!=-1:
        return dp[i][j]
    if s[i]==t[j]:
        dp[i][j] = func(i+1,j+1)+1
        return dp[i][j]
    if s[i]!=t[j]:
        dp[i][j] = max(func(i+1,j),func(i,j+1))
        return dp[i][j]
l=func(0,0)

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


# for i in range(len(s)-1,-1,-1):
#     for j in range(len(t)-1,-1,-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])
# l=dp[0][0]

Submission status: Runtime Error

Solution code:
s=input()
t=input()
dp=[[-1]*(len(t)+1) for x in range(len(s)+1)]
arr = ""
# for i in range(len(s)-1,-1,-1):
#     for j in range(len(t)-1,-1,-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])
# l=dp[0][0]


def func(i,j):
    if i>=(len(s)) or j>=(len(t)):
        return 0
    if dp[i][j]!=-1:
        return dp[i][j]
    if s[i]==t[j]:
        dp[i][j] = func(i+1,j+1)+1
        return dp[i][j]
    if s[i]!=t[j]:
        dp[i][j] = max(func(i+1,j),func(i,j+1))
        return dp[i][j]
l=func(0,0)

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

Submission status: Runtime Error

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

dp=[[-1]*(len(t)+1) for x in range(len(s)+1)]
arr = ""

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

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

print(arr)



# def func(i,j):
    # if i>=(len(s)) or j>=(len(t)):
    #     return 0
    # if dp[i][j]!=-1:
    #     return dp[i][j]
    # if s[i]==t[j]:
    #     dp[i][j] = func(i+1,j+1)+1
    #     return dp[i][j]
    # if s[i]!=t[j]:
    #     dp[i][j] = max(func(i+1,j),func(i,j+1))
    #     return dp[i][j]
# l=func(0,0)

Submission status: Runtime Error

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

dp=[[-1]*(3001) for x in range(3001)]
arr = ""
def func(i,j):
    if i>=(len(s)) or j>=(len(t)):
        return 0
    if dp[i][j]!=-1:
        return dp[i][j]
    if s[i]==t[j]:
        dp[i][j] = func(i+1,j+1)+1
        return dp[i][j]
    if s[i]!=t[j]:
        dp[i][j] = max(func(i+1,j),func(i,j+1))
        return dp[i][j]
l=func(0,0)
i,j=0,0
while len(arr)!=l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>=dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)

Submission status: Runtime Error

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

dp=[[-1]*(3001) for x in range(3001)]
arr = ""
def func(i,j):
    if i>=(len(s)-1) or j>=(len(t)-1):
        return 0
    if dp[i][j]!=-1:
        return dp[i][j]
    if s[i]==t[j]:
        dp[i][j] = func(i+1,j+1)+1
        return dp[i][j]
    if s[i]!=t[j]:
        dp[i][j] = max(func(i+1,j),func(i,j+1))
        return dp[i][j]
l=func(0,0)
i,j=0,0
while len(arr)<l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>=dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)

Submission status: Runtime Error

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

dp=[[-1]*(3001) for x in range(3001)]
arr = ""
def func(i,j):
    if i>=(len(s)-1) or j>=(len(t)-1):
        return 0
    if dp[i][j]!=-1:
        return dp[i][j]
    if s[i]==t[j]:
        dp[i][j] = func(i+1,j+1)+1
        return dp[i][j]
    if s[i]!=t[j]:
        dp[i][j] = max(func(i+1,j),func(i,j+1))
        return dp[i][j]
l=func(0,0)
i,j=0,0
while len(arr)<l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)

Submission status: Runtime Error

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

dp=[[-1]*(3001) for x in range(3001)]
arr = ""
def func(i,j):
    if i>=len(s) or j>=len(t):
        return 0
    if dp[i][j]!=-1:
        return dp[i][j]
    if s[i]==t[j]:
        dp[i][j] = func(i+1,j+1)+1
        return dp[i][j]
    if s[i]!=t[j]:
        dp[i][j] = max(func(i+1,j),func(i,j+1))
        return dp[i][j]
l=func(0,0)
i,j=0,0
while len(arr)<l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)

Submission status: Runtime Error

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

dp=[[-1]*(len(t)+1) for x in range(len(s)+1)]
arr = ""
def func(i,j):
    if i>=len(s) or j>=len(t):
        return 0
    if dp[i][j]!=-1:
        return dp[i][j]
    if s[i]==t[j]:
        dp[i][j] = func(i+1,j+1)+1
        return dp[i][j]
    if s[i]!=t[j]:
        dp[i][j] = max(func(i+1,j),func(i,j+1))
        return dp[i][j]
l=func(0,0)
i,j=0,0
while len(arr)<l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)

Submission status: Runtime Error

Solution code:
def LCS(ls,ss):
    string = ""

    for x in range(len(ls)):
        for y in ss:
            if ls[x] == y:
                string += ls[x]
                ss.replace(y,"")
    return stringdef LCS(ls,ss):
    string = ""

    for x in range(len(ls)):
        for y in ss:
            if ls[x] == y:
                string += ls[x]
                ss.replace(y,"")
    return string
a = str(input())
b = str(input())
LCS(a,b)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

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

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


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


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


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


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


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


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

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

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

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


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


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


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


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


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


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

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecusionlimit(1000000)

def lcs(s, t):
    if s == '' or t == '':
        return ''
    else:
        if s[0] != t[0]:
            lacks = (lcs(s[1:], t))
            lackt = (lcs(s, t[1:]))
            if len(lacks) > len(lackt):
                return lacks
            else:
                return lackt
        else:
            return s[0] + lcs(s[1:], t[1:])

s = input()
t = input()

print(lcs(s, t))

Submission status: Runtime Error

Solution code:
def lcs(s, t):
    if s == '' or t == '':
        return ''
    else:
        if s[0] != t[0]:
            lacks = (lcs(s[1:], t))
            lackt = (lcs(s, t[1:]))
            if len(lacks) > len(lackt):
                return lacks
            else:
                return lackt
        else:
            return s[0] + lcs(s[1:], t[1:])

s = input()
t = input()

print(lcs(s, t))

Submission status: Runtime Error

Solution code:
a = input()
b = input()
def find(i, j):
    if i == len(a) or j == len(b):
        return ''
    l = str()
    if a[i] == b[j]:
        l += a[i] + find(i+1, j+1)
    else:
        l += max(find(i, j+1), find(i+1, j), key = len)
    return l

print(find(0, 0))

Submission status: Runtime Error

Solution code:
a = input()
b = input()
aa = [s for s in a]
bb = [s for s in b]
na = len(a)
nb = len(b)

dp = [[0]*(nb) for _ in range(na)]
k = 0
for i in range(na):
    if a[i] == b[0]:
        k = 1
    dp[i][0] = k
k = 0
for i in range(nb):
    if b[i] == a[0]:
        k = 1
    dp[0][i] = k

for i in range(1, na):
    for j in range(1, nb):
        if a[i] == b[j]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

ans = []
x = na-1
y = nb-1
while x != 0 or y != 0:
    if x-1 == 0 and dp[x][y] == dp[x-1][y]+1:
        ans.append(a[x])
        x = x-1
    elif y-1 == 0 and dp[x][y] == dp[x][y-1]+1:
        ans.append(b[y])
        y = y-1
    elif x-1 > 0 and dp[x][y] == dp[x-1][y]:
        x = x-1
    elif y-1 > 0 and dp[x][y] == dp[x][y-1]:
        y = y-1
    else:
        ans.append(a[x])
        x = x-1
        y = y-1

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

Submission status: Runtime Error

Solution code:
a = input()
b = input()
aa = [s for s in a]
bb = [s for s in b]
na = len(a)
nb = len(b)

dp = [[0]*(na+1) for _ in range(nb+1)]
k = 0
for i in range(na):
    if a[i] == b[0]:
        k = 1
    dp[i][0] = k
k = 0
for i in range(nb):
    if b[i] == a[0]:
        k = 1
    dp[0][i] = k

for i in range(1, na):
    for j in range(1, nb):
        if a[i] == b[j]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

ans = []
x = na-1
y = nb-1
while x != 0 and y != 0:
    if x-1 >= 0 and dp[x][y] == dp[x-1][y]:
        x = x-1
    elif y-1 >= 0 and dp[x][y] == dp[x][y-1]:
        y = y-1
    else:
        ans.append(a[x])
        x = x-1
        y = y-1
if a[0] == b[0]:
    ans.append(a[0])

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

Submission status: Runtime Error

Solution code:
from sys import stdin, gettrace
 
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()

def recursion(s1,s2,i,j,n1,n2,dp):
    if i>=n1 or j>=n2:
        return ""   
    if s1[i]==s2[j]:
        if dp[i+1][j+1]==-1:
            string=recursion(s1,s2,i+1,j+1,n1,n2,dp)
            dp[i+1][j+1]=string
        else:
            string=dp[i+1][j+1]
        return s1[i]+string
    else:
        if dp[i+1][j]==-1:
            x=recursion(s1,s2,i+1,j,n1,n2,dp)
            dp[i+1][j]=x
        else:
            x=dp[i+1][j]
        if dp[i][j+1]==-1:
            y=recursion(s1,s2,i,j+1,n1,n2,dp)
            dp[i][j+1]=y
        else:
            y=dp[i][j+1]
        if len(x)>len(y):
            return x
        else:
            return y

def main():
    s1=input()
    s2=input()
    n1,n2=len(s1),len(s2)
    dp=[[-1 for j in range(n2+1)] for i in range(n1+1)]
    print(recursion(s1,s2,0,0,len(s1),len(s2),dp))
 
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
s=input()
t=input()
dp=[[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
#print(lcs(s,t,0,0," ",dp))

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

printD(dp,len(t),len(s))

x=len(s)
y=len(t)
ans=""
while x!=0 and y!=0:
    if dp[x-1][y]==dp[x][y]:
        x-=1
    elif dp[x][y-1]==dp[x][y]:
        y-=1
    else:
        ans=t[y-1]+ans
        x-=1
        y-=1
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

####################################################
# LCS(longest common sequence)
# 部分列で最長の共通のもの
####################################################

# dp[i+1][j+1]:= s の i 文字目までと t の j 文字目まででの LCS の長さ

def main():
    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] = max(dp[i+1][j], dp[i][j+1], dp[i][j]+1)
            elif:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
#    print(dp)
#    print(dp[ls][lt])

    # 復元
    res = ''
    i, j = ls, lt
    while (i > 0 and j > 0):
        # (i-1, j) -> (i, j) と更新されていた場合
        if dp[i][j] == dp[i-1][j]:
            i-=1   # DP の遷移を遡る
        # (i, j-1) -> (i, j) と更新されていた場合
        elif dp[i][j] == dp[i][j-1]:
            j-=1   # DP の遷移を遡る
        # (i-1, j-1) -> (i, j) と更新されていた場合
        else:
            res = S[i-1] + res
            # このとき s[i-1] == t[j-1] なので、t[j-1] + res でも OK
            i-=1
            j-=1   # DP の遷移を遡る
    print(res)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
s = input()
t = input()

dp = [[0] * (len(s)+1) for _ in range(len(t)+1)]
for i in range(1, len(t)+1):
    ti = t[i-1]
    dp[i] = dp[i-1]
    for j in range(1, len(s)+1):
        if ti == s[j-1]:
            dp[i][j] = dp[i][j-1] + 1
        else:
            if dp[i][j-1] >= dp[i][j]:
                dp[i][j] = dp[i][j-1]
ans = ''
sl = len(s)
tl = len(t)
while sl > 0 and tl > 0:
    if s[sl-1] == t[tl-1]:
        sl -= 1
        tl -= 1
        ans = s[sl] + ans
        continue

    if dp[tl][sl] == dp[tl][sl-1]:
        sl -= 1
    elif dp[tl][sl] == dp[tl-1][sl]:
        tl -= 1
print(ans)

Submission status: Runtime Error

Solution code:
def solve(s1,s2,n,m,i,j):
    if i==n or j==m:
        return 0
    if s1[i]==s2[j]:
        return 1+solve(s1,s2,n,m,i+1,j+1)
    else:
        return max(solve(s1,s2,n,m,i+1,j),solve(s1,s2,n,m,i,j+1))
s1=input()
s2=input()
n=len(s1)
m=len(s2)
print(solve(s1,s2,n,m,0,0))

Submission status: Runtime Error

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

#dp[i][j] : sをi番目、tをj番目まで読んだ時の共通部分列の長さの最大

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

dp = [["" for _ in range(m)] for _ in range(n)]

def lcs(i,j):
    if i <= -1 or j <= -1:
        return ""
    elif s[i] == t[j]:
        dp[i][j] = lcs(i-1, j-1) + s[i]
        return dp[i][j]
    else:
        c1 = lcs(i-1,j)
        c2 = lcs(i,j-1)
        if len(c1) > len(c2):
            dp[i][j] = c1
        else:
            dp[i][j] = c2
        return dp[i][j]

lcs(n-1, m-1)

print(dp[-1][-1])

Submission status: Runtime Error

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

#dp[i][j] : sをi番目、tをj番目まで読んだ時の共通部分列の長さの最大

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

dp = [["" for _ in range(m)] for _ in range(n)]



def lcs(i,j):
    if i == -1 or j == -1:
        return ""
    elif s[i] == t[j]:
        dp[i][j] = lcs(i-1, j-1) + s[i]
        return dp[i][j]
    else:
        c1 = lcs(i-1,j)
        c2 = lcs(i,j-1)
        if len(c1) > len(c2):
            dp[i][j] = c1
        else:
            dp[i][j] = c2
        return dp[i][j]

lcs(len(s)-1, len(t)-1)

print(dp[-1][-1])

Submission status: Runtime Error

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

#dp[i][j] : sをi番目、tをj番目まで読んだ時の共通部分列の長さの最大

dp = [["" for _ in range(len(t))] for _ in range(len(s))]

import numpy as np

def lcs(i,j):
    if i == -1 or j == -1:
        return ""
    elif s[i] == t[j]:
        dp[i][j] = lcs(i-1, j-1) + s[i]
        return dp[i][j]
    else:
        candi = [lcs(i-1,j), lcs(i,j-1)]
        longer = np.argmax(list(map(len, candi)))
        dp[i][j] = candi[longer]
        return dp[i][j]

lcs(len(s)-1, len(t)-1)
print(dp[-1][-1])

Submission status: Runtime Error

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

#dp[i][j] : sをi番目、tをj番目まで読んだ時の共通部分列の長さの最大

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

import numpy as np

def lcs(i,j):
    if i == -1 or j == -1:
        return ""
    elif s[i] == t[j]:
        dp[i][j] = lcs(i-1, j-1) + s[i]
        return dp[i][j]
    else:
        candi = [lcs(i-1,j), lcs(i,j-1)]
        longer = np.argmax(list(map(len, candi)))
        dp[i][j] = candi[longer]
        return dp[i][j]

lcs(len(s)-1, len(t)-1)
print(dp[-1][-1])

Submission status: Runtime Error

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

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

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

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

while dp[i][j] != 0:
    if s[j-1] == t[i-1]:
        st += s[j-1]
        i -= 1
        j -= 1
    else:
        if dp[i][j-1] > dp[i-1][j]:
            j -= 1
        else:
            i -= 1
            
print(st[::-1])

Submission status: Runtime Error

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

#dp[i][j] : sをi番目、tをj番目まで読んだ時の共通部分列の長さの最大

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

def lcs(i,j):
    global res, pre_i
    if i == -1 or j == -1:
        return 0
    elif s[i] == t[j]:
        if i < pre_i:
            res = res + s[i]
            pre_i = i
        dp[i][j] = lcs(i-1, j-1) + 1
        return dp[i][j]
    else:
        dp[i][j] = max(lcs(i-1,j), lcs(i,j-1))
        return dp[i][j]

lcs(len(s)-1, len(t)-1)

print(res[::-1])

Submission status: Runtime Error

Solution code:
s1=input()
s2=input()
n=len(s1)
m=len(s2)
import numpy as np
dp=[[0 for i in range(m+1)]for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        if s1[i-1]==s2[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# print(np.array(dp))
ans=""
print(dp[-1][-1])
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=s1[i-1]+ans
        i-=1
        j-=1
print(ans)

Submission status: Runtime Error

Solution code:
s1=input()
s2=input()
n=len(s1)
m=len(s2)
import numpy as np
dp=[["" for i in range(m+1)]for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        if s1[i-1]==s2[j-1]:
            dp[i][j]=dp[i-1][j-1]+s1[i-1]
        else:
            a=dp[i-1][j]
            b=dp[i][j-1]
            if len(a)>len(b):
                dp[i][j]=a
            else:
                dp[i][j]=b
# print(np.array(dp))
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
import sys
import math
from  collections import defaultdict

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

def solve(test):
	s = input()
	t = input()
	memo = {}
	ans = lcs(s, t, 0, 0, memo)
	print(ans)

def lcs(s, t, i, j, memo):
	if (i, j) in memo:
		return memo[(i, j)]
	elif i == len(s) or j == len(t):
		return ''
	else:
		ans = ''
		if s[i] == t[j]:
			ans = s[i] + lcs(s, t, i + 1, j + 1, memo)
		else:
			s1 = lcs(s, t, i + 1, j, memo)
			s2 = lcs(s, t, i, j + 1, memo)
			if len(s1) >= len(s2):
				ans = s1
			else:
				ans = s2
		memo[(i, j)] = ans
		return ans


if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
import sys
#import cython
 
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n, m = len(text1), len(text2)
        @lru_cache(None)
        def dp(i, j):
            if i == n or j == m: return 0
            if text1[i] == text2[j]: return dp(i+1, j+1) + 1
            return max(dp(i, j+1), dp(i+1, j))
        return dp(0, 0)
 
def main():
    read = lambda: sys.stdin.readline().rstrip()
    s = input()
    t = input()
    ret = Solution().longestCommonSubsequence(s, t)
    print(ret)
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from functools import lru_cache
import sys
import cython
 
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n, m = len(text1), len(text2)
        @lru_cache(None)
        def dp(i, j):
            if i == n or j == m: return 0
            if text1[i] == text2[j]: return dp(i+1, j+1) + 1
            return max(dp(i, j+1), dp(i+1, j))
        return dp(0, 0)
 
def main():
    read = lambda: sys.stdin.readline().rstrip()
    s = input()
    t = input()
    ret = Solution().longestCommonSubsequence(s, t)
    print(ret)
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from functools import lru_cache
import sys
import cython

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n, m = len(text1), len(text2)
        @lru_cache(None)
        def dp(i, j):
            if i == n or j == m: return 0
            if text1[i] == text2[j]: return dp(i+1, j+1) + 1
            return max(dp(i, j+1), dp(i+1, j))
        return dp(0, 0)

def main():
    read = lambda: sys.stdin.readline().rstrip()
    s, t = map(reaf().split())
   	ret = Solution().longestCommonSubsequence(s, t)
    print(ret)
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
s=input()
t=input()
dp=[[0 for i in range(len(s)+1)] for j in range(len(t)+1)]
for i,sele in enumerate(s):
  for j ,tele in enumerate(t):
    if sele==tele:
      dp[i+1][j+1]=dp[i][j] +1
    else :
      dp[i+1][j+1]=dp[i+1][j] if dp[i+1][j]>=dp[i][j+1] else dp[i][j+1]     
print(dp[len(s)][len(t)])

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
s=input()
t=input()
dp=[["" for i in range(len(s)+1)] for j in range(len(t)+1)]
for i,sele in enumerate(s):
  for j ,tele in enumerate(t):
    if sele==tele:
      dp[i+1][j+1]=dp[i][j] +sele
    else :
      dp[i+1][j+1]=dp[i+1][j] if dp[i+1][j]>=dp[i][j+1] else dp[i][j+1]     
print(dp[len(s)][len(t)])

Submission status: Runtime Error

Solution code:
s=input()
t=input()
x=len(s)
y=len(t)
dp=[[0 for i in range(y)] for i in range(x)]
xi=[0 for i in range(x)]
yi=[0 for i in range(y)]
xo=""
for i in range(x-1,-1,-1):
	xo=xo+s[i]
	xi[i]=xo
xo=""
for i in range(y-1,-1,-1):
	xo=xo+t[i]
	yi[i]=xo
for i in range(x):
	if(t[-1] in xi[i]):
		dp[i][y-1]=t[-1]
	else:
		dp[i][y-1]=""
for j in range(y):
	if(s[-1] in yi[i]):
		dp[x-1][j]=s[-1]
	else:
		dp[x-1][j]=""
if(s[-1]==t[-1]):
	dp[x-1][y-1]=t[-1]
else:
	dp[x-1][y-1]=""
for i in range(x-2,-1,-1):
	for j in range(y-2,-1,-1):
		if(s[i]==t[j]):
			dp[i][j]=s[i]+dp[i+1][j+1]
		else:
			if(len(dp[i+1][j])>len(dp[i][j+1])):
				dp[i][j]=dp[i+1][j]
			else:
				dp[i][j]=dp[i][j+1]
print(dp[0][0])

Submission status: Runtime Error

Solution code:
s=input()
t=input()
x=len(s)
y=len(t)
dp=[[0 for i in range(y)] for i in range(x)]
xi=[0 for i in range(x)]
yi=[0 for i in range(y)]
xo=""
for i in range(x-1,-1,0):
	xo=xo+s[i]
	xi[i]=xo
xo=""
for i in range(y-1,-1,0):
	xo=xo+t[i]
	yi[i]=xo
for i in range(x):
	if(t[-1] in xi[i]):
		dp[i][y-1]=t[-1]
	else:
		dp[i][y-1]=""
for j in range(y):
	if(s[-1] in yi[i]):
		dp[x-1][j]=s[-1]
	else:
		dp[x-1][j]=""
if(s[-1]==t[-1]):
	dp[x-1][y-1]=t[-1]
else:
	dp[x-1][y-1]=""
for i in range(x-2,-1,-1):
	for j in range(y-2,-1,-1):
		if(s[i]==t[j]):
			dp[i][j]=s[i]+dp[i+1][j+1]
		else:
			if(len(dp[i+1][j])>len(dp[i][j+1])):
				dp[i][j]=dp[i+1][j]
			else:
				dp[i][j]=dp[i][j+1]
print(dp[0][0])

Submission status: Runtime Error

Solution code:
x = input()
y = input()
n = len(x)
m = len(y)
a = [[-1 for i in range(m+1)] for j in  range(n+1)]
def lcs(x,y,n,m):
    s = set()
    if m ==0 or n ==0:
        return ""
    if a[n][m]!=-1:
        return a[n][m]
    
    if x[n-1]==y[m-1]:
        result =x[n-1]+lcs(x,y,n-1,m-1)
    elif x[n-1]!=y[m-1]:
        result = max(lcs(x,y,n-1,m),lcs(x,y,n,m-1),key=len)
    a[n][m]=result
    return result
print(lcs(x,y,n,m)[::-1])

Submission status: Runtime Error

Solution code:
import sys

def lcs(s, t, i, j, dp, strn, len_s):

    if i >= len(s) or j >= len(t):
        return len_s, strn

    if s[i] == t[j]:

        a, b = lcs(s, t, i + 1, j + 1, dp, strn + s[i], len_s + 1)
        dp[(i, j)] = (a, b)
        return dp[(i, j)]

    a1, b1 = lcs(s, t, i, j + 1, dp, strn, len_s)
    a2, b2 = lcs(s, t, i + 1, j, dp, strn, len_s)

    if a1 > a2:
        dp[(i, j)] = (a1, b1)
        return dp[(i, j)]

    dp[(i, j)] = ((a2, b2))
    return dp[(i, j)]

s =  sys.stdin.readline().strip()
t =  sys.stdin.readline().strip()
dp = {}
sys.stdout.write(str(lcs(s, t, 0, 0, dp, "", 0)[1]))