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:
import sys
import math
from collections import deque
import copy

input = sys.stdin.readline

s = input()
t = input()

dp = [[0 for _ in range(len(s) + 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]:
            i -= 1
        elif dp[i][l-1] == dp[i][l]:
            l -= 1
        else:
            ans = s[i - 1] + ans
            i -= 1
            l -= 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import deque
import copy

input = sys.stdin.readline

s = input()
t = input()

dp = [[0 for _ in range(len(s) + 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][l] == dp[i - 1][l - 1] + 1:
            ans = s[i - 1] + ans
            i -= 1
            l -= 1
        elif dp[i-1][l] == dp[i][l]:
            i -= 1
        elif dp[i][l-1] == dp[i][l]:
            l -= 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sysinput = sys.stdin.readline

s = input()
t = input()

dp = [[0 for _ in range(len(s) + 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][l] == dp[i - 1][l - 1] + 1:
            ans = s[i - 1] + ans
            i -= 1
            l -= 1
        elif dp[i-1][l] == dp[i][l]:
            i -= 1
        elif dp[i][l-1] == dp[i][l]:
            l -= 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sysinput = sys.stdin.readline

s = input()
t = input()

dp = [[0 for _ in range(len(s) + 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][l] == dp[i - 1][l - 1] + 1:
            ans = s[i - 1] + ans
            i -= 1
            l -= 1
        elif dp[i-1][l] == dp[i][l]:
            i -= 1
        elif dp[i][l-1] == dp[i][l]:
            l -= 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import deque
import copy

input = sys.stdin.readline

s = input()
t = input()

dp = [[0 for _ in range(len(s) + 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][l] == dp[i - 1][l - 1] + 1:
            ans = s[i - 1] + ans
            i -= 1
            l -= 1
        elif dp[i-1][l] == dp[i][l]:
            i -= 1
        elif dp[i][l-1] == dp[i][l]:
            l -= 1
    print(ans)

Submission status: Runtime Error

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


def solve(s: str, t: str):
    ls=len(s)
    lt=len(t)
    dp=[[0]*(lt+1) for _ in range(ls+1)] # dp[0:ls+1][0:lt+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=""
    la=dp[ls][lt]
    ttag=lt
    for i in reversed(range(ls+1)):
        if dp[i][ttag]<la:
            assert(dp[i][ttag]==la-1)
            ans=s[i]+ans
            la-=1
            ttag-=1
    assert(false)
    
    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

def solve(s: str, t: str):
    ls=len(s)
    lt=len(t)
    dp=[[0]*(lt+1) for _ in range(ls+1)] # dp[0:ls+1][0:lt+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=""
    la=dp[ls][lt]
    ttag=lt
    for i in reversed(range(ls+1)):
        if dp[i][ttag]<la:
            ans=s[i]+ans                                                                                                                                                      la-=1
            ttag-=1

    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
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)])

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
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
#import numpy as np
#import sympy as syp(素因数分解とか)
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(): #startline--------------------------------------------
    s = input()
    n = len(s)
    t = input()
    m = len(t)
    dp = [[""]*(m+1) for i in range(n+1)] #dp[i][j]...s_iとt_jの共通部分列の長さ
    for i in range(n+1):
        dp[0][i],dp[i][0] = "",""
    for i in range(n):
        for j in range(m):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+s[i]
            else:
                dp[i+1][j+1] = (dp[i][j+1] if len(dp[i][j+1])>=len(dp[i+1][j]) else dp[i+1][j])
    print(dp[n][m])
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Runtime Error

Solution code:
S = input()
T = input()
r = ""
def dp(S,T,r):
    res = []
    #print("##",S,T,r)
    if len(T) == 0:
        return [r]
    res += dp(S,T[1:],r)
    if T[0] in S:
        r += T[0]
        S = S[S.index(T[0])+1:]
        if len(T) > 1:
            res += dp(S,T[1:],r)
        else:
            return [r]
    return res
R = dp(S,T,r)
ml = (0,"")
for r in R:
    l = len(r)
    if l > ml[0]:
        ml = (l,r)
print(ml[1])

Submission status: Runtime Error

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

ls = len(s)
lt = len(t)
ans = ""
dp = [[0]*(ls+1) for i in range(lt+1)]
memo = [[""]*(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])
        memo[i][j] = memo[i-1][j-1]
        if s[j-1] == t[i-1]:
            dp[i][j] = dp[i-1][j-1]+1
            memo[i][j] = memo[i-1][j-1]+s[j-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)

Submission status: Runtime Error

Solution code:
import itertools
s,t=str(input()),str(input())
x=set("".join(x) for i in range(1,len(s)+1) for x in itertools.combinations(s,i))
y=set("".join(x) for i in range(1,len(s)+1) for x in itertools.combinations(t,i))
z=list(x&y)
l=list(map(len,z))
idx=l.index(max(l))
print(z[idx])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
input=sys.stdin.readline
s=input()
t=input()
n,m=len(s),len(t)

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

for i in range(n):
  for j in range(m):
    if s[i]!=t[j]:
      x=len(dp[i+1][j])
      y=len(dp[i][j+1])
      if x>y:
        dp[i+1][j+1]=dp[i+1][j]
      else:
        dp[i+1][j+1]=dp[i][j+1]
    else:
      x=len(dp[i][j])+1
      y=len(dp[i+1][j])
      z=len(dp[i][j+1])
      tmp=max(x,y,z)
      if x==tmp:
        dp[i+1][j+1]=dp[i][j]+s[i]
      elif  y==tmp:
        dp[i+1][j+1]=dp[i+1][j]
      else:
        dp[i+1][j+1]=dp[i][j+1]
print(dp[n][m])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    S=input()
    T=input()
    dp=[[0]*(len(T)+1) for _ in range(len(S)+1)]
    dp2=[[()]*(len(T)+1) for _ in range(len(S)+1)]
    for s in range(len(S)):
        for t in range(len(T)):
            if S[s]==T[t]:
                dp[s+1][t+1]=dp[s][t]+1
                dp2[s+1][t+1]=(s,t)
            else:
                if dp[s+1][t]>dp[s][t+1]:
                    dp[s+1][t+1]=dp[s+1][t]
                    dp2[s+1][t+1]=dp2[s+1][t]
                else:
                    dp[s+1][t+1]=dp[s][t+1]
                    dp2[s+1][t+1]=dp2[s][t+1]
    tmp=dp2[len(S)][len(T)]
    ans=deque()
    ans.appendleft(S[tmp[0]])
    for _ in range(dp[len(S)][len(T)]-1):
        tmp=dp2[tmp[0]][tmp[1]]
        ans.appendleft(S[tmp[0]])
    print(''.join(ans))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
s = input()
t = input()
LENs = len(s)
LENt = len(t)
dp = [[0 for i in range(LENt+1)] for j in range(LENs+1)]
for i in range(LENs+1):
    for j in range(LENt+1):
        if i+1 <= LENs:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if j+1 <= LENt:
            dp[i][j+1] = max(dp[i][j+1],dp[i][j])
        if i+1 <= LENs and j+1<=LENt:
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+1

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

print(ans)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
LENs = len(s)
LENt = len(t)
dp = [[0 for i in range(LENt+1)] for j in range(LENs+1)]
for i in range(LENs+1):
    for j in range(LENt+1):
        if i+1 <= LENs:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if j+1 <= LENt:
            dp[i][j+1] = max(dp[i][j+1],dp[i][j])
        if i+1 <= LENs and j+1<=LENt:
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+1

ans = ''
x = LENs
y = LENt
while True:
    if dp[y][x] == dp[y-1][x]:
        y = y-1
    elif dp[y][x] == dp[y][x-1]:
        x = x-1
    else:
        ans = s[x-1] + ans       

print(ans)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
LENs = len(s)
LENt = len(t)
dp = [[0 for i in range(LENt+1)] for j in range(LENs+1)]
for i in range(LENs+1):
    for j in range(LENt+1):
        if i+1 <= LENs:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if j+1 <= LENt:
            dp[i][j+1] = max(dp[i][j+1],dp[i][j])
        if i+1 <= LENs and j+1<=LENt:
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+1

ans = ''
x = LENs
y = LENt
while True:
    if len(ans)==dp[-1][-1]:
        break
    if dp[x-1][y] == dp[x][y-1]:
        if dp[x-1][y-1] < dp[x][y]:
            ans.append(s[x-1])
            x = x-1
            y = y-1
            continue
        else:
            x = x-1
            continue
    elif dp[x-1][y] < dp[x][y-1]:
        y = y-1
    elif dp[x-1][y] < dp[x][y-1]:
        x = x-1

print(ans[::-1])

Submission status: Runtime Error

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

def backtrack(dp, s, t, i, j):
    if i == 0 or j == 0:
        return ''
    if s[i-1] == t[j-1]:
        return backtrack(dp, s, t, i-1, j-1) + s[i-1]
    if dp[i][j-1] > dp[i-1][j]:
        return backtrack(dp, s, t, i, j-1)
    return backtrack(dp, s, t, i-1, j)

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

Submission status: Runtime Error

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

import sys
sys.setrecursionlimit(2147483647)

def dfs(i,j):
    if (i,j) in dic: return dic[(i,j)]
    if i > len(S) - 1 or j > len(T) - 1:
        return ""
    ans  = ""
    if S[i] == T[j]:
        ans = S[i] + dfs(i + 1,j + 1)
    else:
        res1 = dfs(i + 1,j)
        res2 = dfs(i, j + 1)
        if max([len(res1),len(res2)]) == len(res1):
            ans = res1
        else:
            ans = res
    dic[(i,j)] = ans
    return ans
dic = {}
print(dfs(0,0))

Submission status: Runtime Error

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


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

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            if len(dp[i][j]) + 1 > len(dp[i][j+1]) and len(dp[i][j]) + 1 > len(dp[i+1][j]):
                dp[i+1][j+1] = dp[i][j] + s[i]
            elif len(dp[i][j+1]) > len(dp[i][j]) + 1 and 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]
        else:
            if len(dp[i+1][j]) > len(dp[i][j+1]):
                dp[i+1][j+1] = dp[i+1][j]
            else:
                dp[i+1][j+1] = dp[i][j+1]

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

Submission status: Runtime Error

Solution code:
def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            if dp[i+k]>dp[i]+abs(H[i+k]-H[i]):
                dp[i+k] = dp[i]+abs(H[i+k]-H[i])
    ans = dp[-1]
    print(ans)
    return

def examC():
    N = I()
    A = [0]*N; B = [0]*N; C = [0]*N
    for i in range(N):
        A[i],B[i],C[i] = LI()
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + A[i]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
    ans = max(dp[N])
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    # https://mzp.hatenadiary.org/entry/20100623/lcs
    # LCS
    def maxBy(f, x, y):
        if f(x) > f(y):
            return x
        else:
            return y
    def lcs(xs, ys, table):
        if (xs, ys) in table:
            return table[(xs, ys)]
        ret = ""
        if xs == "" or ys == "":
            ret = ""
        elif xs[-1] == ys[-1]:
            ret = lcs(xs[:-1], ys[:-1], table) + xs[-1]
        else:
            ret = maxBy(len,
                        lcs(xs[:-1], ys, table),
                        lcs(xs, ys[:-1], table))
        table[(xs, ys)] = ret
        return ret

    S = SI(); N = len(S)
    T = SI(); M = len(T)
    ans = lcs(S,T,{ ("","") : "" })
    print(ans)
    return

def examG():

    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examF()

"""

"""

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

s=ss()
t=ss()
dp = [[0 for i in range(len(s)+1)] for j in range(len(t)+1)] #0で初期化

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

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

Submission status: Runtime Error

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

print(r[::-1])

Submission status: Runtime Error

Solution code:
import numpypy as np

s = input()
t = input()

dp = np.full(t , '')
# dp_len = [0]* len(t)

for i in range(len(s)):
    s_temp = s[i]
    temp_max = ''
    max_len = 0
    for j in range(len(t)):
        before = dp[j]
        if(s_temp == t[j]):
            dp[j] = temp_max + s_temp
        if(max_len < len(before)):
            temp_max = before
            max_len = len(temp_max)

ans = ''
for j in range(len(t)):
    if(len(dp[j]) > len(ans)):
        ans = dp[j]

print(ans)

Submission status: Runtime Error

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

dp = ['']* len(t)
# dp_len = [0]* len(t)

for i in range(len(s)):
    s_temp = s[i]
    temp_max = ''
    for j in range(0, len(t)):
        if(s_temp == t[j]):
            dp_temp = temp_max + s_temp
            print(dp_temp)
        else:
            dp_temp = dp[j]

        if( len(dp[j]) > len(temp_max)):
            temp_max = dp[j]
        dp[j] = dp_temp

if( len(dp_temp) > len(temp_max)):
    temp_max = dp_temp

print(temp_max)

Submission status: Runtime Error

Solution code:
def main():
    s = input()
    t = input()
    mat = [[0 for _ in range(len(s)+2)] for _ in range(len(t)+2)]
    for i in range(1, len(s)+1):
        for j in range(1, len(t)+1):
            if s[i-1] == t[j-1]:
                mat[i][j] = 1 + mat[i-1][j-1]
            else:
                a = mat[i-1][j]
                b = mat[i][j-1]
                if a > b:
                    mat[i][j] = a
                else:
                    mat[i][j] = b
    n = mat[len(s)][len(t)]
    ret = [""] * n
    i = len(s)
    j = len(t)
    while i > 0 and j > 0:
        if mat[i][j] == mat[i-1][j]:
            i -= 1
        elif mat[i][j] == mat[i][j-1]:
            j -= 1
        else:
            ret[n-1] = s[i-1]
            i -= 1
            j -= 1
            n -= 1
    print("".join(ret))


main()

Submission status: Runtime Error

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

ans = [[''] * (len(t)+1)]

for i, a in enumerate(s):
    ans.append([''])
    for j, b in enumerate(t):
        if a == b:
            ans[-1].appned(ans[i][j] + a)
        else:
            if len(ans[i][j+1]) >= len(ans[i+1][j]):
                ans[-1].appned(ans[i][j+1])
            else:
                ans[-1].appned(ans[i][j+1])
            
print(ans[-1][-1])

Submission status: Runtime Error

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

#dp[i][j] => s[i], t[j]までの最長部分文字列

dp = [[0] * (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
        else:
            c, d = dp[i][j-1], dp[i-1][j]
            #上か左の長いほうを入れる
            if c < d:
                dp[i][j] = d
            else:
                dp[i][j] = c
def make_ans(a, b):
    if a < 0 or b < 0:
        return 
    if s[a - 1] == t[b - 1]:
        make_ans(a-1,b-1)
        ans.append(s[a-1])
    else:
        if dp[a - 1][b] > dp[a][b - 1]:
            make_ans(a-1,b)
        else:
            make_ans(a,b-1)

ans = []
make_ans(len(s),len(t))
print("".join(ans))

Submission status: Runtime Error

Solution code:

def maxBy(f, x, y):
    if f(x) > f(y):
        return x
    else:
        return y

table = { ("","") : "" }

def lcs(xs,ys):
    if (xs,ys) in table:
        return table[(xs,ys)]

    ret = ""
    if xs == "" or ys == "":
        ret = ""
    elif xs[-1] == ys[-1]:
        ret = lcs(xs[:-1],ys[:-1]) + xs[-1]
    else:
        ret = maxBy(len,
                    lcs(xs[:-1],ys),
                    lcs(xs,ys[:-1]))
    table[(xs,ys)] = ret
    return ret
s = input()
t = input()
ret = lcs(s,t)
if not ret:
  print("")
  exit()
print (ret)

Submission status: Runtime Error

Solution code:

def maxBy(f, x, y):
    if f(x) > f(y):
        return x
    else:
        return y

table = { ("","") : "" }

def lcs(xs,ys):
    if (xs,ys) in table:
        return table[(xs,ys)]

    ret = ""
    if xs == "" or ys == "":
        ret = ""
    elif xs[-1] == ys[-1]:
        ret = lcs(xs[:-1],ys[:-1]) + xs[-1]
    else:
        ret = maxBy(len,
                    lcs(xs[:-1],ys),
                    lcs(xs,ys[:-1]))
    table[(xs,ys)] = ret
    if not ret:
      print("")
      exit()
    return ret
s = input()
t = input()
print (lcs(s,t))

Submission status: Runtime Error

Solution code:

def maxBy(f, x, y):
    if f(x) > f(y):
        return x
    else:
        return y

table = { ("","") : "" }

def lcs(xs,ys):
    if (xs,ys) in table:
        return table[(xs,ys)]

    ret = ""
    if xs == "" or ys == "":
        ret = ""
    elif xs[-1] == ys[-1]:
        ret = lcs(xs[:-1],ys[:-1]) + xs[-1]
    else:
        ret = maxBy(len,
                    lcs(xs[:-1],ys),
                    lcs(xs,ys[:-1]))
    table[(xs,ys)] = ret
    return ret
s = input()
t = input()
print (lcs(s,t))

Submission status: Runtime Error

Solution code:
# Exercício 15.4-3 - Cormen 3 ed.

s = input()
t = input()
# s = "a" * 3000
# t = "a" * 2980
n = len(s) + 1
m = len(t) + 1
c = [[-1] * (m) for x in [-1] * (n)]

def lcsLengthMemoized(i, j):
    global c
    if c[i][j] != -1:
        return c[i][j]
    if i == 0 or j == 0:
        c[i][j] = 0
        return c[i][j]
    global s, t
    if s[i - 1] == t[j - 1]:
        c[i][j] = lcsLengthMemoized(i - 1, j - 1) + 1
        return c[i][j]
    top_p = lcsLengthMemoized(i - 1, j)
    left_p = lcsLengthMemoized(i, j - 1)
    c[i][j] = max(top_p, left_p)
    return c[i][j]
    
def getLCS(i, j, lcs=""):
    global c
    if c[i][j] == 0:
        return lcs
    global s, t
    if s[i - 1] == t[j - 1]: # volta uma linha e uma coluna
        lcs += getLCS(i - 1, j - 1, lcs)
        lcs += s[i - 1]
        return lcs
    elif c[i - 1][j] > c[i][j - 1]: # volta uma linha na mesma coluna
        lcs += getLCS(i - 1, j, lcs)
    else: # volta uma coluna na mesma linha
        lcs += getLCS(i, j - 1, lcs)
    return lcs

lcsLengthMemoized(n - 1, m - 1)
print(getLCS(n - 1, m - 1))

Submission status: Runtime Error

Solution code:
# Exercício 15.4-3 - Cormen 3 ed.

s = input()
t = input()
n = len(s) + 1
m = len(t) + 1
c = [[-1] * (m) for x in [-1] * (n)]

def lcsLengthMemoized(s, t, i, j):
    global c
    if c[i][j] != -1:
        return c[i][j]
    if i == 0 or j == 0:
        c[i][j] = 0
        return c[i][j]
    if s[i - 1] == t[j - 1]:
        c[i][j] = lcsLengthMemoized(s, t, i - 1, j - 1) + 1
        return c[i][j]
    c[i][j] = max([lcsLengthMemoized(s, t, i - 1, j), lcsLengthMemoized(s, t, i, j - 1)])
    return c[i][j]
    
def getLCS(c, s, t, i, j, lcs=""):
    if c[i][j] == 0:
        return lcs
    if s[i - 1] == t[j - 1]: # volta uma linha e uma coluna
        lcs += getLCS(c, s, t, i - 1, j - 1, lcs)
        lcs += s[i - 1]
        return lcs
    elif c[i - 1][j] > c[i][j - 1]: # volta uma linha na mesma coluna
        lcs += getLCS(c, s, t, i - 1, j, lcs)
    else: # volta uma coluna na mesma linha
        lcs += getLCS(c, s, t, i, j - 1, lcs)
    return lcs

r = lcsLengthMemoized(s, t, n - 1, m - 1)
print(getLCS(c, s, t, n - 1, m - 1))

Submission status: Runtime Error

Solution code:
c = []
direction = []
def lcsLength(s, t):
    n = len(s) + 1
    m = len(t) + 1
    global c, direction
    c = [[-1] * (m) for x in [-1] * (n)]
    direction = [[-1] * (m) for x in [-1] * (n)]
    lcsLengthMemoized(s, t, n - 1, m - 1)
    return direction

def lcsLengthMemoized(s, t, i, j):
    global c
    if c[i][j] == -1:
        if i == 0 or j == 0:
            c[i][j] = 0
            return c[i][j]
        elif s[i - 1] == t[j - 1]:
            c[i][j] = lcsLengthMemoized(s, t, i - 1, j - 1) + 1
            direction[i - 1][j - 1] = 0 # volta uma linha e uma coluna
            return c[i][j]
        else:
            top_p = lcsLengthMemoized(s, t, i - 1, j)
            left_p = lcsLengthMemoized(s, t, i, j - 1)
            if left_p >= top_p:
                c[i][j] = left_p
                direction[i - 1][j - 1] = 1 # volta uma coluna na mesma linha
            else:
                c[i][j] = top_p
                direction[i - 1][j - 1] = 2 # volta uma linha na mesma coluna
            return c[i][j]
    else:
        return c[i][j]

def getLCS(direction, s, i, j, lcs=""):
    if i < 0 or j < 0:
        return lcs
    if direction[i][j] == 0: # volta uma linha e uma coluna
        lcs += getLCS(direction, s, i - 1, j - 1, lcs)
        lcs += s[i]
        return lcs
    elif direction[i][j] == 2: # volta uma linha na mesma coluna
        lcs += getLCS(direction, s, i - 1, j, lcs)
    else: # volta uma coluna na mesma linha
        lcs += getLCS(direction, s, i, j - 1, lcs)
    return lcs

s = input()
t = input()
d = lcsLength(s, t)
print(getLCS(d, s, len(d) - 2, len(d[0]) - 2))

Submission status: Runtime Error

Solution code:

global gaa
global aru
aru = [[ "-" for j in range(3002)] for i in range(3002)]

def depe(a,b,i,j):
    if(i < 0 or j < 0): return ""
    if(aru[i][j] != "-"): return aru[i][j]
    if(a[i] == b[j]):
        aru[i][j] =  a[i] + depe(a,b,i-1,j-1)
    else:
        f = depe(a,b,i,j-1)
        r = depe(a,b,i-1,j)
        if(len(r) > len(f)):
            aru[i][j] = r
        else:
            aru[i][j] = f

    return aru[i][j]

def main():
    a = input()
    b = input()
    ru = depe(a,b,len(a)-1,len(b)-1)
    zz = "".join(reversed(ru))
    print(zz)


main()