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:
def F():
    s = S()
    t = S()
    dp = [[0 for i in range(len(t)+1)] for k in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                if dp[i][j + 1] < dp[i + 1][j]:
                    dp[i + 1][j + 1] = dp[i + 1][j]
                else:
                    dp[i + 1][j + 1] = dp[i][j + 1]
    ss = len(s)
    tt = len(t)
    ans = ""
    si = ss
    ti = tt
    while si > 0 and ti > 0:
        if dp[si][ti] == dp[si - 1][ti]:
            si -= 1
        elif dp[si][ti] == dp[si][ti - 1]:
            ti -= 1
        else:
            si -= 1
            ti -= 1
            ans = s[si]+ans
 
 
    print(ans)
    return
F()

Submission status: Runtime Error

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

lens=len(s)
lent=len(t)

dp=[[0]*(lent+1) for _ in range(lens+1)]

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

ans=''
i=-1
tmp=dp[-1][-1]
for j in range(lent,-1,-1):
    if dp[i-1][j-1]<tmp:
        ans+=t[j-1]
        tmp=dp[i-1][j-1]
        i-=1
print(ans[::-1])

Submission status: Runtime Error

Solution code:
a="0"+input()
b="1"+input()
dp=[[0]*len(b) for i in range(len(a))]
for i in range(len(a)):
    for j in range(len(b)):
        if a[i]==b[j]:
            if i>0 and j>0:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=1
        else:
            if i>0 and j>0:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
            elif i==0 and j>0:
                dp[i][j]=dp[i][j-1]
            elif i>0 and j==0:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=0

def findout(x,y):
    stack=[(x,y)]
    while stack:
        x,y=stack.pop()
        if x<0 or y<0:
            continue
        if dp[x][y]==dp[x-1][y-1]+1 and a[x]==b[y]:
            return (x,y)
        stack+=[(x-1,y),(x,y-1)]
        
ans=""
L=dp[-1][-1]
x,y=len(a)-1,len(b)-1
for i in range(L):
    x,y=findout(x,y)
    ans+=a[x]
    x-=1
    y-=1
print(ans[::-1])

Submission status: Runtime Error

Solution code:
a="0"+input()
b="1"+input()
dp=[[0]*len(b) for i in range(len(a))]
for i in range(len(a)):
    for j in range(len(b)):
        if a[i]==b[j]:
            if i>0 and j>0:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=1
        else:
            if i>0 and j>0:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
            elif i==0 and j>0:
                dp[i][j]=dp[i][j-1]
            elif i>0 and j==0:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=0

Ans=[]
def findout(i,j):
    
    if dp[i][j]==dp[i-1][j-1]+1 and a[i]==b[j]:
        
        return (i-1,j-1)
    temp1=None
    temp2=None
    if i>0:
        temp1=findout(i-1,j)
    if j>0:
        temp2=findout(i,j-1)
    if temp1:
        return temp1
    if temp2:
        return temp2
x,y=len(a)-1,len(b)-1
ans=""
for i in range(dp[-1][-1]):
    x,y=findout(x,y)
    ans+=a[x+1]
print(ans[::-1])

Submission status: Runtime Error

Solution code:
a=input()
b=input()
dic={}
def findout(i,j):
    if (i,j) in dic:
        return dic[(i,j)]
    
    if i==0 and j==0:
        if a[i]==b[j]:
            return a[i]
        else:
            return ""
    
    elif i==0 and j>0:
        if a[i]==b[j]:
            
            return a[i]
        else:
            
            dic[(i,j)] = findout(i,j-1)
            return dic[(i,j)]
    
    elif i>0 and j==0:
        if a[i]==b[j]:
            return b[j]
        else:
            dic[(i,j)]=findout(i-1,j)
            return dic[(i,j)]
    else:
        if a[i]==b[j]:
            dic[(i,j)]=findout(i-1,j-1)+a[i]
            return dic[(i,j)]
        else:
            temp1=findout(i,j-1)
            temp2=findout(i-1,j)
            if len(temp1)>len(temp2):
                dic[(i,j)]=temp1
            else:
                dic[(i,j)]=temp2
            return dic[(i,j)]
print(findout(len(a)-1,len(b)-1))

Submission status: Runtime Error

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

lens = len(s)
lent = len(t)

# dp = [[None] * lent for _ in range(lens)]
# def dfs(aindex=0, bindex=0):
#     if aindex >= lens:
#         return 0
#     if bindex >= lent:
#         return 0
#
#     if dp[aindex][bindex] is not None:
#         return dp[aindex][bindex]
#
#     if s[aindex] == t[bindex]:
#         r = dfs(aindex + 1, bindex + 1) + 1
#     else:
#         r = max(dfs(aindex + 1, bindex), dfs(aindex, bindex + 1))
#     dp[aindex][bindex] = r
#     return r
#
# print(dfs())

dp = [[0] * (lent + 1) for _ in range(lens + 1)]
pattern = [[0] * (lent + 1) for _ in range(lens + 1)]
# dp = [[(0, 0) for _ in range(lent + 1)] for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            r = dp[aindex + 1][bindex + 1] + 1
            # p = s[aindex] + pattern[aindex + 1][bindex + 1]
            # p = (1 << aindex) + pattern[aindex + 1][bindex + 1]
        else:
            if dp[aindex + 1][bindex] > dp[aindex][bindex + 1]:
                r = dp[aindex + 1][bindex]
                p = pattern[aindex + 1][bindex]
            else:
                r = dp[aindex][bindex + 1]
                p = pattern[aindex][bindex + 1]
            # r = max(dp[aindex + 1][bindex], dp[aindex][bindex + 1])
        dp[aindex][bindex] = r
        pattern[aindex][bindex] = p
for aindex in range(lens):
    if (1 << aindex) & pattern[0][0]:
        print(s[aindex], end="")
# print()
# print(dp[0])
# print(pattern[0])

Submission status: Runtime Error

Solution code:
from numpy import*
N,W=map(int, input().split())
dp=zeros(W+1)
for i in range(N):
    w,v=map(int, input().split())
    dp[w:]=maximum(dp[w:], dp[:-w]+v)
print(int(dp[W]))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template

# BEGIN CUT HERE
def lcs(s, t):
    '''s,tは文字列をリスト化したもの'''
    n = len(s)
    m = len(t)
    s.insert(0, '$')
    t.insert(0, '%')
    dp = [[0 for _j in range(m + 2)] for _i in range(n + 2)]
    dp[0][0] = 0
    for i in range(n+1):
        for j in range(m+1):
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
            dp[i][j + 1] = max(dp[i][j + 1], dp[i][j])
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + (s[i] == t[j]))
    # return dp[n][m]
    '''復元する'''
    length = dp[n][m]
    ans = ['']*(length+1)
    while(length > 0):
        if(s[n] == t[m]):
            ans[length] = s[n]
            n-=1
            m-=1
            length-=1
        elif(dp[n][m] == dp[n - 1][m]):
            n-=1
        else:
            m-=1
    return ''.join(ans)
# END CUT HERE

def ALDS1_10_C():
    q = ii()
    for _ in range(q):
        s = li()
        t = li()
        print(lcs(s, t))

def EDPC_F():
    s = li()
    t = li()
    print(lcs(s,t))


if __name__ == '__main__':
    # ALDS1_10_C()
    EDPC_F()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
//#define int long long
using namespace std;

int delta[3][2] = {{-1, -1}, {-1, 0}, {0, -1}};

int dp[3000][3000];
char carac[3000][3000];

string a, b;

int lcs(int iA, int iB){
    if (iA == -1 || iB == -1)
        return 0;
    
    if (dp[iA][iB] != -1)
        return dp[iA][iB];
    
    int rep = 0;
    int temp = 0;

    if (a[iA] == b[iB]){
        rep = lcs(iA - 1, iB - 1) + 1;
        carac[iA][iB] = a[iA];
    }
    else{
        rep = lcs(iA - 1, iB);
        temp = lcs(iA, iB - 1);

        if (temp > rep)
            rep = temp;
    }

    dp[iA][iB] = rep ;
    return rep;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> a >> b;

    for (int i = 0; i < 3000; i++){
        for (int a = 0; a < 3000; a++){
            dp[i][a] = -1;
        }
    }

    lcs(a.length()-1, b.length() - 1);
    pair<int,int> pos = {a.length()-1, b.length() -1};

    string chaine = "";
    bool  continuer = true;
    while (continuer){
        continuer = false;

        if (carac[pos.first][pos.second]){
            chaine = carac[pos.first][pos.second] + chaine;
        }
        
        int maxi = -1;
        pair<int,int>  nextPos = {-1,-1};

        for (int i = 0; i < 3; i++){
            int dx = delta[i][0]; int dy = delta[i][1];

            bool inGrid = (0 <= pos.first + dx && 0 <= pos.second + dy);
            if (inGrid && dp[pos.first + dx][pos.second + dy] > maxi){
                maxi = dp[pos.first + dx][pos.second + dy];
                nextPos.first = pos.first + dx;
                nextPos.second = pos.second + dy;
                continuer = true;
            }
        }
        pos.first = nextPos.first;
        pos.second = nextPos.second;
    }
    cout << chaine;

}

Submission status: Runtime Error

Solution code:
a = input()
b = input()

dp = [ [-1 for i in range(len(b))] for x in range(len(a))]
char = [ ['' for i in range(len(b))] for x in range(len(a))]

def lcs(iA, iB):
    if iA == -1 or iB == -1:
        return 0
    
    if dp[iA][iB] != -1:
        return dp[iA][iB]
    
    if a[iA] == b[iB]:
        rep = lcs(iA - 1, iB - 1) + 1
        char[iA][iB] = a[iA]
    
    else:
        rep = lcs(iA - 1, iB)
        temp = lcs(iA, iB - 1)

        if temp > rep:
            rep = temp

    dp[iA][iB] = rep 
    return rep

lcs(len(a)-1, len(b) - 1)

pos = (len(a)-1, len(b)-1)



chaine = ''
continuer = True 
while continuer:
    continuer = False
    chaine = char[pos[0]][pos[1]] + chaine
    
    maxi = -1
    nextPos = None 

    for dx, dy in [(-1, -1), (-1, 0), (0, -1)]:
        inGrid =  0 <= pos[0] + dx and 0 <= pos[1] + dy
        if inGrid and dp[pos[0] + dx][pos[1] + dy] > maxi:
            maxi = dp[pos[0] + dx][pos[1] + dy]
            nextPos = (pos[0] + dx, pos[1] + dy)
            continuer = True 
    
    pos = nextPos 

print(chaine)


"""
for i in dp:
    print(*i)

for i in char:
    print(*i)
"""

Submission status: Runtime Error

Solution code:
a = input()
b = input()

dp = [ [-1 for i in range(len(b))] for x in range(len(a))]
char = [ ['' for i in range(len(b))] for x in range(len(a))]

def lcs(iA, iB):
    if iA == -1 or iB == -1:
        return 0
    
    if dp[iA][iB] != -1:
        return dp[iA][iB]
    
    if a[iA] == b[iB]:
        rep = lcs(iA - 1, iB - 1) + 1
        char[iA][iB] = a[iA]
    
    else:
        rep = lcs(iA - 1, iB)
        temp = lcs(iA, iB - 1)

        if temp > rep:
            rep = temp

    dp[iA][iB] = rep 
    return rep

lcs(len(a)-1, len(b) - 1)

pos = (len(a)-1, len(b)-1)



chaine = ''
continuer = True 
while continuer:
    continuer = False
    chaine += char[pos[0]][pos[1]]
    
    maxi = -1
    nextPos = None 

    for dx, dy in [(-1, -1), (-1, 0), (0, -1)]:
        inGrid =  0 <= pos[0] + dx and 0 <= pos[1] + dy
        if inGrid and dp[pos[0] + dx][pos[1] + dy] > maxi:
            maxi = dp[pos[0] + dx][pos[1] + dy]
            nextPos = (pos[0] + dx, pos[1] + dy)
            continuer = True 
    
    pos = nextPos 

print(chaine[::-1])


"""
for i in dp:
    print(*i)

for i in char:
    print(*i)
"""

Submission status: Runtime Error

Solution code:
a = input()
b = input()

dp = [ [-1 for i in range(len(b))] for x in range(len(a))]
char = [ ['' for i in range(len(b))] for x in range(len(a))]

def lcs(iA, iB):
    if iA == -1 or iB == -1:
        return 0
    
    if dp[iA][iB] != -1:
        return dp[iA][iB]
    
    if a[iA] == b[iB]:
        rep = lcs(iA - 1, iB - 1) + 1
        char[iA][iB] = a[iA]
    
    else:
        rep = lcs(iA - 1, iB)
        temp = lcs(iA, iB - 1)

        if temp > rep:
            rep = temp

    dp[iA][iB] = rep 
    return rep

lcs(len(a)-1, len(b) - 1)

pos = (len(a)-1, len(b)-1)



chaine = ''
continuer = True 
while continuer:
    continuer = False
    chaine += char[pos[0]][pos[1]]
    
    maxi = -1
    nextPos = None 

    for dx, dy in [(-1, -1), (-1, 0), (0, -1)]:
        inGrid =  0 <= pos[0] + dx and 0 <= pos[1] + dy
        if inGrid and dp[pos[0] + dx][pos[1] + dy] > maxi:
            maxi = dp[pos[0] + dx][pos[1] + dy]
            nextPos = (pos[0] + dx, pos[1] + dy)
            continuer = True 
    
    pos = nextPos 

chaine += char[0][0]

print(chaine[::-1])


"""
for i in dp:
    print(*i)

for i in char:
    print(*i)
"""

Submission status: Runtime Error

Solution code:
def main():
	S, T = input(), input()

	Z = 20 # 3010
	dp = [[0] * Z for _ in range(Z)]
	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])

	#for line in dp:
	#	print(line)
	#print(dp[len(S)][len(T)])
	i, j, result = len(S), len(T), ""
	while 0 < i and 0 < j:
		if dp[i][j] == dp[i - 1][j]:
			i -= 1
		elif dp[i][j] == dp[i][j - 1]:
			j -= 1
		else:
			result = S[i - 1] + result
			i -= 1
			j -= 1
	print(result)

main()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

input = sys.stdin.readline

S = input()
T = input()

def lcs(S, T):
    s = [ch for ch in S]
    t = [ch for ch in T]

    # s[:i]とt[:j]のLCS
    dp = np.empty((len(s)+1, len(t)+1), dtype="U300")

    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] + s[i-1]
            else:
                case1 = dp[i, j-1]
                case2 = dp[i-1, j]
                if len(case1) > len(case2):
                    dp[i, j] = case1
                else:
                    dp[i, j] = case2
    return dp[-1, -1]

print(lcs(S, T))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

input = sys.stdin.readline

S = input()
T = input()

def lcs(S, T):
    s = [ch for ch in S]
    t = [ch for ch in T]

    # s[:i]とt[:j]のLCS
    dp = np.empty((len(s)+1, len(t)+1), dtype="U3000")

    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] + s[i-1]
            else:
                case1 = dp[i, j-1]
                case2 = dp[i-1, j]
                if len(case1) > len(case2):
                    dp[i, j] = case1
                else:
                    dp[i, j] = case2
    return dp[-1, -1]

print(lcs(S, T))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def mi(): return map(int, input().split())


def li(): return list(mi())


def li_(): return [int(x) - 1 for x in input().split()]


def lin(n: int): return [input() for _ in range(n)]


def llin(n: int): return [li() for _ in range(n)]


def llin_(n: int): return [li_() for _ in range(n)]


def lli(): return [list(map(int, l.split())) for l in input()]


def i(): return int(input())


def f(): return float(input())


def s(): return input().replace('\n', '')


def main():
    S = s()
    T = s()
    dp = [[0] * len(T) for _ in range(len(S))]
    dp[0][0] = int(S[0] == T[0])
    check = [[None] * len(T) for _ in range(len(S))]
    ok = (10, 10)
    check[0][0] = ok if dp[0][0] else (0, 0)
    for i in range(1, len(S)):
        if S[i] == T[0]:
            dp[i][0] = 1
            check[i][0] = ok
        else:
            dp[i][0] = dp[i - 1][0]
            check[i][0] = (-1, 0)
    for j in range(1, len(T)):
        if T[i] == S[0]:
            dp[0][j] = 1
            check[0][j] = ok
        else:
            dp[0][j] = dp[0][j-1]
            check[0][j] = (0, -1)
    for i in range(1, len(S)):
        for j in range(1, len(T)):
            if S[i] == T[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                check[i][j] = (-1, -1)
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                if dp[i - 1][j] > dp[i][j - 1]:
                    check[i][j] = (-1, 0)
                else:
                    check[i][j] = (0, -1)

    ans = ""
    i = len(S)-1
    j = len(T)-1
    for _ in range(len(S) + len(T)):
        if check[i][j] == ok:
            ans = S[i] + ans
            break
        else:
            if check[i][j] == (-1, -1):
                ans = S[i] + ans
                tmp = i
                i += check[i][j][0]
                j += check[tmp][j][1]
            else:
                tmp = i
                i += check[i][j][0]
                j += check[tmp][j][1]
    #print(*check, sep="\n")
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

s = input()
t = input()

len_s = len(s)
len_t = len(t)

dp = np.zeros((len_s+1, len_t+1), dtype = int)

for i in range(len_s):
    for j in range(len_t):
        if s[i] == t[j]:
            dp[i+1, j+1] = np.maximum( dp[i+1, j+1], dp[i, j] + 1)
        dp[i+1, j+1] = np.maximum(dp[i+1,j+1], dp[i+1,j])
        dp[i+1, j+1] = np.maximum(dp[i+1,j+1], dp[i,j+1])
#        print(dp)

i = len_s
j = len_t
str = ''

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

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(1000000000000000000000000000000000)
s = [x for x in input()]
t = [x for x in input()]
dp = [['' for i in range(len(s))] for j in range(len(t))]
def dppp(ns,nt):
    global dp,s,t
    if ns == len(s) or nt == len(t):return ''
    if dp[nt][ns] != '':return dp[nt][ns]
    if s[ns] == t[nt]:
        get = s[ns] + dppp(ns+1,nt+1)
    else:
        get = ''
    sgo = dppp(ns+1,nt)
    tgo = dppp(ns,nt+1)
    if len(sgo) >= len(tgo) and len(sgo) >= len(get):
        dp[nt][ns] = sgo
        return sgo
    elif len(tgo) >= len(sgo) and len(tgo) >= len(get):
        dp[nt][ns] = tgo
        return tgo
    else:
        dp[nt][ns] = get
        return get
ans = dppp(0,0)
print(ans)

Submission status: Runtime Error

Solution code:
s = [x for x in input()]
t = [x for x in input()]
dp = [['' for i in range(len(s))] for j in range(len(t))]
def dppp(ns,nt):
    global dp,s,t
    if ns == len(s) or nt == len(t):return ''
    if dp[nt][ns] != '':return dp[nt][ns]
    if s[ns] == t[nt]:
        get = s[ns] + dppp(ns+1,nt+1)
    else:
        get = ''
    sgo = dppp(ns+1,nt)
    tgo = dppp(ns,nt+1)
    if len(sgo) >= len(tgo) and len(sgo) >= len(get):
        dp[nt][ns] = sgo
        return sgo
    elif len(tgo) >= len(sgo) and len(tgo) >= len(get):
        dp[nt][ns] = tgo
        return tgo
    else:
        dp[nt][ns] = get
        return get
ans = dppp(0,0)
print(ans)

Submission status: Runtime Error

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

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

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

ansl = []
cnt = dp[-1][-1]
def tami(i,j):
  global cnt
  if cnt == 0:
    return
  if s[i-1] == t[j-1]:
    cnt -= 1
    ansl.append(i-1)
  if dp[i-1][j-1]==cnt:
    tami(i-1,j-1)
  elif dp[i][j-1]==cnt:
    tami(i,j-1)

tami(len(s),len(t))

ans = ""
for i in ansl:
  ans += s[i]
print(ans[::-1])

Submission status: Runtime Error

Solution code:
def lcs(i,j):
    if i*j==0:
        return ""
    ij=i*1000+j
    if ij in memo:
        return memo[ij]
    if s[i-1]==t[j-1]:
        re=lcs(i-1,j-1)+s[i-1]
        memo[ij]=re
        return re
    re1=lcs(i-1,j)
    re2=lcs(i,j-1)
    if len(re1)>len(re2):
        memo[ij]=re1
        return re1
    memo[ij]=re2
    return re2


s = input()
t = input()
ls = len(s)
lt = len(t)
memo={}
print(lcs(ls,lt))

Submission status: Runtime Error

Solution code:
def lcs(i,j):
    if i*j==0:
        return ""
    if s[i-1]==t[j-1]:
        return lcs(i-1,j-1)+s[i-1]
    re1=lcs(i-1,j)
    re2=lcs(i,j-1)
    if len(re1)>len(re2):
        return re1
    return re2


s = input()
t = input()
ls = len(s)
lt = len(t)
print(lcs(ls,lt))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

# input処理を高速化する
input = sys.stdin.readline

# 入力
S = input()
T = input()

def lcs(s, t):
    dp = np.zeros((len(S)+1, len(T)+1), dtype=int)

    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] = np.maximum(dp[i+1][j], dp[i][j+1])
    
    ans = ''
    i = len(S)
    j = len(T)
    while (i>0  and j>0):
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans += s[i-1] 
            i -= 1
            j -= 1
    
    print(ans[::-1])

Submission status: Runtime Error

Solution code:
MAX_LENGTH  = 100
memoization = [[-1 for i in range(MAX_LENGTH)] for a in range(MAX_LENGTH)] 

string1 = input()
string2 = input()

def LCS(indexString1, indexString2):
   if indexString1 == len(string1) or indexString2 == len(string2):
      return ''
   
   if memoization[indexString1][indexString2] != -1:
      return memoization[indexString1][indexString2] 
   
   longestCommonSubsequence = None

   if string1[indexString1] == string2[indexString2]:
      longestCommonSubsequence = string1[indexString1] + LCS(indexString1+1, indexString2+1)
   
   else:
      longestCommonSubsequence = LCS(indexString1+1, indexString2)
      temp = LCS(indexString1, indexString2+1) 

      if len(temp) > len(longestCommonSubsequence):
         longestCommonSubsequence = temp
   
   memoization[indexString1][indexString2] = longestCommonSubsequence
   return longestCommonSubsequence

print( LCS(0,0) )

Submission status: Runtime Error

Solution code:
def LCS(s1, s2):
    l1, l2 = len(s1), len(s2)
    if l1 == 0 or l2 == 0: return ''

    # memorization of m[l1][l2]
    m = []
    for x in range(l1):
        m.append([0]*(l2))

    # Fill 0th row
    isSameFound = False
    for i in range(l1):
        if isSameFound or s1[i] == s2[0]:
            m[i][0] = 1
            isSameFound = True

    # Fill 0th column
    isSameFound = False
    for j in range(l2):
        if isSameFound or s2[j] == s1[0]:
            m[0][j] = 1
            isSameFound = True

    max_len = 0
    # m[i][j] stores the maximum length of subsequence of s1[:i+1], s2[:j+1]
    for i in range(0, l1-1):
        for j in range(0, l2-1):
            if s1[i+1] == s2[j+1]:
                m[i+1][j+1] = m[i][j] + 1
                max_len = max(m[i][j], max_len)
            else:
                m[i+1][j+1] = max(m[i][j+1], m[i+1][j])

    #If you want to know just the length of the lcs, return maxLen.
    #Here we'll try to print the lcs.
    lcs_str = ''
    i, j = l1-1, l2-1
    while i >= 0 and j >= 0:
        if s1[i] == s2[j]:
            lcs_str += s1[i] #or s2[j-1]
            i -= 1
            j -= 1
        else:
            if m[i-1][j] > m[i][j-1]:
                i -= 1
            else:
                j -= 1

    return lcs_str[::-1]
  

s,t = input()

print(LCS(s,t))

Submission status: Runtime Error

Solution code:
def main():
    s = " "+input()
    N = len(s)-1

    t = " "+input()
    M = len(t)-1
    if N < M:
        N, M = M, N
        s, t = t, s
    # dp[i][j] := sのi文字目, tのj文字目までを使ったLCSの長さ
    # last_letter[i][j] := s_i, t_jまでを使ったLCSの最後の文字
    dp = [[-1]*(M+1) for i in range(N+1)]
    last_letter = [[-1]*(M+1) for i in range(N+1)]
    dp[0] = [0]*(N+1)
    last_letter[0] = ['' for n in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0
        last_letter[i][0] = ''
    for i in range(1, N+1):
        for j in range(1, M+1):
            
            if s[i] == t[j]:
                dp[i][j] = dp[i-1][j-1]+1
                last_letter[i][j] = s[i]
            elif s[i] != t[j]:
                if dp[i-1][j] > dp[i][j-1]:
                    dp[i][j] = dp[i-1][j]
                    last_letter[i][j] = last_letter[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1]
                    last_letter[i][j] = last_letter[i][j-1]
    print(get(s, t, N, M, dp, last_letter))

def get(s, t, i, j, dp, last_letter):
    if i == 0 or j == 0:
        return ""
    ll = last_letter[i][j]
    if s[i]==t[j]==ll:
        return get(s, t, i-1, j-1, dp, last_letter) + s[i]
    elif ll == s[i] and ll != t[j]:
        return get(s, t, i, j-1, dp, last_letter)
    elif ll == t[j] and ll != s[i]:
        return get(s, t, i-1, j, dp, last_letter)
    elif ll != t[j] and ll!= s[i]:
        return get(s, t, i-1, j-1, dp, last_letter)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

# 最長部分列の長さを求める
# 0行と0列は0
def lcs_count(A,B):
    # initial value setting
    dp = [[0]*(l2+1) for _ in range(l1+1)]
    # create table
    for i in range(1,l1+1):
        for j in range(1,l2+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
#    for line in dp:
#        print(line)
    return dp

def lcs_string(dp): 
    string = []
    i = l1-1
    j = l2-1
    while i > 0 and j > 0:
        if t[i - 1] == t[j - 1]:
            string.insert(0,chr(s[i-1]+97))
            i, j = i - 1, j - 1
        elif dp[i][j - 1] > dp[i - 1][j]:
            j -= 1
        else:
            i -= 1
    print("".join(string))

s = [ord(a)-97 for a in list(sys.stdin.readline().rstrip())]
t = [ord(b)-97 for b in list(sys.stdin.readline().rstrip())]
l1 = len(s)
l2 = len(t)

DP = lcs_count(s,t)
#print(DP[l1][l2])
lcs_string(DP)

Submission status: Runtime Error

Solution code:
import sys

def main():
  s = sys.stdin.readline().rstrip()
  t = sys.stdin.readline().rstrip()
  l1 = len(s)
  l2 = len(t)

  DP = lcs_count(s,t)
  lcs_string(DP)

  def lcs_count(A,B):
      # initial value setting
      dp = [list(0 for _ in range(l2+1)) for _ in range(l1+1)]
      # create table
      for i in range(1,l1+1):
          for j in range(1,l2+1):
              if A[i-1] == B[j-1]:
                  dp[i][j] = dp[i-1][j-1] + 1
              else:
                  dp[i][j] = max(dp[i-1][j],dp[i][j-1])
      return dp

  def lcs_string(dp):
      string = []
      S = [m for m in range(l1,0,-1)]
      T = [n for n in range(l2,0,-1)]
      for i,j in zip(S,T):
          if dp[i][j] > dp[i-1][j-1]:
              string.insert(0,s[i-1])
      print("".join(string))

main()

Submission status: Runtime Error

Solution code:
s = input()
t= input()
# s = "abracadabra"
# t = "avadakedavra"

dp=[[0]*len(t) for i in range(len(s))]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])
            
i, j, dp_len = len(s),len(t), dp[-1][-1]
ans = ""

while dp_len:
#     print("現在精査している文字は{}と{}です。もとのsは{}で、tは{}です。sの長さは{}, tの長さは{}です".format(s[i-1],t[j-1],s[:i-1], t[:j-1], i,j))
    if s[i-1] == t[j-1]:
        ans += s[i-1]
        i -= 1
        j -= 1
        dp_len -= 1
#         print("一致")
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1
        
# print(dp)
print(ans[::-1])

Submission status: Runtime Error

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