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:
#EDP-F
import sys

S = sys.stdin.readline().rstrip()
T = sys.stdin.readline().rstrip()
sn, tn = len(S), len(T)
dp = [[0 for j in range(tn)] for i in range(sn)]

#方針:その時点での最長数を入れる
for j in range(tn):
    dp[0][j] = dp[0][j-1]
    if S[0]==T[j]:
        dp[0][j] = 1
for i in range(sn):
    dp[i][0] = dp[i-1][0]
    if S[i]==T[0]:
        dp[i][0] = 1
        

for i in range(1, sn):
    for j in range(1, tn):
        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])

#pprint.pprint(dp)

i,j= sn-1, tn-1
ans =''
while True:
    if i ==0:
        if dp[i][j]==1:
            ans+= S[0]
        print(ans[::-1])
        break
    if dp[i-1][j] == dp[i][j]:
        i-=1
    elif dp[i][j-1] == dp[i][j]:
        j-=1
    elif dp[i-1][j-1] +1 == dp[i][j]:
        ans += S[i]
        i-=1
        j-=1

Submission status: Runtime Error

Solution code:
# size of s - m and size of t is n
# LCS[i,j] - longest common subsequence ending at index i in s and j in t
# LCS[i,j] = a +  LCS[i-1,j-1] if s[i]==t[j]=a and i<m and i<n
# 	   = max_len(LCS[i-1,j],LCS[i,j-1]) if i<m and i<n
# 	      LCS[0,j] if i<0
# 	      LCS[i,0] if j<0
def lcs(s,t,m,n,LCS):
	if m<0:
		return ""
	elif n<0:
		return ""
	elif LCS[n][m]!=-1:
		return LCS[n][m]
	elif s[m]==t[n]:
		LCS[n][m] = lcs(s,t,m-1,n-1,LCS)+s[m]
	else:
		if len(lcs(s,t,m-1,n,LCS)) >= len(lcs(s,t,m,n-1,LCS)):
			LCS[n][m] = lcs(s,t,m-1,n,LCS)
		else:
			LCS[n][m] = lcs(s,t,m,n-1,LCS)
	return LCS[n][m]

s = input()
t = input()
LCS = [[-1]*len(s) for i in range(len(t))]
print(lcs(s,t,len(s)-1,len(t)-1,LCS))

Submission status: Runtime Error

Solution code:
s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for i in range(m+1)] for j in range(n+1)]
​
​
#メイン
​
#dp[i][j]:=s_1~s_iとt_1~t_jに対するLCSの長さ
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])
#print(dp[n][m])
#dpを逆からたどって文字列を復元
ans = ''
while(dp[n][m]>0):
  if dp[n][m] == dp[n-1][m-1] +1 and dp[n][m] == dp[n-1][m] +1 and dp[n][m] == dp[n][m-1] +1:
    ans += s[n-1]
    n -= 1
    m -= 1
  elif dp[n-1][m] > dp[n][m-1]:
    n -= 1
  else:
    m -= 1
print(''.join(reversed(list(ans))))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
d=[[] for i in range(N)]
for i in range(M):
    x,y=map(int,input().split())
    d[x-1].append(y-1)
scores=[]
def depth(now,score):
    global scores
    if d[now]:
        for i in d[now]:
            depth(i,score+1)
    else:
        scores.append(score)
Max=0
for i in range(N):
    depth(i,0)
    if scores and max(scores)>Max:
        Max=max(scores)
    scores.clear()
print(Max)

Submission status: Runtime Error

Solution code:
s=input()
t=input()
L=[]
for i in s:
	for j in range(len(t)):
		if(t[j]==i):
			L.append([j,i])
for i in range(len(L)-2,-1,-1):
	maxlen=0
	maxstr=''
	for j in range (i+1,len(L)):
		if(L[j][0]>L[i][0] and len(L[j][1])>maxlen):
			maxlen=len(L[j][1])
			maxstr=L[j][1]
	L[i][1]=L[i][1]+maxstr
print(L[0][1])

Submission status: Runtime Error

Solution code:
# EDP F-LCS
import sys
input = sys.stdin.readline

ans = ""

def main():
    S = input()
    T = input()
    LS = len(S)
    LT = len(T)
    dp = [[0 for j in range(LT+1)] for i in range(LS+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:
                if dp[i+1][j] >= dp[i][j+1]:
                    dp[i+1][j+1] = dp[i+1][j]
                else:
                    dp[i+1][j+1] = dp[i][j+1]

    def rec(i, j):
        if i == 0 or j == 0:
            return

        if S[i-1] == T[j-1]:
            global ans
            ans += S[i-1]
            rec(i-1, j-1)
        elif dp[i-1][j] > dp[i][j-1]:
            rec(i-1, j)
        else:
            rec(i, j-1)

    rec(LS, LT)
    print(ans[::-1])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# EDP F-LCS
import sys
input = sys.stdin.readline


def main():
    S = input()
    T = input()

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

    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if s == t:
                dp[i+1][j+1] = [dp[i][j][0]+1, dp[i][j][1]+s[i]]
            else:
                if dp[i+1][j][0] >= dp[i][j+1][0]:
                    dp[i+1][j+1] = dp[i+1][j]
                else:
                    dp[i+1][j+1] = dp[i][j+1]

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
def main():
  S=list(sys.stdin.readline())[:-1]
  T=list(sys.stdin.readline())[:-1]
  lS=len(S)
  lT=len(T)
  dp=[[0]*lS for _ in range(lT)]
  for iT in range(lT):
    for iS in range(lS):
      if S[iS]==T[iT]:
        if iS-1>=0 and iT-1>=0:
          dp[iT][iS] = dp[iT-1][iS-1]+1
        else:
          dp[iT][iS] = 1
      else:
        if iS-1>=0 and (iT-1<0 or dp[iT][iS-1]>=dp[iT-1][iS]):
          dp[iT][iS] = dp[iT][iS-1]
        elif iT-1>=0 and (iS-1<0 or dp[iT-1][iS]>=dp[iT][iS-1]):
          dp[iT][iS] = dp[iT-1][iS]

  iS = lS-1
  iT = lT-1
  ans = ""
  while(iS>0 and iT>0):
    if dp[iT][iS]==dp[iT-1][iS-1]:
      iS -= 1
      iT -= 1
    elif dp[iT][iS]==dp[iT][iS-1]:
      iS -= 1
    else:
      ans = S[iS]+ans
      iS -= 1
      iT -= 1
  if dp[iT][iS]=1:
    if iS == 0:
      ans = S[0]+ans
    else:
      ans = T[0]+ans
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Runtime Error

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

lA = len(a)
lB = len(b)

memo={}

def LCS(i,j):
    if (i,j) in memo:
        return memo[(i,j)]
    if (i>=lA) or (j>=lB):
        ret = ''
    elif a[i]==b[j]:
        ret = a[i]+LCS(i+1,j+1)
    else:
        x,y = LCS(i+1,j),LCS(i,j+1)
        ret = (x if len(x)>len(y) else y)
    memo[(i,j)] = ret
    return ret

print(LCS(0,0))

Submission status: Runtime Error

Solution code:
import sys
def main():
  S=list(input())
  T=list(input())
  lS=len(S)
  lT=len(T)
  ans=[[]*lS for _ in range(lT)]
  for iT in range(lT):
    for iS in range(lS):
      if S[iS]==T[iT]:
        if iS-1>=0 and iT-1>=0:
          ans[iT][iS]=ans[iT-1][iS-1]+S[iS]
        else:
          ans[iT][iS]=S[iS]
      else:
        if iS-1>=0 and (iT-1<0 or len(ans[iT][iS-1])>=len(ans[iT-1][iS])):
          ans[iT][iS]=ans[iT][iS-1]
        elif iT-1>=0 and (iS-1<0 or len(ans[iT-1][iS])>=len(ans[iT][iS-1])):
          ans[iT][iS]=ans[iT-1][iS]
  print(ans[lT-1][lS-1])

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
S=input()
T=input()
lS=len(s)
lT=len(t)
ans=[[""]*lS for _ in range(lT)]
for iT in range(lT):
  for iS in range(lS):
    if S[iS]==T[iT]:
      if iS-1>=0 and iT-1>=0:
        ans[iT][iS]=ans[iT-1][iS-1]+S[iS]
      else:
        ans[iT][iS]=S[iS]
    else:
      if iS-1>=0 and (iT-1<0 or len(ans[iT][iS-1])>=len(ans[iT-1][iS])):
        ans[iT][iS]=ans[iT][iS-1]
      elif iT-1>=0 and (iS-1<0 or len(ans[iT-1][iS])>=len(ans[iT][iS-1])):
        ans[iT][iS]=ans[iT-1][iS]
print(ans[lT-1][lS-1])

Submission status: Runtime Error

Solution code:
# 最長共通部分　LCS ***未完成***
strA = input()
strB = input()
### 一致したら左上+1、そうでない場合は上か左のMAX
# / | 0 | A | B | C | B | A |
# 0 | 0 | 0 | 0 | 0 | 0 | 0 |
# B | 0 | 0 | 1 | 1 | 1 | 1 |
# B | 0 | 0 | 1 | 1 | 2 | 2 |
# A | 0 | 0 | 1 | 1 | 2 | 3 |
dp = [[0] * (len(strA) + 1) for _ in range(len(strB) + 1)]

for i, A in enumerate(strA, 1):
    for j, B in enumerate(strB, 1):
        if A == B:
            dp[j][i] = dp[j - 1][i - 1] + 1
        else:
            dp[j][i] = max(dp[j - 1][i], dp[j][i - 1])
ans = ""
cnt = 1
lstAns = dp[-1]
x, y = len(strB), len(strA)
while x > 0 and y > 0:
    if dp[x][y] == dp[x - 1][y]:
        x -= 1
    elif dp[x][y] == dp[x][y - 1]:
        y -= 1
    else:
        ans = strA[x] + ans
        x -= 1
        y -= 1
print(ans)

Submission status: Runtime Error

Solution code:
# 最長共通部分　LCS
strA = input()
strB = input()
### 一致したら左上+1、そうでない場合は上か左のMAX
# / | 0 | A | B | C | B | A |
# 0 | 0 | 0 | 0 | 0 | 0 | 0 |
# B | 0 | 0 | 1 | 1 | 1 | 1 |
# B | 0 | 0 | 1 | 1 | 2 | 2 |
# A | 0 | 0 | 1 | 1 | 2 | 3 |
dp = [[0] * (len(strA) + 1) for _ in range(len(strB) + 1)]

for i, A in enumerate(strA, 1):
    for j, B in enumerate(strB, 1):
        if A == B:
            dp[j][i] = dp[j - 1][i - 1] + 1
        else:
            dp[j][i] = max(dp[j - 1][i], dp[j][i - 1])
ans = ""
cnt = 1
lstAns = dp[-1]
for DP in lstAns:
    if cnt == DP:
        cnt += 1
        ans += strB[cnt - 1]
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
s = input()
t = input()
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1] , dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i][j+1] , dp[i+1][j] ,dp[i+1][j+1])
print(dp)
dp = np.array(dp).T
for i in range(1,len(s) + 1):
    if dp[len(t)][i] != dp[len(t)][i - 1]:
        print(s[i-1] , end = '')

Submission status: Runtime Error

Solution code:
from collections import deque 

S = input()
T = input()
ans = []
dp = [[0] * (len(T)) for _ in range(len(S))]
for i in range(0, len(T)-1):
  if T[i] == S[0]:
    dp[0][i] = 1
  dp[0][i+1] = dp[0][i]
for i in range(0, len(S)-1):
  if S[i] == T[0]:
    dp[i][0] = 1
  dp[i+1][0] = dp[i][0]
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
    else:
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])
i, j = len(S)-1, len(T)-1
max_len = dp[i][j]
ans = []
dp[i][j] = -1
while len(ans) < max_len:
  while dp[i][j] == dp[i-1][j]:
    i -= 1
  while dp[i][j] == dp[i][j-1]:
    j -= 1
  ans.append(S[i])
  i -= 1
  j -= 1
print(''.join(ans[::-1])

Submission status: Runtime Error

Solution code:
S = input()
T = input()
ans = []
dp = [[0] * (len(T)) for _ in range(len(S))]
for i in range(0, len(T)-1):
  if T[i] == S[0]:
    dp[0][i] = 1
  dp[0][i+1] = dp[0][i]
for i in range(0, len(S)-1):
  if S[i] == T[0]:
    dp[i][0] = 1
  dp[i+1][0] = dp[i][0]
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
    else:
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])
i, j = len(S)-1, len(T)-1
ans = []
while i >= 0 and j >= 0:
  if S[i] == T[i]:
    ans.append(S[i])
    i -= 1
    j -= 1
  else:
    if dp[i-1][j] > dp[i][j-1]:
      i -= 1
    else:
      j -= 1
print(''.join(ans[::-1]))

Submission status: Runtime Error

Solution code:
S = input()
T = input()
ans = []
dp = [[0] * (len(T)) for _ in range(len(S))]
for i in range(0, len(T)-1):
  if T[i] == S[0]:
    dp[0][i] = 1
  dp[0][i+1] = dp[0][i]
for i in range(0, len(S)-1):
  if S[i] == T[0]:
    dp[i][0] = 1
  dp[i+1][0] = dp[i][0]
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
    else:
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])
i, j = len(S)-1, len(T)-1
ans = []
while i >= 0 and j >= 0:
  if S[i] == T[i]:
    ans.append(S[i])
  else:
    if dp[i-1][j] > dp[i][j-1]:
      i -= 1
    else:
      j -= 1
print(''.join(ans[::-1]))

Submission status: Runtime Error

Solution code:
s = input()
t = input()
dp - [[0 for _ in rannge(len(s)+1)] for i in range(len(t)+1)]
for i in range(len(s)+1):
    dp[i][0] = 0
for j in range(len(t)+1):
    dp[0][j] = 0
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1] == t[i-1]:
            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)][len(t)])

Submission status: Runtime Error

Solution code:
a = list(map(str,input()))
b = list(map(str,input()))
#print(a,b)

n1 = len(a)
n2 = len(b)
#print(n1,n2)

mat = [[0 for i in range(n1+1)] for j in range(n2+1)]

for i in range(n1):
    mat[0][i] = 0
for j in range(n2):
    mat[j][0] = 0

for j in range(1,n2+1):
    for i in range(1,n1+1):
        if a[i-1] == b[j-1]:
            mat[j][i] = max(max(mat[j-1][i],mat[j][i-1]),mat[j-1][i-1]+1)
        else:
            mat[j][i] = max(mat[j-1][i],mat[j][i-1])

'''            
for i in range(n1):
    mat[0][i+1] = a[i]
for j in range(n2):
    mat[j+1][0] = b[j]


for j in range(0,n2+1):
    for i in range(0,n1+1):
        print(mat[j][i],end = " ")
    print("")
    
'''
    
i = n1 
j = n2
n = 0

list_val = []
len_val = mat[-1][-1]
#print(len_val)
while i >= 2 and j >=2 :
    if mat[j][i] == mat[j][i-1]:
        i = i-1
    else:
        list_val.append(a[i-1])
        i = i-1
        j = j-1
        n = n+1 
        if n == len_val:
            break
#print(list_val)
for i in range(len_val):
    print(list_val[i],end = "")

Submission status: Runtime Error

Solution code:
#include "bits/stdc++.h"
using namespace std;


// =========================== DEBUGGER =================================

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ((it == d.b) ? "" : ", ") << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define tag(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

// =====================================================================







#define ll long long
const ll int INF = 1e15;

int dp[3005][3005];
string s1, s2;


int kil(int idx1, int idx2)
{
  if(idx1 == s1.length() || idx2 == s2.length())
    return 0;
  if(dp[idx1][idx2] != -1)
    return dp[idx1][idx2];

  if(s1[idx1] == s2[idx2])
      dp[idx1][idx2] = max(dp[idx1][idx2], kil(idx1+1, idx2+1) + 1);
  else
  {
    dp[idx1][idx2] = max(dp[idx1][idx2], kil(idx1, idx2+1));
    dp[idx1][idx2] = max(dp[idx1][idx2], kil(idx1+1, idx2));
  }
  return dp[idx1][idx2];
}

int main()
{
  cin>>s1>>s2;
  string res;
  int ans;
  memset(dp, -1, sizeof dp);
  ans = kil(0, 0);

  for(int i=0; i<s1.length(); i++)
  for(int j=0; j<s2.length(); j++) kil(i, j);
  
  
  int i=0, j=0;
  int n = s1.length();
  int m = s2.length();
  while(i!=n && j!=m){
       if (s1[i]==s2[j]){
         cout<<s1[i];
        i+=1;
          j+=1;
    } else{
         if (dp[i][j]==dp[i+1][j]) i+=1;
        else if (dp[i][j]==dp[i][j+1]) j+=1;
        else{
             cout << "ERROR " <<endl; 
        }
      
    }
    
  }
  //cout<<res<<endl;  

  return 0;
}

Submission status: Runtime Error

Solution code:
s = input()
t = input()
dp = [[0] * len(t) for _ in range(len(s))]
for i in range(len(s)):
  if s[i] == t[0]:
    for k in range(i, len(s)):
      dp[k][0] = 1
    break
for j in range(tl):
  if s[0] == t[j]:
    for k in range(j, len(t)):
      dp[0][k] = 1
    break
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
    else:
      dp[i][j] = dp[i - 1][j]
      if dp[i][j] < dp[i][j - 1]:
        dp[i][j] = dp[i][j - 1]
i, j = len(s) - 1, len(t) - 1
u = []
while i >= 0 and j >= 0:
  if s[i] == t[j]:
    u.append(s[i])
    i -= 1
    j -= 1
  elif dp[i][j] == 0:
    break
  elif dp[i - 1][j] == dp[i][j]:
    i -= 1
  else:
    j -= 1
print(''.join(u[::-1]))

Submission status: Runtime Error

Solution code:
s = input()
t = input()
dp = [[-1] * (len(t) + 1) for _ in range(len(s) + 1)]
dp[0][0] = 0
def rec(i, j):
  if dp[i][j] != -1:
    return dp[i][j]
  k = -1
  if i - 1 >= 0:
    k = rec(i - 1, j)
  if j - 1 >= 0:
    k = max(k, rec(i, j - 1))
  if i - 1 >= 0 and j - 1 >= 0 and s[i - 1] == t[j - 1]:
    k = max(k, rec(i - 1, j - 1) + 1)
  dp[i][j] = k
  return dp[i][j]
rec(len(s), len(t))
i = len(s)
j = len(t)
result = ''
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:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)

Submission status: Runtime Error

Solution code:
# AtCoder DP Task F - LCS
def backtrack(C, A, B, i, j):
    if i == 0 or j == 0:
        return ""
    if A[i - 1] == B[j - 1]:
        return backtrack(C, A, B, i - 1, j - 1) + A[i - 1]
    if C[i][j - 1] > C[i - 1][j]:
        return backtrack(C, A, B, i, j - 1)
    return backtrack(C, A, B, i - 1, j)

def lcs(A, B):
    a, b = len(A), len(B)
    C = [ [0] * (b + 1) for _ in range(a + 1) ]
    for i in range(1, a + 1):
        for j in range(1, b + 1):
            if A[i - 1] == B[j - 1]:
                C[i][j] = C[i-1][j-1] + 1
            else:
                C[i][j] = max(C[i][j - 1], C[i - 1][j])
#    return C[a][b]
    ret = backtrack(C, A, B, a, b)
    return ret

assert lcs("XMJYAUZ", "MZJAWXU") == "MJAU"
assert lcs("AGCAT", "GAC") == "AC"
assert lcs("AAAA", "AAAA") == "AAAA"

x = input().strip()
y = input().strip()
ans = lcs(x, y)
print(ans)

Submission status: Runtime Error

Solution code:
def solve(i, j):
    if i == 0 or j == 0:
        return ''
    if dp[i][j] != '-':
        return dp[i][j]
    c = s[-i]
    sp = t[-j:].split(c, maxsplit=1)
    if len(sp) == 1:
        dp[i][j] = solve(i - 1, j)
    else:
        if len(solve(i - 1, len(sp[1]))) + 1 >= len(solve(i - 1, j)):
            dp[i][j] = c + solve(i - 1, len(sp[1]))
        else:
            dp[i][j] = solve(i - 1, j)
    return dp[i][j]


s = input()
t = input()
dp = [['-'] * (len(t) + 1) for _ in range(len(s) + 1)]
print(solve(len(s), len(t)))

Submission status: Runtime Error

Solution code:
def solve(s, t):
    if s == '' or t == '':
        return ''
    c = s[0]
    sp = t.split(c, maxsplit=1)
    if len(sp) == 1:
        return solve(s[1:], t)
    else:
        if len(solve(s[1:], sp[1])) + 1 >= len(solve(s[1:], t)):
            return c + solve(s[1:], sp[1])
        else:
            return solve(s[1:], t)


s = input()
t = input()
print(solve(s, t))

Submission status: Runtime Error

Solution code:
import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner in = new Scanner(System.in);
        String s = in.next();
        String t = in.next();
        int n = s.length();
        int m = t.length();
        String dp[][] = new String[n+1][m+1];
        in.close();
        for(int i=0;i<=n;i++){
            dp[i][0] = "";
        }
        for(int j=0;j<=m;j++){
            dp[0][j] = "";
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if (s.charAt(i) == t.charAt(j)){
                    dp[i+1][j+1] = dp[i][j]+s.charAt(i);
                }
                else{
                    if (dp[i][j+1].length() >= dp[i+1][j].length()){
                        dp[i+1][j+1] = dp[i][j+1];
                    }
                    else{
                        dp[i+1][j+1] = dp[i+1][j];
                    }
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}

Submission status: Runtime Error

Solution code:
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
Mod = 1000000007



def main(): #startline-------------------------------------------
    s = input()
    n = len(s)
    t = input()
    m = len(t)
    dp = [[""]*(m+1) for i in range(n+1)] #dp[i][j]...s_iとt_jの共通部分列の長さ
    for i in range(n+1):
        dp[0][i],dp[i][0] = "",""
    for i in range(n):
        for j in range(m):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+s[i]
            else:
                dp[i+1][j+1] = (dp[i][j+1] if len(dp[i][j+1])>=len(dp[i+1][j]) else dp[i+1][j])
    print(dp[n][m])
if __name__ == "__main__":
    main() #endline===============================================




def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n < 2 is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))):
        if prime[i] == 1:
            for j in range(2*i,n):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n):
        if prime[i] == 1:
            res.append(i)
    return res

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py

    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

Submission status: Runtime Error

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

cross = [((si, ti), s[si]) for si in range(len(s)) for ti in range(len(t)) if s[si] == t[ti]]
if len(cross) == 0:
    print('')
    exit
seq = {c:(s[c[0][0]], 1) for c in cross}

lc = len(cross)
for i in range(lc):
    li = seq[cross[i]][1]
    for j in range(i+1, lc):
        if cross[i][0][0] < cross[j][0][0] and cross[i][0][1] < cross[j][0][1] and li + 1 > seq[cross[j]][1]:
            seq[cross[j]] = (seq[cross[i]][0] + cross[j][1], li + 1)

print(max(seq.values(), key=lambda x: x[1])[0])

Submission status: Runtime Error

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

cross = [(si, ti) for si in range(len(s)) for ti in range(len(t)) if s[si] == t[ti]]
ch = {c:s[c[0]] for c in cross}
seq = ch.copy()

lc = len(cross)
for i in range(lc):
    li = len(seq[cross[i]])
    for j in range(i+1, lc):
        if cross[i][0] < cross[j][0] and cross[i][1] < cross[j][1] and li + 1 >len(seq[cross[j]]):
            seq[cross[j]] = seq[cross[i]] + ch[cross[j]]

print(max(seq.values(), key=len))

Submission status: Runtime Error

Solution code:

s, t = input(), input()
ls, lt = map(len,[s,t])

cls_list = [ [ 0 for j in range(lt+1) ] for i in range(ls+1) ]

    

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


ans = []
k = ls - cls_list[-1][-1]

for i in range(lt):
    if cls_list[k][i] != cls_list[k+1][i+1]:
        k += 1
        ans.append(t[i])


print("".join(ans))

Submission status: Runtime Error

Solution code:
#EDPC
s = list(str(input()))
t = list(str(input()))
dp = [["" for i in range(len(t)+1)] for j in range(len(t)+1)]

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

Submission status: Runtime Error

Solution code:
# A Naive recursive Python implementation of LCS problem 

def lcs(X, Y, m, n): 

	if m == 0 or n == 0: 
		return (0, '');
	elif X[m-1] == Y[n-1]:
		c = lcs(X, Y, m-1, n-1)
		return (1 + c[0], c[1]+Y[n-1]);
	else:
		a = lcs(X, Y, m, n-1)
		b = lcs(X, Y, m-1, n)
		if a[0] > b[0] :
			return a
		else:
			return b


# Driver program to test the above function 
X = str(input())
Y = str(input())
print (lcs(X , Y, len(X), len(Y))[1])

Submission status: Runtime Error

Solution code:
# A Naive recursive Python implementation of LCS problem 

def lcs(X, Y, m, n): 

	if m == 0 or n == 0: 
		return (0, '');
	elif X[m-1] == Y[n-1]:
		c = lcs(X, Y, m-1, n-1)
		return (1 + c[0], c[1]+Y[n-1]);
	else:
		a = lcs(X, Y, m, n-1)
		b = lcs(X, Y, m-1, n)
		if a[0] > b[0] :
			return a
		else:
			return b


# Driver program to test the above function 
X = input()
Y = input()
print (lcs(X , Y, len(X), len(Y))[1])

Submission status: Runtime Error

Solution code:
a=input()
b=input()
c=[[0 for i in range(len(b)+1)]for j in range(len(a)+1)]

for i in range(0,len(a)):
  for j in range(0,len(b)):
    if a[i]==b[j]:
      c[i+1][j+1]=c[i][j]+1
    c[i+1][j+1]=max(c[i+1][j],c[i][j+1],c[i+1][j+1])
    
i=len(a)
j=len(b)
d=""
while i>0 or j>0:
  if c[i][j]==c[i-1][j]:
    i-=1
  elif c[i][j]==c[i][j-1]:
    j-=1
  else:
    d=a[i-1]+d
    i-=1
    j-=1
print(d)

Submission status: Runtime Error

Solution code:
t = input().rstrip()

ans = ''

if len(s) < len(t):
    s, t = t, s

for si in range(len(s)):
    pos = [-1] * len(t)
    pos2 = [-1] * len(t)
    pre = 0
    for i in range(len(t)):
        pos[i] = s.find(t[i], si + pre)
        if pos[i] >= 0:
            pre += 1
    pos2 = [s.find(t[i], si + i) for i in range(len(t))]
    common = [''] * len(pos)
    dp = [-1] * len(pos)
    end = 0
    for p1, p2 in zip(pos, pos2):
        p = min(p1, p2) if p2 < len(t) else p2
        if p < 0:
            continue
        i = bisect_right(dp, p, 0, end)
        dp[i] = p
        common[i] = s[p]
        if i >= end:
            end += 1
    common = ''.join(common)
    if len(common) > len(ans):
        ans = common

print(ans)

Submission status: Runtime Error

Solution code:
#include <stdio.h>
#include <string.h>

void chmax(int *a, int b){
  if(*a < b) *a = b;
}

int main(void){
  char s[3010], t[3010];
  scanf("%s", s);
  scanf("%s", t);

  int N, M;
  N = strlen(s);
  M = strlen(t);

  int dp[N+1][M+1];
  for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= M; j++) {
      dp[i][j] = 0;
    }
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      if(s[i] == t[j]) chmax(&dp[i+1][j+1], dp[i][j]+1);
      chmax(&dp[i+1][j+1], dp[i+1][j]);
      chmax(&dp[i+1][j+1], dp[i][j+1]);
    }
  }

  char tmp[3010];
  int num = 0;
  while(N > 0 && M > 0){
    if(dp[N][M] == dp[N-1][M]) N--;
    else if(dp[N][M] == dp[N][M-1]) M--;
    else{
      N--, M--;
      tmp[num++] = s[N];
    }
  }

  char ans[3010];
  for (int i = 0; i < num; i++) {
    ans[i] = tmp[num-i-1];
  }

  printf("%s\n", ans);

  return 0;
}