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:
s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for i in range(n+1)] for j in range(m+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])
l=dp[n][m]
ans=''
a=n
b=m
while a>0 and b>0:
  if dp[a][b]==dp[a-1][b]:
    a-=1
  elif dp[a][b]==dp[a][b-1]:
    b-=1
  else:
    a-=1
    b-=1
    ans=s[a]+ans
print(ans)

Submission status: Runtime Error

Solution code:
def LCS(s1, s2):
    l1, l2 = len(s1), len(s2)
    dp = [[0 for _ in range(l2 + 1)] for _ in range(l1 + 1)]
    for i in range(1, l1+1):
        for j in range(1, l2+1):
            if s1[i + 1] == s2[j + 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
    return dp[l1][l2]


if __name__ == '__main__':
    s1 = input()
    s2 = input()
    print(LCS(s1, s2))

Submission status: Runtime Error

Solution code:
def LCS(s1, s2):
    l1, l2 = len(s1), len(s2)
    dp = [[0 for _ in range(l2 + 1)] for _ in range(l1 + 1)]
    for i in range(1, l1):
        for j in range(1, l2):
            if s1[i + 1] == s2[j + 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
    return dp[l1][l2]


if __name__ == '__main__':
    s1 = input()
    s2 = input()
    print(LCS(s1, s2))

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout
from collections import deque, defaultdict
import math as m

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	s = rll()[0]
	t = rll()[0]
	m, n = len(s), len(t)
	dp = [[0 for __ in range(n)] for _ in range(m)]

	#dp[i][j] = LCs of s0,...,si and t0,...,tj

	def pprint(M):
		for row in M:
			print(row)
		print("~~~")
	
	dp[0][0] = 1 if s[0] == t[0] else 0
	for c in range(1, n):
		dp[0][c] = max(dp[0][c-1], 1 if s[0] == t[c] else 0)
	for r in range(1, m):
		dp[r][0] = max(dp[r-1][0], 1 if s[r] == t[0] else 0)

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

	ans = deque()
	def reconstruct(i, j):
		if i < 0 or j < 0: return
		if s[i] == t[j]:
			ans.appendleft(s[i])
			reconstruct(i-1, j-1)
		else:
			up, left = NINF, NINF
			if i - 1 >= 0:
				up = dp[i-1][j]
			if j - 1 >= 0:
				left = dp[i][j-1]
			if up >= left:
				reconstruct(i-1, j)
			else:
				reconstruct(i, j-1)
	reconstruct(m-1, n-1)
	print("".join(x for x in ans))
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
def LCS(a,n1,b,n2,dp):
	for i in range(1, n1+1):
		for j in range(1, n2+1):
			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])
				
			
a=input()
n1=len(a)
a='#'+a+'#'
b=input()
n2=len(b)
b='#'+b+'#'
dp=[[0 for i in range(n1+10)] for i in range(n2+10)]
LCS(a,n1,b,n2,dp)

for i in range(n1+1):
	for j in range (n2+1):
		print(dp[i][j], end=" ")
	print("")
	
i=n1
j=n2
res=""
while(i>0 and j>0):
	if(a[i]==b[j]):
		res+=a[i]	
		i-=1
		j-=1
	else:
		if(dp[i-1][j]>=dp[i][j-1]): i-=1
		else: j-=1


print(res[::-1])

Submission status: Runtime Error

Solution code:
def LCS(a,n1,b,n2,dp):
	for i in range(1, n1+1):
		for j in range(1, n2+1):
			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])
				
			
a=input("Enter  string 1: ")
n1=len(a)
a='#'+a+'#'
b=input("Enter  string 2: ")
n2=len(b)
b='#'+b+'#'
dp=[[0 for i in range(n1+10)] for i in range(n2+10)]
LCS(a,n1,b,n2,dp)

for i in range(n1+1):
	for j in range (n2+1):
		print(dp[i][j], end=" ")
	print("")
	
i=n1
j=n2
res=""
while(i>0 and j>0):
	if(a[i]==b[j]):
		res+=a[i]	
		i-=1
		j-=1
	else:
		if(dp[i-1][j]>=dp[i][j-1]): i-=1
		else: j-=1


print(res[::-1])

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):
        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])
ans=''
i=len(s)
j=len(t)
while(i>0 and j>0):
    # print(i,j,dp[i][j-1],dp[i-1][j],s[i],t[j])
    # print(ans)
    if s[i-1]==t[j-1]:
        ans=s[i]+ans
        i-=1 
        j-=1 
    else:
        if dp[i][j-1]>dp[i-1][j]:
            j-=1
            # print('here')
        else:
            i-=1 
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.buffer.readline
s1 = input()
s2 = input()
n, m = len(s1), len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
prev = dp[0]
for i in range(1,n+1):
    dpi = dp[i]
    for j in range(1, m+1):
        if s1[i-1] == s2[j-1]:
            dpi[j] = 1 + prev[j-1]
        else:
            dpi[j] = max(prev[j], dpi[j-1])
    prev = dpi
res = ''
i, j = n, m
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        res = s1[i-1] + res
        i -= 1
        j -= 1
print(res)

Submission status: Runtime Error

Solution code:
def main():
    s=input()
    t=input()
    n,m=len(s),len(t)
    dp=[[0]*(m+1)for i 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])
    index = dp[n][m] 
    lcs = [""] * (index+1) 
    lcs[index] = "" 
    i = m 
    j = n 
    while i > 0 and j > 0: 
  
        # If current character in X[] and Y are same, then 
        # current character is part of LCS 
        if t[i-1] == s[j-1]: 
            lcs[index-1] = t[i-1] 
            i-=1
            j-=1
            index-=1
  
        # If not same, then find the larger of two and 
        # go in the direction of larger value 
        elif dp[i-1][j] > dp[i][j-1]: 
            i-=1
        else: 
            j-=1
    print(''.join(lcs))
if __name__== '__main__':
    main()

Submission status: Runtime Error

Solution code:

dp =  [[-1 for i in range(3005)] for j in range(3005)]
s=''
t=''
k=0

def fun(iss,itt):

    if ((iss==len(s)) or (itt==len(t))):
        dp[iss][itt]=0
        return dp[iss][itt]

    elif dp[iss][itt]!=-1:
        return dp[iss][itt]

    ans=0
    if(s[iss]==t[itt]):
        ans=1+fun(iss+1,itt+1)
    ans = max(ans,fun(iss+1,itt))
    ans = max(ans, fun(iss , itt+1))
    dp[iss][itt] = ans
    return dp[iss][itt]

s=input()
t=input()
val=fun(0,0)
ans=''
idx_s=0
idx_t=0

while idx_s<len(s) and idx_t<len(t):
    if ((dp[idx_s+1][idx_t+1]==dp[idx_s][idx_t]-1) and (s[idx_s]==t[idx_t]) and (dp[idx_s][idx_t]!=0)):
        ans+=s[idx_s]
        idx_s+=1
        idx_t+=1
    elif dp[idx_s][idx_t]==dp[idx_s+1][idx_t]:
        idx_s+=1
    else:
        idx_t+=1

print(ans)

Submission status: Runtime Error

Solution code:

dp =  [[-1 for i in range(3005)] for j in range(3005)]
s=''
t=''
k=0

def fun(iss,itt):

    if ((iss==len(s)) or (itt==len(t))):
        dp[iss][itt]=0
        return dp[iss][itt]

    elif dp[iss][itt]!=-1:
        return dp[iss][itt]

    ans=0
    if(s[iss]==t[itt]):
        ans=1+fun(iss+1,itt+1)
    ans = max(ans,fun(iss+1,itt))
    ans = max(ans, fun(iss , itt+1))
    dp[iss][itt] = ans
    return dp[iss][itt]

s=input()
t=input()
val=fun(0,0)
ans=''
idx_s=0
idx_t=0

while idx_s<len(s) and idx_t<len(t):
    if (dp[idx_s+1][idx_t+1]==dp[idx_s][idx_t]-1) and s[idx_s]==t[idx_t] and dp[idx_s][idx_t]!=0:
        ans+=s[idx_s]
        idx_s+=1
        idx_t+=1
    elif dp[idx_s][idx_t]==dp[idx_s+1][idx_t]:
        idx_s+=1
    else:
        idx_t+=1

print(ans)

Submission status: Runtime Error

Solution code:

dp =  [[-1 for i in range(3005)] for j in range(3005)]
s=''
t=''
k=0

def fun(iss,itt):

    if ((iss==len(s)) or (itt==len(t))):
        dp[iss][itt]=0
        return dp[iss][itt]

    elif dp[iss][itt]!=-1:
        return dp[iss][itt]

    ans=0
    if(s[iss]==t[itt]):
        ans=1+fun(iss+1,itt+1)
    ans = max(ans,fun(iss+1,itt))
    ans = max(ans, fun(iss , itt+1))
    dp[iss][itt] = ans
    return dp[iss][itt]

s=input()
t=input()
val=fun(0,0)
ans=''
idx_s=0
idx_t=0

while idx_s<len(s) and idx_t<len(t):
    if (dp[idx_s+1][idx_t+1]==dp[idx_s][idx_t]-1) and s[idx_s]==t[idx_t]:
        ans+=s[idx_s]
        idx_s+=1
        idx_t+=1
    elif dp[idx_s][idx_t]==dp[idx_s+1][idx_t]:
        idx_s+=1
    else:
        idx_t+=1

print(ans)

Submission status: Runtime Error

Solution code:

dp =  [[-1 for i in range(3005)] for j in range(3005)]
s=''
t=''
k=0

def fun(iss,itt):

    if ((iss==len(s)) or (itt==len(t))):
        dp[iss][itt]=0
        return dp[iss][itt]

    elif dp[iss][itt]!=-1:
        return dp[iss][itt]

    ans=0
    if(s[iss]==t[itt]):
        ans=1+fun(iss+1,itt+1)
    ans = max(ans,fun(iss+1,itt))
    ans = max(ans, fun(iss , itt+1))
    dp[iss][itt] = ans
    return dp[iss][itt]

s=input()
t=input()
val=fun(0,0)
ans=''
idx_s=0
idx_t=0
while idx_s<len(s) and idx_t<len(t):
    if dp[idx_s+1][idx_t+1]==dp[idx_s][idx_t]-1:
        ans+=s[idx_s]
        idx_s+=1
        idx_t+=1
    elif dp[idx_s][idx_t]==dp[idx_s+1][idx_t]:
        idx_s+=1
    else:
        idx_t+=1

print(ans)

Submission status: Runtime Error

Solution code:

dp =  [[-1 for i in range(3005)] for j in range(3005)]
string=[['' for i in range(3005)] for j in range(3005)]
s=''
t=''
k=0

def fun(iss,itt):

    if ((iss==len(s)) or (itt==len(t))):
        dp[iss][itt]=0
        string[iss][itt]=''
        return dp[iss][itt]

    elif dp[iss][itt]!=-1:
        return dp[iss][itt]

    ans=0
    temp=''
    if(s[iss]==t[itt]):
        ans=1+fun(iss+1,itt+1)
        temp=s[iss]+string[iss+1][itt+1]
    ans = max(ans,fun(iss+1,itt))
    if ans==dp[iss+1][itt] :
        temp = string[iss + 1][itt]
    ans = max(ans, fun(iss , itt+1))
    if ans==dp[iss][itt+1] :
        temp = string[iss ][itt + 1]
    dp[iss][itt] = ans
    string[iss][itt]=temp
    return dp[iss][itt]


s=input()
t=input()
fa=fun(0,0)
print(string[0][0])

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

int main(){
    string S,T;
    cin>>S>>T;
    int N = S.length();
    int M = T.length();
    vector<vector<int>> dp(N+1, vector<int>(M+1,0));
    vector<vector<pair<int,int>>> prev(N+1, vector<pair<int,int>>(M+1, pair(-1,-1)));
    for(int i = 1;i < N+1;i++){
        for(int j = 1;j < M+1;j++){
            if(S[i-1] != T[j-1] || dp[i][j-1] != dp[i-1][j-1] || dp[i-1][j] != dp[i-1][j-1]){
                if(dp[i][j-1] > dp[i-1][j]){
                    dp[i][j] = dp[i][j-1];
                    prev[i][j] = pair(i,j-1);
                }else{
                    dp[i][j] = dp[i-1][j];
                    prev[i][j] = pair(i-1,j);
                }
            }else{
                dp[i][j] = dp[i-1][j-1]+1;
                prev[i][j] = pair(-2,-2);
            }
        }
    }

    pair<int,int> to = pair(N,M);
    string res = "";
    while(to != pair(-1,-1)){
        pair<int,int> p = prev[to.first][to.second];
        if(p == pair(-2,-2)){
            res += S[to.first-1];
            to = pair(to.first-1, to.second-1);
        }else{
            to = p;
        }
    }
    reverse(res.begin(),res.end());
    cout<<res<<endl;
}

Submission status: Runtime Error

Solution code:
a=input()
b=input()
m=len(a)
n=len(b)
dp=[[0 for x in range(m+1)]for y in range(n+1)]
#print(dp)
for x in range(1,n+1):
    for y in range(1,m+1):
        if a[x-1]==b[y-1]:
            dp[x][y]=1+dp[x-1][y-1]
            print(a[x-1],end="")
        else:
            dp[x][y]=max(dp[x-1][y],dp[x][y-1])
            pass
#print(dp)
#print(dp[m][n])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon May  4 12:20:33 2020

@author: Kanaru Sato
"""

s = list(input())
t = list(input())

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

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

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon May  4 12:20:33 2020

@author: Kanaru Sato
"""

s = list(input())
t = list(input())

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

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

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon May  4 12:03:46 2020

@author: Kanaru Sato
"""

import sys
sys.setrecursionlimit(10**10)

s = list(input())
t = list(input())

def lcs(a,b,i,j):
    if i == 0 or j == 0:
        return ""
    else:
        if a[i-1] == b[j-1]:
            return lcs(a,b,i-1,j-1)+a[i-1]
        else:
            p = len(lcs(a,b,i-1,j))
            q = len(lcs(a,b,i,j-1))
            if p >= q:
                return lcs(a,b,i-1,j)
            else:
                return lcs(a,b,i,j-1)

print(lcs(s,t,len(s),len(t)))

Submission status: Runtime Error

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

dp = [[0 for i in range(len(s)+2)] for j in range(len(t)+2)]

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

print(ans)

Submission status: Runtime Error

Solution code:
input = sys.stdin.readline

def inp_str():
    '''
    一行の文字をlistで取得
    '''
    return list(input())[:-1]


s = inp_str()
t = inp_str()
n = len(s)
m = len(t)
value = [[0]*(m+1) for i in range(n+1)]
ans = [[""]*(m+1) for i in range(n+1)]

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
            ans[i + 1][j + 1] = "".join([ans[i][j], s[i]])
        elif value[i][j + 1] > value[i + 1][j]: #UP
            ans[i + 1][j + 1] = ans[i][j + 1]
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            ans[i + 1][j + 1] = ans[i + 1][j]
            value[i + 1][j + 1] = value[i + 1][j]

print(ans[n][m])

Submission status: Runtime Error

Solution code:
s=list(input())
t=list(input())
dp=[[0]*(30) for j in range(30)]
ans=[]
memo=-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
             if memo < i:
                 ans.append(t[j])
                 memo = i

        else:
            dp[i+1][j+1] =max(dp[i][j+1],dp[i+1][j])

#print(dp[len(s)][len(t)])
answer=[]
i,j=len(s),len(t)
d=dp[i-1][j-1]
while i>0 and j>0 :
    if dp[i-1][j-1]!=dp[i][j]:
        answer.append(s[i-1])
        i-=1
        j-=1
        continue
    elif dp[i-1][j]==dp[i][j]:
        i-=1
    elif dp[i][j-1]==dp[i][j]:
        j-=1
print("".join(reversed(answer)))

Submission status: Runtime Error

Solution code:
s=list(input())
t=list(input())
dp=[[0]*(30) for j in range(30)]
ans=[]
memo=-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
             if memo < i:
                 ans.append(t[j])
                 memo = i

        else:
            dp[i+1][j+1] =max(dp[i][j+1],dp[i+1][j])

#print(dp[len(s)][len(t)])
answer=[]
i,j=len(s),len(t)
d=dp[i-1][j-1]
while i>0 and j>0 :
    if dp[i-1][j-1]!=dp[i][j]:
        answer.append(chr(s[i-1]))
        i-=1
        j-=1
    elif dp[i-1][j]==dp[i][j]:
        i-=1
    elif dp[i][j-1]==dp[i][j]:
        j-=1
print("".join(reversed(answer)))

Submission status: Runtime Error

Solution code:
s=list(input())
t=list(input())
dp=[[0]*(30) for j in range(30)]
ans=[]
memo=-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
             if memo < i:
                 ans.append(t[j])
                 memo = i

        else:
            dp[i+1][j+1] =max(dp[i][j+1],dp[i+1][j])

#print(dp[len(s)][len(t)])
answer=[]
i,j=len(s),len(t)
d=dp[i-1][j-1]
while i>0 and j>0 :
    if dp[i-1][j-1]!=dp[i][j]:
        answer.append(s[i-1])
        i-=1
        j-=1
    elif dp[i-1][j]==dp[i][j]:
        i-=1
    elif dp[i][j-1]==dp[i][j]:
        j-=1
print("".join(reversed(answer)))

Submission status: Runtime Error

Solution code:
s=list(input())
t=list(input())
dp=[[0]*(30) for j in range(30)]
ans=[]
memo=-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
             if memo < i:
                 ans.append(t[j])
                 memo = i

        else:
            dp[i+1][j+1] =max(dp[i][j+1],dp[i+1][j])

#print(dp[len(s)][len(t)])
answer=[]
i,j=len(s),len(t)
d=dp[i-1][j-1]
while i!=0 :
    if dp[i-1][j-1]!=dp[i][j]:
        answer.append(s[i-1])
        i-=1
        j-=1
    elif dp[i-1][j]==dp[i][j]:
        i-=1
    elif dp[i][j-1]==dp[i][j]:
        j-=1
print("".join(reversed(answer)))

Submission status: Runtime Error

Solution code:
s=list(input())
t=list(input())
dp=[[0]*(30) for j in range(30)]
ans=[]
memo=-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
             if memo < i:
                 ans.append(t[j])
                 memo = i

        else:
            dp[i+1][j+1] =max(dp[i][j+1],dp[i+1][j])

#print(dp[len(s)][len(t)])
answer=[]
i,j=len(s),len(t)
d=dp[i-1][j-1]
while i!=0 and j!=0:
    if dp[i-1][j-1]!=dp[i][j]:
        answer.append(s[i-1])
        i-=1
        j-=1
    elif dp[i-1][j]==dp[i][j]:
        i-=1
    elif dp[i][j-1]==dp[i][j]:
        j-=1
print("".join(reversed(answer)))

Submission status: Runtime Error

Solution code:
s=list(input())
t=list(input())
dp=[[0]*(30) for j in range(30)]
ans=[]
memo=-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
             if memo < i:
                 ans.append(t[j])
                 memo = i

        else:
            dp[i+1][j+1] =max(dp[i][j+1],dp[i+1][j])

#print(dp[len(s)][len(t)])
answer=[]
i,j=len(s),len(t)
d=dp[i-1][j-1]
while i!=0 or j!=0:
    if dp[i-1][j-1]!=dp[i][j]:
        answer.append(s[i-1])
        i-=1
        j-=1
    elif dp[i-1][j]==dp[i][j]:
        i-=1
    else:
        j-=1
print("".join(reversed(answer)))

Submission status: Runtime Error

Solution code:
s=list(input())
t=list(input())
dp=[[0]*(30) for j in range(30)]
ans=[]
memo=-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
             if memo < i:
                 ans.append(t[j])
                 memo = i

        else:
            dp[i+1][j+1] =max(dp[i][j+1],dp[i+1][j])

#print(dp[len(s)][len(t)])
answer=[]
i,j=len(s),len(t)
d=dp[i-1][j-1]
while i!=0 and j!=0:
    if dp[i-1][j-1]!=dp[i][j]:
        answer.append(s[i-1])
        i-=1
        j-=1
    elif dp[i-1][j]==dp[i][j]:
        i-=1
    else:
        j-=1
print("".join(reversed(answer)))

Submission status: Runtime Error

Solution code:
s = input()
t = input()
len_s = len(s)
len_t = len(t)
dp = [[0]*(len_t+1) for _ in range(len_s+1)]
# dp[i][j]はs[i],t[j]までで、最長の部分列の長さ
for i in range(len_s):
    for j in range(len_t):
        if s[i] == t[i]:
            dp[i+1][j+1] = max(dp[i][j]+1, dp[i+1][j], dp[i][j+1])

        dp[i+1][i+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])
#print(dp)
ans = ""
while len_t>0 and len_s>0:
    if dp[len_s][len_t] == dp[len_s-1][len_t]:
        len_s -= 1
    elif dp[len_s][len_t] == dp[len_s][len_t-1]:
        len_t -= 1
    else:
        ans += s[len_s-1]
        len_s -= 1
        len_t -= 1
print(ans[::-1])

Submission status: Runtime Error

Solution code:
s = input()
t = input()
len_s = len(s)
len_t = len(t)
dp = [[0]*(len_t+1) for _ in range(len_s+1)]
# dp[i][j]はs[i],t[j]までで、最長の部分列の長さ
for i in range(len_s):
    for j in range(len_t):
        if s[i] == t[i]:
            dp[i+1][j+1] = max(dp[i][j]+1, dp[i+1][j], dp[i][j+1])
        else:
            dp[i+1][i+1] = max(dp[i+1][j], dp[i][j+1])
#print(dp)
ans = ""
while len_t>0 and len_s>0:
    if dp[len_s][len_t] == dp[len_s-1][len_t]:
        len_s -= 1
    elif dp[len_s][len_t] == dp[len_s][len_t-1]:
        len_t -= 1
    else:
        ans += s[len_s-1]
        len_s -= 1
        len_t -= 1
print(ans[::-1])

Submission status: Runtime Error

Solution code:
s = input()
t = input()
len_s = len(s)
len_t = len(t)
dp = [[0]*(len_t+1) for _ in range(len_s+1)]
# dp[i][j]はs[i],t[j]までで、最長の部分列の長さ
for i in range(len_s):
    for j in range(len_t):
        if s[i] == t[i]:
            dp[i+1][j+1] = max(dp[i][j]+1, dp[i+1][j], dp[i][j+1])
        else:
            dp[i+1][i+1] = max(dp[i+1][j], dp[i][j+1])
print(dp)
ans = ""
while len_t>0 and len_s>0:
    if dp[len_s][len_t] == dp[len_s-1][len_t]:
        len_s -= 1
    elif dp[len_s][len_t] == dp[len_s][len_t-1]:
        len_t -= 1
    else:
        ans += s[len_s-1]
        len_s -= 1
        len_t -= 1
print(ans[::-1])

Submission status: Runtime Error

Solution code:
S = input()
T = input()
m, n = len(S), len(T)
DP = [[0 for j in range(n+1)] for i 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] = DP[i-1][j-1] + 1
        else:
            DP[i][j] = max(DP[i][j-1], DP[i-1][j])
X = ''
i, j = m, n
while len(X) < DP[m][n]:
    if DP[i][j] == DP[i-1][j-1]+1:
        i -= 1
        j -= 1
        l += 1
        X = S[i-1]+X
    elif DP[i][j] == DP[i-1][j]:
        i -= 1
    elif DP[i][j] == DP[i][j-1]:
        j -= 1
print(X)

Submission status: Runtime Error

Solution code:

def find(s,t):
    if (len(s)==0 or len(t)==0):
        return ""
    if(s[0]==t[0]):
        if(len(s)==1 or len(t)==1):
            return s[0]
        return s[0]+find(s[1:],t[1:])
    x=y=""
    if(len(t)>1):
        x=find(s[::],t[1:])
    if(len(s)>1):
        y=find(s[1:],t[::])
    if(len(x)>len(y)):
        return x
    else:
        return y
def solve():
    s=input()
    t=input()
    ans=find(s,t)
    print(ans)

solve()

Submission status: Runtime Error

Solution code:
def find(s,t):
    if (len(s)==0 or len(t)==0):
        return ""
    if(s[0]==t[0]):
        if(len(s)==1 or len(t)==1):
            return s[0]
        return s[0]+find(s[1:],t[1:])
    x=y=""
    if(len(t)>1):
        x=find(s,t[1:])
    if(len(s)>1):
        y=find(s[1:],t)
    if(len(x)>len(y)):
        return x
    else:
        return y
def solve():
    s=input()
    t=input()
    ans=find(s,t)
    print(ans)

solve()

Submission status: Runtime Error

Solution code:
def localInp():
    import sys
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')

def find(s,t):
    if (len(s)==0 or len(t)==0):
        return ""
    if(s[0]==t[0]):
        if(len(s)==1 or len(t)==1):
            return s[0]
        return s[0]+find(s[1:],t[1:])
    x=y=""
    if(len(t)>1):
        x=find(s,t[1:])
    if(len(s)>1):
        y=find(s[1:],t)
    if(len(x)>len(y)):
        return x
    else:
        return y
def solve():
    s=input()
    t=input()
    ans=find(s,t)
    print(ans)

#solve()



localInp()
# t=int(input())
t=1
for i in range(t):
    # print("Case",i+1)
    solve()

Submission status: Runtime Error

Solution code:
def localInp():
    import sys
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')

def find(s,t):
    if (len(s)==0 or len(t)==0):
        return ""
    if(s[0]==t[0]):
        if(len(s)==1 or len(t)==1):
            return s[0]
        return s[0]+find(s[1:],t[1:])
    x=y=""
    if(len(t)>1):
        x=find(s,t[1:])
    if(len(s)>1):
        y=find(s[1:],t)
    if(len(x)>len(y)):
        return x
    else:
        return y
def solve():
    s=input()
    t=input()
    ans=find(s,t)
    print(ans)

#solve()



localInp()
t=int(input())
for i in range(t):
    print("Case",i+1)
    solve()

Submission status: Runtime Error

Solution code:
def LCS_iter(s1, s2):
	dp = [[-10000 for i in range(len(s2) + 1)] for i in range(len(s1) + 1)]
	ans = [['' for i in range(len(s2) + 1)] for i in range(len(s1) + 1)]
	for i in range(len(s2) + 1):
		dp[0][i] = 0
	for i in range(len(s1) + 1):
		dp[i][0] = 0
	i = 1
	j = 1
	while i <= len(s1):
		while j <= len(s2):
			if s1[i - 1] == s2[j - 1]:
				dp[i][j] = 1 + dp[i - 1][j - 1]
				ans[i][j] = 'cross'
			else:
				if dp[i - 1][j] > dp[i][j - 1]:
					dp[i][j] = dp[i - 1][j]
					ans[i][j] = 'up'
				else:
					dp[i][j] = dp[i][j - 1]
					ans[i][j] = 'left'
			j += 1
		i += 1
		j = 1
	i = len(s1)
	j = len(s2)
	s = ''
	while i >= 0 and j >= 0:
		if ans[i][j] == 'cross':
			s += f'{s1[i - 1]}'
			i -= 1
			j -= 1
		elif ans[i][j] == 'up':
			i -= 1
		else:
			j -= 1
	return s[::-1]


s1 = input()
s2 = input()

print(LCS_iter(s1, s2))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


s=input()
t=input()
dp1=[0]*len(s)
for i in range(len(t)):
    m=0
    dp2=dp1.copy()
    for j in range(len(s)):
        if s[j]==t[i]:
            dp2[j]=max(m+1,dp1[j])
        m=max(m,dp1[j])
    dp1=dp2.copy()

dp3=[0]*len(s)
for i in range(len(t)-1,-1,-1):
    m=0
    dp2=dp3.copy()
    for j in range(len(s)-1,-1,-1):
        if s[j]==t[i]:
            dp2[j]=max(m+1,dp3[j])
        m=max(m,dp3[j])
    dp3=dp2.copy()

m=max(dp1)
cnt=max(dp1)
ans=''
for j in range(len(s)-1,-1,-1):
    if dp1[j]>=cnt and dp3[j]>=m-cnt+1:
        ans=s[j]+ans
        cnt-=1
    if cnt==0:
        break
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


s=data()
t=data()
dp1=[0]*len(s)
for i in range(len(t)):
    m=0
    dp2=dp1.copy()
    for j in range(len(s)):
        if s[j]==t[i]:
            dp2[j]=max(m+1,dp1[j])
        m=max(m,dp1[j])
    dp1=dp2.copy()

dp3=[0]*len(s)
for i in range(len(t)-1,-1,-1):
    m=0
    dp2=dp3.copy()
    for j in range(len(s)-1,-1,-1):
        if s[j]==t[i]:
            dp2[j]=max(m+1,dp3[j])
        m=max(m,dp3[j])
    dp3=dp2.copy()

m=max(dp1)
cnt=max(dp1)
ans=''
for j in range(len(s)-1,-1,-1):
    if dp1[j]>=cnt and dp3[j]>=m-cnt+1:
        ans=s[j]+ans
        cnt-=1
    if cnt==0:
        break
print(ans)

Submission status: Runtime Error

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

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

dp = np.array([0]*(len_t+1) for _ in range(len_s+1))
route = np.array([[0,0]]*(len_t+1) for _ in range(len_s+1))

for i in range(len_s+1):
    for j in range(len_t+1):
        route[i][j] = [0,0]


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
            route[i+1][j+1] = [i,j]
        if dp[i+1][j+1] < dp[i+1][j]:
            dp[i+1][j+1] = dp[i+1][j]
            route[i+1][j+1] = [i+1,j]
        if dp[i+1][j+1] < dp[i][j+1]:
            dp[i+1][j+1] = dp[i][j+1]
            route[i+1][j+1] = [i,j+1]

i = len_s
j = len_t 
ans = ""

while i > 0 and j > 0:
    i, j = route[i][j][0], route[i][j][1]
    if i >= len_s or j >= len_t:
        continue
    if s[i] == t[j]:
        ans += s[i]

ans = ans[::-1]
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
s=np.array(list(input()))
t=np.array(list(input()))
is_eq=np.array(s[:,None]==t[None,])
# is_eq[i][j]:sのi文字目とtのj文字目が等しいかどうか
# print(is_eq)
ns=len(s)
nt=len(t)
dp=np.zeros((ns+1,nt+1),np.int64)
print(dp.shape)
print(is_eq.shape)

# dp[i+1][j+1]:sのi文字目までとtのj文字目までで最長の部分裂の長さ
# dp[0][j]=0,dp[i][0]=0,
for i in range(ns): #sのi文字目までの文字列で調査
    dp[i+1][1:]=np.maximum(dp[i][:-2]+is_eq[i],dp[i+1][:-1],dp[i][1:])
print(dp)
print(is_eq)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())

G=[[] for _ in range(N+1)]  #G[0]はダミー
for edge in range(M):
    x,y=map(int,input().split())
    G[x].append(y)

DP=[-1]*(N+1)   #DP[0]はダミー

def rec(now):
    global G

    if DP[now]!=-1:
        return DP[now]

    else:
        res=0
        for next in G[now]:
            res=max(res,rec(next)+1)
        DP[now]=res
        return res

ans=0
for v in range(1,N+1):
    ans=max(ans,rec(v))

print(ans)

Submission status: Runtime Error

Solution code:
s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
def al(str):
    return alphabetlist.index(str)+1

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

firsts=N
for i in range(0,N):
    if s[i]==t[0]:
        firsts=i
        break

firstt=M
for i in range(0,M):
    if t[i]==s[0]:
        firstt=i
        break

for i in range(0,N):
    if i>=firsts:
        dp[i][0]=1

for i in range(0,M):
    if i>=firstt:
        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]

ans=[]
i=N-1
j=M-1
while i>-1:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    else:
        while s[i]==t[j]:
            j-=1
        ans.append(s[i])
        i-=1
        
ans=ans[::-1]
print(''.join(ans))