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 copy,bisect

s=input()
N=len(s)
t=input()
M=len(t)

dp=[[0 for i in range(0,M)] for i in range(0,N)]

for i in range(0,N):
    if s[0:i+1].count(t[0])>0:
        dp[i][0]=1

for i in range(0,M):
    if t[0:i+1].count(s[0])>0:
        dp[0][i]=1

for i in range(1,N):
    for j in range(1,M):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            if dp[i][j-1])>dp[i-1][j]:
                dp[i][j]=dp[i][j-1]
            else:
                dp[i][j]=dp[i-1][j]

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

Submission status: Runtime Error

Solution code:
import copy,bisect

s=input()
N=len(s)
t=input()
M=len(t)

dp=[[0 for i in range(0,M)] for i in range(0,N)]

for i in range(0,N):
    if s[0:i+1].count(t[0])>0:
        dp[i][0]=1

for i in range(0,M):
    if t[0:i+1].count(s[0])>0:
        dp[0][i]=1

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

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

Submission status: Runtime Error

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

ns=len(s)
nt=len(t)
dp=np.zeros((ns+1,nt+1),np.int64)
pp=np.full((ns+1,nt+1),'')
ppd={0:'c',1:'l',2:'u'}
for i in range(ns):
  for j in range(nt):
    a=np.array([dp[i][j]+1 if s[i]==t[j] else -1,dp[i+1][j],dp[i][j+1]])
    dp[i+1][j+1]=np.max(a)
    pp[i+1][j+1]=ppd[np.argmax(a)]

i=ns
j=nt
ans=[]
while i>0 and j>0:
  sw=pp[i][j]
  if sw=='c':
        i-=1
        j-=1
        ans.append(s[i])
  elif sw=='l':
        j-=1
  elif sw=='u':
        i-=1
ans1=''
for _ in range(len(ans)):
      ans1+=ans.pop()
print(ans1)

Submission status: Runtime Error

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

"""
dp[i+1][j+1]:sのi文字目までとtのj文字目まででの LCS の長さ
dp[i+1][j+1]をdp[i][j],dp[i][j+1],dp[i][j+1]を使って表現する。
dp[i+1][j+1]=max(dp[i][j]+1 if s[i]==t[j] else 0,dp[i+1][j],dp[i][j+1])
"""
ns=len(s)
nt=len(t)
dp=np.zeros((ns+1,nt+1),np.int64)
pp=np.full((ns+1,nt+1),'')
ppd={0:'c',1:'l',2:'u'}
for i in range(ns):
  for j in range(nt):
    a=np.array([dp[i][j]+1 if s[i]==t[j] else -1,dp[i+1][j],dp[i][j+1]])
    dp[i+1][j+1]=np.max(a)
    pp[i+1][j+1]=ppd[np.argmax(a)]

i=ns
j=nt
ans=[]
while i>0 and j>0:
  sw=pp[i][j]
  if sw=='c':
        i-=1
        j-=1
        ans.append(s[i])
  elif sw=='l':
        j-=1
  elif sw=='u':
        i-=1
ans1=''
for _ in range(len(ans)):
      ans1+=ans.pop()
print(ans1)

Submission status: Runtime Error

Solution code:
X = input()
Y = input()
x = len(X)
y = len(Y)

dp = [[0 for _ in range(y + 1)] for _ in range(x + 1)]
for i in range(x):
	for j in range(y):
		if X[i] == Y[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])

print(dp[x][y])

Submission status: Runtime Error

Solution code:
#Template 1.0
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
def list2d(a, b, c): return [[c] * b for i in range(a)]
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

# start your code here:

def solve(i, j):
    if(i==Ls or j==Lt):
        return ""
    elif(s[i]==t[j]):
        if(dp[i][j]==-1):
            foo = str(s[i]) + solve(i+1, j+1)
            dp[i][j] = foo
            return foo
        else:
            return dp[i][j]
    else:
        if(dp[i][j]==-1):
            temp1 = solve(i+1, j)
            temp2 = solve(i, j+1)

            if(len(temp1)>len(temp2)):
                dp[i][j] = temp1
                return temp1
            dp[i][j] = temp2
            return temp2
        else:
            return dp[i][j]

s = STR()
t = STR()
Ls = len(s)
Lt = len(t)
dp = list2d(3001, 3001, -1)
print(solve(0, 0))

Submission status: Runtime Error

Solution code:
def main():
    s = input()
    t = input()
    dp = [[0] * len(s) for _ in range(len(t))]
    for i,x in enumerate(s):
        for j,y in enumerate(t):
            if i == 0:
                dp[i][j] = 1 if x in t[:j+1] else 0
            elif j == 0:
                dp[i][j] = 1 if y in s[:i+1] else 0
            elif x == y:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    print(dp[len(s)-1][len(t)-1])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
if __name__ == "__main__":
    s, t = input(), input()
    ans = lcs(t, s)

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

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

    i, j = len(t), len(s)
    ans = []

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

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

Submission status: Runtime Error

Solution code:
s=input()
t=input()
dp=[["" for i in range(len(t)+1)] for j in range(len(s)+1)]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1]==t[j-1]:
            dp[i][j]="".join(dp[i-1][j-1],s[i-1])
        else:
            A=len(dp[i-1][j])
            B=len(dp[i][j-1])
            if A>=B:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=dp[i][j-1]
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
s=input()
t=input()
n=len(s)
m=len(t)
#print(n,m)
dp=[[0]*3300 for i in range(3300)]

for i in range(n+1):
  for j in range(m+1):
    if (i==0 | j==0):
      dp[i][j]=0
      continue
    dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    if (s[i-1]==t[j-1]):
      dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j])
#print(dp[n][m])  
rewsna=''

while (n>0 and m>0):
  if (dp[n][m]==dp[n-1][m]):
    n-=1
  elif (dp[n][m]==dp[n][m-1]):
    m-=1
  else:
    rewsna+=s[n-1]
    n-=1
    m-=1
    #print(rewsna)
ans=[] 
l=len(rewsna)
for i in range(l+1):
  ans.append(rewsna[l-i-1])
print(''.join(ans))

Submission status: Runtime Error

Solution code:
def solve(X,Y):
    res=''
    n,m=len(X),len(Y)
    dp=[[0]*(m+1) for i in range(m+1)]
    for i in range(n):
        for j in range(m):
            if(X[i]==Y[j]):
                dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1)
            dp[i+1][j+1]=max([dp[i+1][j+1],dp[i][j+1],dp[i+1][j]])
    i,j=i+1,j+1
    while(i>0 and j>0):
        if(dp[i][j]==dp[i-1][j]):
            i-=1
        elif(dp[i][j]==dp[i][j-1]):
            j-=1
        else:
            i-=1;j-=1
            res+=X[i]
    return res[::-1]

def main():
    X=input()
    Y=input()
    print(solve(X,Y))

if __name__=='__main__':
    main()

Submission status: Runtime Error

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

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

i1,i2 = len(s),len(t)

rev_ans = ""
while i1 != 0:
    lru = dp[i2-1][i1-1]
    now = dp[i2][i1]
    #  print(lru,now)
    if now - lru == 1:
        rev_ans += t[i2-1]
        i2 -= 1
        i1 -= 1
    elif now - dp[i2-1][i1] == 0:
        i2 -= 1
    else:
        i1 -= 1

for c in reversed(rev_ans):
    print(c,end='')

Submission status: Runtime Error

Solution code:
S=input()
T=input()
N=len(S)
M=len(T)
dp=[""]*(N+1)
for i in range(M):
  cp=[""]*(M+1)
  for j in range(N):
    if len(cp[j])>len(dp[j+1]):
      cp[j+1]=cp[j]
    else:
      cp[j+1]=dp[j+1]
    if T[i]==S[j] and len(dp[j])+1>len(cp[j+1]):
      cp[j+1]=dp[j]+S[j]
  for j in range(N+1):
    dp[j]=cp[j]
print(dp[N])

Submission status: Runtime Error

Solution code:
S = input()
T = input()
m, n = len(S), len(T)
C = [[0 for j in range(n+1)] for i in range(m+1)]
for i in range(m):
    for j in range(n):
        if S[i] == T[j]:
            C[i+1][j+1] = C[i][j] + 1
        else:
            C[i+1][j+1] = max(C[i][j+1], C[i+1][j])
X = ''
i, j, k = 0, 0, 0
while k < C[m][n]:
    if S[i] == T[j]:
        X = X + S[i]
        i += 1
        j += 1
        k += 1
    elif C[i+1][j] == C[i][j]:
        i += 1
    else:
        j += 1
print(X)

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

Solution code:
s = input()
t = input()
lenS = len(s)
lenT = len(t)

dp = [[0]*(lenT+1)for _ in range(lenS+1)]

for i in range(1,lenS+1):
  for j in range(1,lenT+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])
      
m = lenS
n = lenT
ans = ""
while m or n:
  if dp[m][n] == dp[m-1][n]:
    m -= 1
    continue
  elif dp[m][n] == dp[m][n-1]:
    n -= 1
    continue
  else:
    m -= 1
    n -= 1
    ans = "".join([s[m],ans])
    continue
print(ans)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
lenS = len(s)
lenT = len(t)

dp = [[0]*(lenT+1)for _ in range(lenS+1)]

for i in range(1,lenS+1):
  for j in range(1,lenT+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])
      
m = lenS
n = lenT
ans = ""
while m or n:
  if dp[m][n] == dp[m-1][n]:
    m -= 1
    continue
  elif dp[m][n] == dp[m][n-1]:
    n -= 1
    continue
  else:
    m -= 1
    n -= 1
    ans = "".join([s[m],ans])
    continue
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(200000)

X = input()
Y = input()
lenX = len(X)
lenY = len(Y)
dp = np.full((lenX+1,lenY+1),"-1",dtype=object)
dp[0,:]=""
dp[:,0]=""
def f(i,j):
  if dp[i][j]=="-1":
    x = X[i-1]
    y = Y[j-1]
    lo = f(i-1,j-1)
    l = f(i,j-1)
    o = f(i-1,j)
    if x==y:
      dp[i][j]="".join([lo,x])
    else:
      if len(l)>=len(o):
        dp[i][j]=l
      else:
        dp[i][j]=o
  return dp[i][j]

print(f(lenX,lenY))

Submission status: Runtime Error

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

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

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

ans = ""
while m > 0 and n > 0:
    if dp[m][n] == dp[m-1][n]:
        m -= 1
    elif dp[m][n] == dp[m][n-1]:
        n -= 1
    elif dp[m][n] == dp[m-1][n-1] + 1:
        ans += t[n-1]
        m -= 1
        n -= 1

print(ans[::-1])

Submission status: Runtime Error

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

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

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

ans = ""
while m > 0 and n > 0:
    if dp[m][n] == dp[m-1][n]:
        m -= 1
    elif dp[m][n] == dp[m][n-1]:
        n -= 1
    elif dp[m][n] == dp[m-1][n-1] + 1:
        ans += t[n-1]
        m -= 1
        n -= 1

print(ans[::-1])

Submission status: Runtime Error

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

#output
m = len(s)
n = len(t)
dp = [[0]*(ls+1) for _ in range(lt+1)]

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

ans = ""
while m > 0 and n > 0:
    if dp[m][n] == dp[m-1][n]:
        m -= 1
    elif dp[m][n] == dp[m][n-1]:
        n -= 1
    elif dp[m][n] == dp[m-1][n-1] + 1:
        ans += t[n-1]
        m -= 1
        n -= 1

print(ans[::-1])

Submission status: Runtime Error

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

#output
import numpy as np
m = len(s)
n = len(t)
dp = np.zeros((m+1, n+1), int)

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

ans = ""
while m > 0 and n > 0:
    if dp[m, n] == dp[m-1, n]:
        m -= 1
    elif dp[m, n] == dp[m, n-1]:
        n -= 1
    elif dp[m, n] == dp[m-1, n-1] + 1:
        ans += t[n-1]
        m -= 1
        n -= 1

print(ans[::-1])

Submission status: Runtime Error

Solution code:
def lcs(s,t,i,j,dp):
	if i>=len(s) or j>=len(t):
		return 0
	if dp[i][j]>-1:
		return dp[i][j]
	if s[i]==t[j]:
		ans =  1+lcs(s,t,i+1,j+1,dp)
	else:
		ans = max(lcs(s,t,i,j+1,dp),lcs(s,t,i+1,j,dp))
	dp[i][j] = ans
	return ans
s = input()
t = input()
dp = [[-1]*len(t) for i in range(len(s))]
i,j = 0,0
string = ''
lcs(s,t,0,0,dp)
while i < len(s)-1 and j < len(t)-1:  
		if s[i] == t[j]: 
			string+=t[j]   
			i+=1
			j+=1
		elif dp[i+1][j] > dp[i][j+1]: 
			i+=1
		else: 
			j+=1
if i==len(s)-1 and j==len(t)-1:
	if s[i]==t[j]:
		string+=t[j]
elif i < len(s)-1:
	while i< len(s):
		if s[i]==t[j]:
			string+=s[i]
		i+=1
elif j < len(t)-1:
	while j < len(t):
		if s[i]==t[j]:
			string+=s[i]
		j+=1
print(string)

Submission status: Runtime Error

Solution code:
def lcs(s,t,i,j,dp):
	if i>=len(s) or j>=len(t):
		return 0
	if dp[i][j]>-1:
		return dp[i][j]
	if s[i]==t[j]:
		ans =  1+lcs(s,t,i+1,j+1,dp)
	else:
		ans = max(lcs(s,t,i,j+1,dp),lcs(s,t,i+1,j,dp))
	dp[i][j] = ans
	return ans
s = input()
t = input()
dp = [[-1]*3000 for i in range(3000)]
i,j = 0,0
ans = ''
lcs(s,t,0,0,dp)
while(i!=len(s)-1 and j!=len(t)-1):
	if t[i]==s[j]:
		ans+=t[i]
		i+=1
		j+=1
	elif dp[i+1][j]<dp[i][j+1]:
		j+=1
	else:
		i+=1
while j<len(t)-1:
	if t[j+1]==s[i]:
		ans+=t[j+1]
	j+=1
while i<len(s)-1:
	if s[i+1]==t[j]:
		ans+=t[j+1]
	i+=1
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
X = input()
Y = input()
lenX = len(X)
lenY = len(Y)
dp = np.full((lenX+1,lenY+1),"-1",dtype=object)
dp[0,:]=""
dp[:,0]=""
def f(i,j):
  if dp[i][j]=="-1":
    x = X[i-1]
    y = Y[j-1]
    lo = f(i-1,j-1)
    l = f(i,j-1)
    o = f(i-1,j)
    if x==y:
      dp[i][j]="".join([lo,x])
    else:
      if len(l)>=len(o):
        dp[i][j]=l
      else:
        dp[i][j]=o
  return dp[i][j]
print(f(lenX,lenY))

Submission status: Runtime Error

Solution code:
import numpy as np

q = int(input())
for k in range(q):
  X = input()
  Y = input()
  lenX = len(X)
  lenY = len(Y)
  dp = np.full((lenX+1,lenY+1),-1)
  dp[0,:]=0
  dp[:,0]=0
  def f(i,j):
    if dp[i][j]==-1:
      x = X[i-1]
      y = Y[j-1]
      if x==y:
        dp[i][j]=max(f(i-1,j-1)+1,f(i-1,j),f(i,j-1))
      else:
        dp[i][j]=max(f(i-1,j),f(i,j-1))
    return dp[i][j]
  print(int(f(lenX,lenY)))

Submission status: Runtime Error

Solution code:
import numpy as np

s = input()
t = input()
len_s, len_t = len(s), len(t)
dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
for index_s in range(len_s):
  char_s = s[index_s]
  dp_s = dp[index_s]
  dp_ss = dp[index_s + 1]
  for index_t in range(len_t):
    if char_s == t[index_t]:
      dp_ss[index_t + 1] = dp_s[index_t] + 1
    else:
      dp_ss[index_t + 1] = max(dp_s[index_t + 1], dp_ss[index_t])
index_s, index_t = len_s - 1, len_t - 1
lcs_reverse = []
len_lcs = dp[-1, -1]
while len_lcs > 0:
  if s[index_s] == t[index_t]:
    lcs_reverse.append(s[index_s])
    index_s -= 1
    index_t -= 1
    len_lcs -= 1
  elif dp[index_s][index_t + 1] == len_lcs:
    index_s -= 1
  else:
    index_t -= 1
print(''.join(lcs_reverse[::-1]))

Submission status: Runtime Error

Solution code:
def get_lcs(S: str, T: str):
    N, M = len(S), len(T)
    dp = [[0] * (M + 1) for _ in range(N + 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 + 1][j], dp[i][j + 1])

    reversed_lcs = ""
    while N and M:
        if S[N - 1] == T[M - 1]:
            N -= 1
            M -= 1
            reversed_lcs += S[N]
        if dp[N - 1][M] > dp[N][M - 1]:
            N -= 1
        else:
            M -= 1
    return reversed_lcs[::-1]


def main():
    S, T = open(0).read().split()
    print(get_lcs(S, T))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = 0
m = []

def lcs(s, t, a, b, ans):
    global n
    global m
    if a == 0 or b == 0:
        return 0;
    elif s[a-1] == t[b-1]:
        ans.append(s[a-1])
        owo = 1 + lcs(s, t, a-1, b-1, ans)
        if owo > n:
            n = owo
            m = ans.copy()
        return owo
    else:
        return max(lcs(s, t, a-1, b, ans), lcs(s, t, a, b-1, ans))

s = [char for char in input()]
t = [char for char in input()]


l = lcs(s, t, len(s), len(t), [])

for a in range(l-1, -1, -1):
    print(m[a], end="")

Submission status: Runtime Error

Solution code:
n = 0
m = []

def lcs(s, t, a, b, ans):
    global n
    global m
    if a == 0 or b == 0:
        return 0;
    elif s[a-1] == t[b-1]:
        ans.append(s[a-1])
        owo = 1 + lcs(s, t, a-1, b-1, ans)
        if owo > n:
            n = owo
            m = ans
        return owo
    else:
        return max(lcs(s, t, a-1, b, ans), lcs(s, t, a, b-1, ans))

s = [char for char in input()]
t = [char for char in input()]


l = lcs(s, t, len(s), len(t), [])

for a in range(l-1, -1, -1):
    print(m[a], end="")

Submission status: Runtime Error

Solution code:
from itertools import product


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


def lcs(s, t):
    S = len(s)
    T = len(t)
    dp = [[0 for j in range(T+1)] for i in range(S+1)]
    maxpos = (0, 0)
    for i, j in product(range(S), range(T)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
            if dp[maxpos[0]+1][maxpos[1]+1] < dp[i+1][j+1]:
                maxpos = (i, j)
        else:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])
    return maxpos, dp


def dfs(s, t, i, j, dp):
    if i < 0 or j < 0:
        return list()
    if s[i] == t[j]:
        x = dfs(s, t, i-1, j-1, dp)
        return x + [i]
    else:
        x = dfs(s, t, i-1, j, dp)
        y = dfs(s, t, i, j-1, dp)
        return x if len(x) > len(y) else y


def solve(s, t):
    maxpos, dp = lcs(s, t)
    i, j = maxpos
    x = dfs(s, t, i, j, dp)
    ans = ''.join([s[i] for i in x])
    return ans


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Runtime Error

Solution code:
from itertools import product
from collections import deque


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


def lcs(s, t):
    S = len(s)
    T = len(t)
    dp = [[0 for j in range(T+1)] for i in range(S+1)]
    maxpos = (0, 0)
    for i, j in product(range(S), range(T)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
            if dp[maxpos[0]+1][maxpos[1]+1] < dp[i+1][j+1]:
                maxpos = (i, j)
        else:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])
    return maxpos, dp


def dfs(s, t, i, j, dp):
    if i < 0 or j < 0:
        return list()
    if s[i] == t[j]:
        x = dfs(s, t, i-1, j-1, dp)
        return x + [i]
    else:
        x = dfs(s, t, i-1, j, dp)
        y = dfs(s, t, i, j-1, dp)
        return x if len(x) > len(y) else y


def solve(s, t):
    maxpos, dp = lcs(s, t)
    x = dfs(s, t, *maxpos, dp)
    ans = ''.join([s[i] for i in x])
    return ans


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Runtime Error

Solution code:
'''
    Auther: ghoshashis545 Ashis Ghosh
    college: jalpaiguri Govt Enggineering College
    Date:12/03/2020
'''

s=input()
t=input()
Mxn=3005
dp=[["" for i in range(Mxn)] for j in range(Mxn)] 
n=len(s)
m=len(t)
for i in range(n+1):
    for j in range(m+1):
        if(i==0 or j==0):
            dp[i][j]=""
        elif(s[i-1]==t[j-1]):
            dp[i][j]=dp[i-1][j-1]+s[i-1]
        else:
            if(len(dp[i][j-1])<len(dp[i-1][j])):
                dp[i][j]=dp[i-1][j-1]
            else:
                dp[i][j]=dp[i][j-1]
print(dp[n][m])

Submission status: Runtime Error

Solution code:
'''
    Auther: ghoshashis545 Ashis Ghosh
    college: jalpaiguri Govt Enggineering College
    Date:14/03/2020
'''

s=input()
t=input()
Mxn=3000
dp=[["" for i in range(Mxn)] for j in range(Mxn)] 
n=len(s)
m=len(t)
for i in range(n+1):
    for j in range(m+1):
        if(i==0 or j==0):
            dp[i][j]=""
        elif(s[i-1]==t[j-1]):
            dp[i][j]=dp[i-1][j-1]+s[i-1]
        else:
            if(len(dp[i][j-1])<len(dp[i-1][j])):
                dp[i][j]=dp[i-1][j-1]
            else:
                dp[i][j]=dp[i][j-1]
print(dp[n][m])

Submission status: Runtime Error

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

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

res = ''
i, j = m, n
while i > 0 and j > 0:
  if dp[i][j] == dp[i-1][j]:
    i -= 1
  elif dp[i][j] == dp[i][j-1]:
    j -= 1
  else:
    i -= 1
    j -= 1
    res = s[i] + res
print(res)

Submission status: Runtime Error

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

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

res = ''
i, j = m, n
while i > 0 and j > 0:
  if dp[i][j] == dp[i-1][j]:
    i -= 1
  elif dp[i][j] == dp[i][j-1]:
    j -= 1
  else:
    i -= 1
    j -= 1
    res += s[i]
print(res[::-1])

Submission status: Runtime Error

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

#import numpy as np
#print(np.array(dp))

#from collections import deque
#ans = deque()

ans = []
i, j = ls, lt
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        i -= 1
        j -= 1
        #ans.appendleft(s[i])
        ans = s[i] + ans
#print(''.join(ans))
print(ans)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
dp = [[0]*(len(t)+1) for i in range(len(s)+1)]
#dp[i+1][j+1]sのi文字目までとtのj文字目までを比較したときのLCS
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j]+1
        else:
            dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])

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

Submission status: Runtime Error

Solution code:
A = input()
B = input()

dp = [[None] * (len(B) + 1) for _ in range(len(A) + 1)]
def dfs(a=0, b=0):
    if a >= len(A) or b >= len(B):
        return 0

    if dp[a][b] is not None:
        return dp[a][b]

    match = A[a] == B[b]
    if match:
        r = dfs(a + 1, b + 1) + 1
    else:
        r = max(dfs(a + 1, b), dfs(a, b + 1))
    dp[a][b] = r
    return r

dfs()
# print(dfs())
# print(dp)

# print("---")
# for v in dp:
#     print(*map(lambda x: x if x is not None else "*", v))

def or_inf(v):
    return float('inf') if v is None else v

def reconst(a=0, b=0):
    if a >= len(A) or b >= len(B):
        return ''

    match = A[a] == B[b]
    if match:
        return reconst(a + 1, b + 1) + A[a]
    else:
        if or_inf(dp[a + 1][b]) >= or_inf(dp[a][b + 1]):
            return reconst(a + 1, b)
        else:
            return reconst(a, b + 1)
print(reconst()[::-1])

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
import numpy as np
from itertools import accumulate

s = np.array(list(input()), np.unicode)
sl = len(s)
t = np.array(list(input()), np.unicode)
tl = len(t)
equal = (s[:, None] == t[None, :])

dp = [np.zeros(tl + 1, np.int32)]
for i in range(sl):
    tmp = dp[-1].copy()
    np.maximum(tmp[1:], tmp[:-1] + equal[i], out=tmp[1:])
    tmp = accumulate(tmp)
    dp.append(tmp)

answer = ''
while sl > 0 and tl > 0:
    if s[sl - 1] == t[tl - 1]:
        sl -= 1
        tl -= 1
        answer += s[sl]
        continue

    if dp[sl - 1][tl] > dp[sl][tl - 1]:
        sl -= 1
    else:
        tl -= 1

print(answer[::-1])

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
s=list(input())
t=list(input())
n=len(s)
m=len(t)
dp=[[[] for i in range(m+1)] for j in range(n+1)]
#dps=[[0 for i in range(m+1)] for j 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].append(s[i])
            #dps[i+1][j+1]=dps[i][j]+1
        else:
            if len(dp[i+1][j])>len(dp[i][j+1]):
                dp[i+1][j+1]=dp[i+1][j]
                #dps[i+1][j+1]=dps[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]
                #dps[i+1][j+1]=dps[i][j+1]
print(''.join(dp[n][m]))

Submission status: Runtime Error

Solution code:
from numba import njit
S = input()
T = input()
dp = [[ "" for _ in range(len(S) + 1 )] for _ in range(len(T) + 1)]


@njit
def solv()
for i in range(1,len(dp)):
    for j in range(1,len(dp[0])):
        if T[i - 1] == S[j-1]:
            dp[i ][j ] = dp[i-1][j-1] + S[j-1]
        else:
            res1 = dp[i - 1][j]
            res2 = dp[i][j - 1]
            l1 = len(res1)
            l2 = len(res2)
            if l1 > l2:
                dp[i ][j] = res1
            else:
                dp[i ][j] = res2
solv()
print(dp[-1][-1])

Submission status: Runtime Error

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

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

ret = []
while ls > 0 and lt > 0:
    # dpテーブルの番号が一致しているということは、今評価対象の文字は最長共通部分列に含まれないということになる
    # そのため評価対象の文字を変更して次のループに入る
    # dpテーブルを右下から左上になめるように見ていくのは、評価対象以降の文字列の影響を除くため
    if dp[lt][ls] == dp[lt][ls-1]:
        ls -= 1
    elif dp[lt][ls] == dp[lt-1][ls]:
        lt -= 1
    else:
        ret.append(s[ls])
        ls -= 1
        lt -= 1

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

Submission status: Runtime Error

Solution code:
def main():
    s = input()
    t = input()
    ret = []
    ret = search(s, t, 0, 0, ret)
    print("".join(ret))


def search(s, t, i, j, ret):
    if i >= len(s) or j >= len(t):
        return ret
    if s[i] != t[j]:
        ret1 = search(s, t, i, j+1, ret[:])
        ret2 = search(s, t, i + 1, j, ret)
        return ret1 if len(ret1) > len(ret2) else ret2

    ret.append(s[i])
    return search(s, t, i + 1, j + 1, ret)


main()

Submission status: Runtime Error

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


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

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

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

Submission status: Runtime Error

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

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

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

i = len(s)-1
j = len(t)-1
while (i>0 and j>0):

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] and i >= 1:
            i -= 1
        elif dp[i][l-1] == dp[i][l] and l >= 1:
            l -= 1
        else:
            ans = s[i - 1] + ans
            i -= 1
            l -= 1
    print(ans)