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: Accepted

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

l_s = len(s)
l_t = len(t)

dp = [[0] * (l_t + 1) for i in range(l_s + 1)]

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

if dp[l_s][l_t] == 0:
    print(" ")
    exit()

ans = ""
i = l_t
j = l_s

while i > 0 and j > 0:
    if s[j - 1] == t[i - 1]:
        ans += s[j - 1]
        i -= 1
        j -= 1
    else:
        if dp[j - 1][i] > dp[j][i - 1]:
            j -= 1
        else:
            i -= 1

print(ans[::-1])

Submission status: Accepted

Solution code:
s = input()
t = input()
dp = [0]
lcs = ['']
for b in t:
    search_idx = 0
    ncs = lcs[:]
    for i, curr_idx in enumerate(dp):
        char_idx = s.find(b, search_idx)
        if char_idx == -1:
            break
        next_idx = char_idx + 1
        if next_idx < curr_idx:
            dp[i] = next_idx
            ncs[i] = lcs[i - 1] + b
        search_idx = curr_idx
    else:
        char_idx = s.find(b, search_idx)
        if char_idx > -1:
            dp.append(char_idx + 1)
            ncs.append(lcs[-1] + b)
    lcs = ncs
print(lcs[-1])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(4000)
a = input()
b = input()
def print_lcs (a, b, lcs, i, j):
    global ans
    if (i == 0 or j == 0):
        return
    if (a[i-1] == b[j-1]):
        print_lcs(a, b, lcs, i - 1, j - 1)
        ans.append(a[i - 1])
    else:
        if lcs[i-1][j] >= lcs[i][j-1]:
            print_lcs(a, b, lcs, i - 1, j)
        else:
            print_lcs(a, b, lcs, i, j - 1)

lcs = [ [0 for j in range(len(b) + 1)] for i in range(len(a)+1) ]

for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        if a[i - 1] == b[j - 1]:
            x = 1
        else:
            x = 0
        lcs[i][j] = max(lcs[i-1][j-1] + x, lcs[i-1][j], lcs[i][j-1])

ans = []
print_lcs(a, b, lcs, len(a), len(b))
print("".join(ans))

Submission status: Runtime Error

Solution code:
class Solution:
	def solve(self,s1,s2,x,y):
		if x==0 or y==0:
			return self.dp[x][y]
		elif self.dp[x][y]!=-1:
			return self.dp[x][y]
		else:
			if s1[x-1]==s2[y-1]:
				self.dp[x][y]=1+self.solve(s1,s2,x-1,y-1)
				return self.dp[x][y]
			else:
				self.dp[x][y]=max(self.solve(s1,s2,x,y-1),self.solve(s1,s2,x-1,y))
				return self.dp[x][y] 
	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		m=len(text1)
		n=len(text2)
		self.dp=[[-1 for i in range(n+1)] for j in range(m+1)]
		for i in range(n+1):
			self.dp[0][i]=0
		for i in range(m+1):
			self.dp[i][0]=0
		self.solve(text1,text2,m,n)
		common=""
		target=1
		for i in range(1,m+1):
			for j in range(1,n+1):
				if self.dp[i][j]==target:
					common+=text1[i-1]
					target+=1
		return common
if __name__ == "__main__":
	s=input()
	t=input()
	obj=Solution()
	ans1=obj.longestCommonSubsequence(s,t)
	print(ans1)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]



s = st()
t = st()


n1 = len(s)
n2 = len(t)

@lru_cache(None)
def dp(i, j):
    if i == n1 or j == n2:return (-1, -1, 0)
    ans = (-1, -1, 0)
    if s[i] == t[j]:return (i + 1, j + 1, dp(i + 1, j + 1)[-1] + 1)
    

    if dp(i + 1, j)[-1] > ans[-1]:ans = (i + 1, j, dp(i + 1, j)[-1])
    if dp(i, j + 1)[-1] > ans[-1]:ans = (i, j + 1, dp(i, j + 1)[-1])
    
    # print(i, j, ans)

    return ans


dp(0, 0)
ans = ''

x, y = 0, 0

while x < n1 and y < n2 and x != -1 and y != -1:
    # print(x, y)
    if s[x] == t[y]:
        ans += s[x]
    x = dp(x, y)[0]
    y = dp(x, y)[1]
    

print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]




s = st()
t = st()


n1 = len(s)
n2 = len(t)

@lru_cache(None)
def dp(i, j):
    if i == n1 or j == n2:return ''
    ans = ''

    curr = s[i]
    ind = j
    while j < n2 and t[j] != curr:
        j += 1
    if j != n2:
        temp = curr + dp(i + 1, j + 1)
        if len(temp) > len(ans):ans = temp
    
    j = ind
    ind = i
    curr = t[j]
    while i < n1 and s[i] != curr:
        i += 1
    if i != n1:
        temp = curr + dp(i + 1, j + 1)
        if len(temp) > len(ans):ans = temp
    
    i = ind

    if len(dp(i + 1, j)) > len(ans):ans = dp(i + 1, j)
    if len(dp(i, j + 1)) > len(ans):ans = dp(i, j + 1)
    

    return ans


print(dp(0, 0))

Submission status: Runtime Error

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

sl = len(s)
tl = len(t)
dp = [["" for i in range(tl+1)] for i in range(sl+1)]

#dp[i][j] sをi文字目、tをj文字目まで求めたときの最大の長さ

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

Submission status: Runtime Error

Solution code:
x=input()
y=input()
mem=[[-1]*(len(x)) for i in range(len(y))]

def fu(x,y,m,n):

    if m==-1or n==-1:
        return 0
    elif x[m]==y[n]:
        if mem[n][m]==-1:
            mem[n][m]=     1+fu(x,y,m-1,n-1)
            return mem[n][m]
        else:
            return mem[n][m]
    else:
        if mem[n][m]==-1:
            mem[n][m]=     max(fu(x,y,m,n-1),fu(x,y,m-1,n))
            return mem[n][m]
        else:
            return mem[n][m]



print(fu(x,y,len(x)-1,len(y)-1))

Submission status: Runtime Error

Solution code:
t = input()
len_t=len(t)
len_s=len(s) 
dp = [[0 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]=dp[i-1][j-1]+1
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])

ans=""
count=np.max(dp)
pos_s=len_s
pos_t=len_t

while(len(ans)!=count):
  if s[pos_s-1]==t[pos_t-1]:
    ans=s[pos_s-1]+ans
    pos_s=pos_s-1
    pos_t=pos_t-1
  elif dp[pos_s][pos_t-1]>=dp[pos_s-1][pos_t]:
    pos_t=pos_t-1
  elif dp[pos_s][pos_t-1]<dp[pos_s-1][pos_t]:
    pos_s=pos_s-1
print(ans)

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

ans=""
l=dp[ls][lt]-1
i=ls-1
j=lt-1
while l>=0:
    if s[i]==t[j]:
        ans=s[i]+ans
        i-=1
        j-=1
        l-=1
    else:
      	if dp[i-1][j]>dp[i][j-1]:
        	i-=1
    	else:
        	j-=1

print(ans)

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

ans=""
l=dp[ls][lt]-1
i=ls-1
j=lt-1
while l>=0:
    if s[i]==t[j]:
        ans=s[i]+ans
        i-=1
        j-=1
        l-=1
    else:
      	if dp[i-1][j]>dp[i][j-1]:
        i-=1
    else:
        j-=1

print(ans)

Submission status: Runtime Error

Solution code:
# 問題F
import numpy as np
import warnings
warnings.filterwarnings('ignore')

s = str(input())
t = str(input())


# dp[i,j]:文字列のiまでと文字列tのjまでの最長一致文字列
dp = np.array([[0] * (len(t)+1)] * (len(s)+1))
dp_str = {}
dp[0,0] = 0
#文字列格納用
dp_str[0,0]=""

for i in range(0, len(s)):
    for j in range(0, len(t)):
        if s[i] == t[j]:
            dp[i+1,j+1] = dp[i,j] + 1
            if dp_str.get((i, j)):
                dp_str[i+1,j+1] = dp_str[i,j] + s[i]
            else:
                dp_str[i+1,j+1] = s[i]
        else:
            if dp[i+1,j] >= dp[i,j+1]:
                dp[i+1,j+1] = dp[i+1,j]
                dp_str[i+1,j+1] = dp_str[i+1,j]
            else:
                dp[i+1,j+1] = dp[i,j+1]
                dp_str[i+1,j+1] = dp_str[i,j+1]

#print(dp[len(s),len(t)])
print(dp_str[len(s),len(t)])

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_f?lang=ja


def lcs(s1,s2):
    n1,n2 = len(s1),len(s2)
    dp = [ [0]*(n2+1) for _ in range(n1+1) ]
    for i in range(1,n1+1):
        for j in range(1,n2+1):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 
            if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]+1
    return dp[-1][-1]



for _ in range(int(input())):
    s1 = input()
    s2 = input()
    ans = lcs(s1,s2)
    print(ans,flush=True)

Submission status: Runtime Error

Solution code:

def solve(s,t,n,m,dp):
    if n<0 or m<0:
            return ''
    if dp[n][m]!=-1:
        return dp[n][m]
    else:
        ans=''
        if s[n]==t[m]:
            ans=s[n]+solve(s,t,n-1,m-1,dp)
            dp[n][m]= ans
        else:
            s1=solve(s,t,n-1,m,dp)
            s2=solve(s,t,n,m-1,dp)
            if len(s1)>len(s2):
                ans=s1
            else:
                ans=s2
            dp[n][m]= ans
        return dp[n][m]


s=input()
t=input()
dp=[[-1]*(len(t)) for i in range(len(s))] 
# print(dp)
solve(s,t,len(s)-1,len(t)-1,dp)
print(dp[-1][-1][::-1])

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std ;
const int N=3e3+1;  
string s , t ; 
int Dp[N][N];
int calc(int i , int j ){
    if(i == s.size() or  j==t.size())return 0 ; 
    if(i>=s.size() or  j>=t.size())return 0 ; 
    int &ret = Dp[i][j]; 
    if(ret!=-1)return ret ; 
    if(s[i]==t[j]) ret =max(ret , 1+calc(i+1,j+1));
    else {
        ret  = max(ret , calc(i,j+1));
        ret = max(ret , calc(i+1,j));
    } 
    return ret ; 
 
}
void printing (int i,int j ){
    
    if(i == s.size() or  j==t.size())return  ; 
    if(i>=s.size() or  j>=t.size())return ; 
    if(calc(i,j)==1+calc(i+1,j+1)){
        cout<<s[i];
        printing(i+1,j+1);
        return ; 
    }
    else if (calc(i,j)==calc(i+1,j))
    { 
        printing(i+1,j);
        return ; 
    }
    else {
    printing(i,j+1);
    return ;} 
}
int main (){ 
 
    cin>>s>>t ; 
    memset(Dp,-1,sizeof Dp);
   calc(0,0);
   printing(0,0);
    return 0 ; 
}

Submission status: Runtime Error

Solution code:
def lcs(s,t):
    m = len(s)
    n = len(t)

    dp = [[0]*(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] = 1+ dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    
    
    substr = ""
    i,j = m,n
    while i!=0 or j!=0:
        if s[i-1] == t[j-1]:
            substr+=s[i-1]
            i-=1
            j-=1
        elif dp[i][j-1]>dp[i-1][j]:
            j-=1
        else:
            i-=1
    return substr[::-1]
    
    

# s = "abracadabra"
# t = "avadakedavra"
# s = "axyb"
# t = "abyxb"
s = input()
t = input()
print(lcs(s,t))

Submission status: Runtime Error

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()



from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count



def ifvalid(i):
    if i<0:
        return False
    return True


def solve():
    s=inp()
    t=inp()
    a=len(s)
    b=len(t)
    dp=[[0 for _ in range(a+5)] for i in range(b+5)]
    for i in range(1,a+1):
        for j in range(1,b+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])
    i=a
    j=b
    ans=""
    while(i>0 and j>0):
        if s[i-1]==t[j-1]:
            ans+=s[i-1]
            i-=1
            j-=1
        else:
            if dp[i-1][j]>dp[i][j-1]:
                i-=1
            else:
                j-=1
    print(ans[::-1])








solve()

Submission status: Runtime Error

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()



from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count



def ifvalid(i):
    if i<0:
        return False
    return True


def solve():
    s=inp()
    t=inp()
    a=len(s)
    b=len(t)
    dp=[[[0,""] for _ in range(a+5)] for i in range(b+5)]
    for i in range(1,a+1):
        for j in range(1,b+1):
            if s[i-1]==t[j-1]:
                dp[i][j]=[dp[i-1][j-1][0]+1,dp[i-1][j-1][1]+s[i-1]]
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    print(dp[a][b][1])








solve()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10**7)
s,t=input(),input()
dp=[[0]*(len(t)+1) for i in range(len(s)+1)]
for i in range(len(s)+1):
    for j in range(len(t)+1):
        if i<len(s):
            dp[i+1][j]=max(dp[i+1][j],dp[i][j])
        if j<len(t):
            dp[i][j+1]=max(dp[i][j+1],dp[i][j])
        if i<len(s) and j<len(t):
            dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+(s[i]==t[j]))
ans=""
def move(i,j):
    global dp,ans
    if dp[i][j]>dp[i-1][j-1] and s[i-1]==t[j-1]:
        ans=s[i-1]+ans
        if dp[i-1][j-1]!=0:
            move(i-1,j-1)
    else:
        if dp[i][j]==dp[i][j-1]:
            move(i,j-1)
        else:
            move(i-1,j)
move(len(s),len(t))
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np

s=input()
t=input()

 
dp=np.full((len(s)+1,len(t)+1),0)
from numba import njit
 
 
@njit('(i8[:],i8[:],)', cache=True)
def process(dp):
    a=len(s)
    b=len(t)
    for i in range(1,1+len(s)):
        for j in range(1,1+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-1][j],dp[i][j-1])
    res=''
    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
            res=s[a]+res
    print(res)
            
process(dp)

Submission status: Runtime Error

Solution code:

def common(s, t):
    if s == '' or t == '':
        return ''

    l = len(s)
    m = len(t)
    u = ''
    ans = ''
    for i in range(l):
        for j in range(m):
            if s[i] == t[j]:
                u += s[i]
                s1 = s[i + 1:]
                t1 = t[j + 1:]
                u += common(s1, t1)
                if len(u) > len(ans):
                    ans = u
                u = '' 

    return ans

s = input()
t = input()

ans = common(s, t)

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# Input#
# n = int(input())
# n, k = map(int, input().split())
# a = list(map(int, input().split()))

s = input()
t = input()

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

for i in range(len(s) + 1):
    memo[i][0] = 0

for i in range(len(t) + 1):
    memo[0][i] = 0


def dp(i, j):
    if memo[i][j] == -1:
        if s[i - 1] == t[j - 1]:
            memo[i][j] = dp(i - 1, j - 1) + 1
        else:
            memo[i][j] = max(dp(i - 1, j), dp(i, j - 1))

    return memo[i][j]


for i in range(max(len(s), len(t))):
    if i > 0:
        for j in range(i):
            tmp = dp(min(abs(i - j), len(s)), min(abs(j - i), len(t)))


max = dp(len(s), len(t))

ans = ""

i = len(s)
j = len(t)

while i > 0 and j > 0:
    if memo[i][j] == memo[i - 1][j - 1] + 1:
        ans = s[i - 1] + ans
        i -= 1
        j -= 1
    elif memo[i][j] == memo[i - 1][j]:
        i -= 1
    else:
        j -= 1

print("{}".format(ans))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# Input#
# n = int(input())
# n, k = map(int, input().split())
# a = list(map(int, input().split()))

s = input()
t = input()

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

for i in range(len(s) + 1):
    memo[i][0] = 0

for i in range(len(t) + 1):
    memo[0][i] = 0


def dp(i, j):
    if memo[i][j] == -1:
        if s[i - 1] == t[j - 1]:
            memo[i][j] = dp(i - 1, j - 1) + 1
        else:
            memo[i][j] = max(dp(i - 1, j), dp(i, j - 1))

    return memo[i][j]


for i in range(max(len(s), len(t))):
    tmp = dp(min(i, len(s)), min(i, len(t)))


max = dp(len(s), len(t))

ans = ""

i = len(s)
j = len(t)

while i > 0 and j > 0:
    if memo[i][j] == memo[i - 1][j - 1] + 1:
        ans = s[i - 1] + ans
        i -= 1
        j -= 1
    elif memo[i][j] == memo[i - 1][j]:
        i -= 1
    else:
        j -= 1

print("{}".format(ans))