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:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    """
    N個の足場があります。足場には1,2,…,Nと番号が振られています。 
    各i (1≤i≤N) について、足場 i の高さは hi です。
    最初、足場 1 にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。
    足場 i にいるとき、足場 i+1 または i+2 へジャンプする。
    このとき、ジャンプ先の足場を j とすると、コスト |hi−hj| を支払う。
    カエルが足場 N に辿り着くまでに支払うコストの総和の最小値を求めてください。

    制約
        入力はすべて整数である。
    2≤N≤10**5
    1≤hi≤10**4
    """
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]))
    print(dp[n-1])
    return

#B
def B():
    n, K = LI()
    h = LI()
    dp = [float("INF") for i in range(n + K + 1)]
    dp[0] = 0
    for i in range(n):
        for k in range(1, K + 1):
            if i + k >= n:
                break
            dp[i + k] = min(dp[i + k], dp[i] + abs(h[i] - h[i + k]))
    print(dp[n-1])
    return

#C
def C():
    n = II()
    abc = LIR(n)
    dp = [0 for i in range(3 * n + 1)]
    dp[0] = abc[0][0]
    dp[1] = abc[0][1]
    dp[2] = abc[0][2]
    for i in range(1,n):
        dp[3 * i] = max(dp[3 * i], dp[3 * (i - 1) + 1] + abc[i][0], dp[3 * (i - 1) + 2] + abc[i][0])
        dp[3 * i + 1] = max(dp[3 * i + 1], dp[3 * (i - 1) + 2] + abc[i][1], dp[3 * (i - 1)] + abc[i][1])
        dp[3 * i + 2] = max(dp[3 * i + 2], dp[3 * (i - 1) + 1] + abc[i][2], dp[3 * (i - 1)] + abc[i][2])
    dp[3 * n] = max(dp)
    print(dp[3*n])

    return

#D
def D():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**5
    1≤wi≤W
    1≤vi≤10**9"""
    n, w = LI()
    wv = LIR(n)
    dp = [[0 for k in range(w + 1)] for i in range(n + 2)]
    for i in range(1,n + 1):
        for j in range(w + 1):
            if j < wv[i-1][0]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i - 1][0]] + wv[i - 1][1])
    print(dp[n+1][w])

    
    return

#E
def E():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**9
    1≤wi≤W
    1≤vi≤10**3"""
    n, w = LI()
    wv = LIR(n)
    dp = [[float("INF") for i in range(10 ** 5 + 1)] for k in range(n + 1)]
    dp[0][0] = 0
    for i in range(n):
        for k in range(10 ** 5 + 1):
            if k < wv[i][1]:
                dp[i + 1][k] = dp[i][k]
            else:
                dp[i + 1][k] = min(dp[i][k], dp[i][k - wv[i][1]] + wv[i][0])
    ans = 0
    for i in range(10 ** 5 + 1):
        if dp[n][i] <= w:
            ans = i
    print(ans)

    return

#F
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[i]+ans


    print(ans)
    return

#G
def G():
    n, m = LI()
    xy = LIR_(m)
    edge = [[] for i in range(n)]
    for x,y in xy:
        edge[x].append(y)
    dp = [0 for i in range(n)]
    def ans(dp, i):
        #print(dp, i)
        if dp[i] != 0:
            return dp[i]
        else:
            if len(edge[i]) == 0:
                return 0
            ansb = 0
            for k in edge[i]:
                #print(dp, k , i)
                ansb = max(ansb, ans(dp, k) + 1)
                dp[i] = max(ansb, dp[i])
                #print(dp)
            return ansb
            
    for i in range(n):
        dp[i] = ans(dp, i)
    print(max(dp))
    return

#H
def H():
    h, w = LI()
    a = SR(h)
    dp = [[0 for i in range(w)] for k in range(h)]
    for i in range(w):
        if a[0][i] == "#":
            break
        dp[0][i] = 1
    for i in range(h):
        if a[i][0] == "#":
            break
        dp[i][0] = 1
    for i in range(1,w):
        for k in range(1, h):
            #print(i,k, dp)
            if a[k - 1][i] == ".":
                if a[k][i - 1] == ".":
                    dp[k][i] = dp[k - 1][i] + dp[k][i - 1] % mod
                else:
                    dp[k][i] = dp[k - 1][i]
            else:
                if a[k][i - 1] == ".":
                    dp[k][i] = dp[k][i - 1]
    print(dp[h-1][w-1] % mod)

    return

#I
def I():
    n = II()
    p = LF()
    dp = [[0 for k in range(n+1)] for i in range(n+1)]
    dp[1][1] = p[0]
    dp[1][0] = 1-p[0]
    for i in range(2,n+1):
        for k in range(i + 1):
            if k == 0:
                
                dp[i][k] = dp[i-1][k] * (1 - p[i-1])
            else:
                dp[i][k] = dp[i - 1][k - 1] * p[i - 1] + dp[i - 1][k] * (1 - p[i - 1])
    #print(dp)
    print(sum(dp[n][n//2+1:]))
    return 
#J
def J():
    n = II()
    a = LI()


#K


#L

#M
#N
# O
# P
# Q
# R
# S
# T
# U
# V
# W
# X
# Y
# Z


#Solve
if __name__ == '__main__':
    F()

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    n = I()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n-2):
        dp[i+1] = min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
        dp[i+2] = min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
    dp[n-1] = min(dp[n-1],dp[n-2]+abs(h[n-1]-h[n-2]))
    print(dp[n-1])
#B
def B():
    n,k = LI()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,min(n-i,k+1)):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
    print(dp[n-1])

#C
def C():
    n = I()
    v = LIR(n)
    dp = [[0,0,0] for i in range(n+1)]
    for i in range(n):
        dp[i+1][0] = max(dp[i+1][0],dp[i][1]+v[i][0],dp[i][2]+v[i][0])
        dp[i+1][1] = max(dp[i+1][1],dp[i][2]+v[i][1],dp[i][0]+v[i][1])
        dp[i+1][2] = max(dp[i+1][2],dp[i][0]+v[i][2],dp[i][1]+v[i][2])
    print(max(dp[n]))

#D
def D():
    n,W = LI()
    g = LIR(n)
    dp = [[0 for i in range(W+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(W+1)[::-1]:
            w,v = g[i]
            if j >= w:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
            else:
                dp[i+1][j] = max(dp[i+1][j],dp[i][j])
    print(max(dp[n]))
#E
def E():
    n,W = LI()
    g = LIR(n)
    V = 100000
    dp = [[float("inf") for i in range(V+1)] for j in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(V+1)[::-1]:
            w,v = g[i]
            if j >= v:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
            else:
                dp[i+1][j] = min(dp[i+1][j],dp[i][j])

    for i in range(V+1)[::-1]:
        if dp[n][i] <= W:
            print(i)
            quit()

#F
def F():
    s = S()
    t = S()
    dp = [[deque() for i in range(len(t)+1)] for j in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                if len(dp[i+1][j]) < len(dp[i][j])+1:
                    if len(dp[i][j+1]) < len(dp[i][j])+1:
                        dp[i+1][j+1] = dp[i][j].copy()
                        dp[i+1][j+1].append(s[i])
                    else:
                        dp[i+1][j+1] = dp[i][j+1]
                else:
                    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]
            else:
                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]
    for i in dp[len(s)][len(t)]:
        print(i,end ="")
    print()
#G
def G():
    n,m = LI()
    e = LIR(m)
    dp = [[0 for i in range(n+1)] for j in range(m+1)]
    for i in range(m):
        x,y = e[i]
        dp[i+1][y] = max(dp[i][y],dp[i][x]+1)
    ans = 0
    for i in range(m+1):
        ans = max(dp[i])
    print(ans)
#H
def H():
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Runtime Error

Solution code:
s = [ord(c)-97 for c in input()]
t = [ord(c)-97 for c in input()]

sl = len(s)
tl = len(t)
rr = [[0]*tl for _ in range(sl)]
t0 = t[0]
for i in range(tl):
  if s[i] == t0:
    for k in range(i, sl):
      rr[k][0] = 1
    break
    
rr0 = rr[0]
s0 = s[0]
for j in range(tl):
  if s0 == t[j]:
    for k in range(j, tl):
      rr0[k] = 1
    break

ttl = [(i, t[i]) for i in range(1,tl)]
for i in range(1, sl):
  rri = rr[i]
  rrij = rr[i-1]
  si = s[i]
  for j, tj in ttl:
    if si == tj:
      rri[j] = rrij[j-1]+1
    else:
      rri[j] = rrij[j]
      if rri[j] < rri[j-1]:
        rri[j] = rri[j-1]
i = sl-1
j = tl-1
r = []
while i >= 0 and j >= 0:
  if s[i] == t[j]:
    r.append(s[i]+97)
    i -= 1
    j -= 1
    continue
  if rr[i][j] == 0:
    break
  if i > 0 and rr[i-1][j] == rr[i][j]:
    i -= 1
  else:
    j -= 1
print(''.join(map(chr,r[::-1])))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(sys.getrecursionlimit())
def trace(i,j):
    global ans
    if i == 0 or j == 0:
        return
    if dp[i][j][1] == 0:
        trace(i,j-1)
    elif dp[i][j][1] == 1:
        ans += s[i-1]
        trace(i-1,j-1)
    elif dp[i][j][1] == 2:
        trace(i-1,j)
    else:
        return

s = input()
t = input()
# dp[i][j] = LCS(s[:i+1],t[:j+1])
dp = [ [( 0 , -1 )]*(len(t)+1)  for _ in range(len(s)+1) ]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        comp = [ dp[i][j-1][0],dp[i-1][j-1][0]+int(s[i-1]==t[j-1]),dp[i-1][j][0]]
        argmax = comp.index(max(comp))
        dp[i][j] = ( comp[argmax] , argmax )

ans = ""
trace(len(s),len(t))
print(ans[::-1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(sys.getrecursionlimit())
def trace(i,j):
    global ans
    if dp[i][j][1] == 0:
        trace(i,j-1)
    elif dp[i][j][1] == 1:
        ans += s[i-1]
        trace(i-1,j-1)
    elif dp[i][j][1] == 2:
        trace(i-1,j)
    else:
        return

s = input()
t = input()
# dp[i][j] = LCS(s[:i+1],t[:j+1])
dp = [ [( 0 , -1 )]*(len(t)+1)  for _ in range(len(s)+1) ]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        comp = [ dp[i][j-1][0],dp[i-1][j-1][0]+int(s[i-1]==t[j-1]),dp[i-1][j][0]]
        argmax = comp.index(max(comp))
        dp[i][j] = ( comp[argmax] , argmax )

ans = ""
trace(len(s),len(t))
print(ans[::-1])

Submission status: Runtime Error

Solution code:
def trace(i,j):
    global ans
    if dp[i][j][1] == 0:
        trace(i,j-1)
    elif dp[i][j][1] == 1:
        ans += s[i-1]
        trace(i-1,j-1)
    elif dp[i][j][1] == 2:
        trace(i-1,j)
    else:
        return

s = input()
t = input()
# dp[i][j] = LCS(s[:i+1],t[:j+1])
dp = [ [( 0 , -1 )]*(len(t)+1)  for _ in range(len(s)+1) ]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        comp = [ dp[i][j-1][0],dp[i-1][j-1][0]+int(s[i-1]==t[j-1]),dp[i-1][j][0]]
        argmax = comp.index(max(comp))
        dp[i][j] = ( comp[argmax] , argmax )

ans = ""
trace(len(s),len(t))
print(ans[::-1])

Submission status: Runtime Error

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

len_s = len(s)
len_t = len(t)
INF = float('inf')

dp = [[-INF] * (len_t+1) for _ in range(len_s+1)]

dp[0][0] = 0

memo = [[] * (len_t+1) for _ in range(len_s+1)]

for i in range(len_s+1):
    for j in range(len_t+1):
        if i+1 <= len_s and j <= len_t and dp[i+1][j] <= dp[i][j]:
            dp[i+1][j] = dp[i][j]
            memo[i+1][j] = [i, j]
        if i <= len_s and j+1 <= len_t and dp[i][j+1] <= dp[i][j]:
            dp[i][j+1] = dp[i][j]
            memo[i][j+1] = [i, j]
        if i+1 <= len_s and j+1 <= len_t and s[i] == t[j] and dp[i+1][j+1] <= dp[i][j]+1:
            dp[i+1][j+1] = dp[i][j] + 1
            memo[i+1][j+1] = [i, j]

i = len_s
j = len_t
ans = ""
while i > 0 and j > 0:
    pre_i, pre_j = memo[i][j][0], memo[i][j][1]
    if i == pre_i + 1 and j == pre_j + 1:
        ans += s[i-1]
    i = pre_i
    j = pre_j

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 for _ in range(len_s)]

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

i = len_s
j = len_t
res = ""
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        res += s[i-1]
        i -= 1
        j -= 1

print(res[::-1])

Submission status: Runtime Error

Solution code:
def lcs(s1, s2):
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if not chr_idx:
                break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if chr_idx:
                dp.append(chr_idx)
    return len(dp)

def solve():
    N = int(input())
    for _ in range(N):
        x = input()
        y = input()
        print(lcs(x, y))

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
S=input()
T=input()
s=len(S)
t=len(T)
dp=[['' for i in range(s+1)] for j in range(t+1)]
for i in range(s):
    for j in range(t):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+S[i]
        else:
            dp[i+1][j+1]=dp[i+1][j]
            if len(dp[i][j+1])>len(dp[i+1][j]):
                dp[i+1][j+1]=dp[i][j+1]
print(dp[s][t])

Submission status: Runtime Error

Solution code:
S=input()
T=input()
s=len(S)
t=len(T))
dp=[['' for i in range(T+1)] for j in range(T+1)]
for i in range(S):
    for j in range(T):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+s[i]
        else:
            dp[i+1][j+1]=dp[i+1][j]
            if len(dp[i][j+1])>len(dp[i+1][j]):
                dp[i+1][j+1]=dp[i][j+1]
print(dp[S][T])

Submission status: Runtime Error

Solution code:
a = list(input())

b = list(input())

aa = len(a)

bb = len(b)

dp = [[]*(m+1) for i in range(n+1)]

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

ans = ""

while aa > 0 and bb > 0:
	if a[n-1] == b[m-1]:
		aa -= 1
		bb -= 1
		ans += a[aa]
	elif dp[aa][bb-1] > dp[a-1][b]:
		aa -= 1
	else:
		bb -= 1
print(ans[::-1])

Submission status: Runtime Error

Solution code:
s1 = raw_input()
n = len(s1)
s2 = raw_input()
m = len(s2)
 
memo = {}
sol = {}
 
def lcs(n, m): ##1 index
    state = (n, m)
 
    if state not in memo:
        if n <= 0 or m <= 0:
            memo[state] = 0
            sol[state] = list()
            return 0
            
        if s1[n-1] == s2[m-1]:
            memo[state] = 1+lcs(n-1, m-1)
            sol[state] = [s1[n-1]]+sol[(n-1, m-1)]
                                          
        else:
            memo[state] = max(lcs(n-1, m), lcs(n, m-1))
            if memo[state] == memo[(n-1, m)]:
                sol[state] = list(sol[(n-1, m)])
            else:
                sol[state] = list(sol[(n, m-1)])
 
    return memo[state]
  
k = lcs(n, m)
  
print ''.join(sol[(n, m)])

Submission status: Runtime Error

Solution code:
s1 = raw_input()
n = len(s1)
s2 = raw_input()
m = len(s2)

memo = {}
sol = {}

def lcs(n, m): ##1 index
    state = (n, m)

    if state not in memo:
        if n <= 0 or m <= 0:
            memo[state] = 0
            sol[state] = list()
            return 0
            
        if s1[n-1] == s2[m-1]:
            memo[state] = 1+lcs(n-1, m-1)
            sol[state] = [s1[n-1]]+sol[(n-1, m-1)]
                                          
        else:
            memo[state] = max(lcs(n-1, m), lcs(n, m-1))
            if memo[state] == memo[(n-1, m)]:
                sol[state] = list(sol[(n-1, m)])
            else:
                sol[state] = list(sol[(n, m-1)])

    return memo[state]
  
  k = lcs(n, m)
  
  print sol([n, m])

Submission status: Runtime Error

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
sys.setrecursionlimit(4000)


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


s = ''
dp = []
def main():
    global s
    global dp
    s = input()
    t = input()

    n = len(s)
    m = len(t)

    dp = [[0 for j in range(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+1][j], dp[i][j+1])

    #  print(t)
    #  v = 0
    #  result = ''
    #  print('dp[-1]', dp[-1])
    #  for idx, i in enumerate(dp[-1]):
    #      print(idx, i)
    #      if i == v + 1:
    #          result += t[idx-1]
    #          v += 1

    #  print(result)

    #  lcs_str = ''
    #  i, j = n - 1, m - 1
    #  while i >= 0 and j >= 0:
    #      if s[i] == t[j]:
    #          lcs_str += s[i]
    #          i -= 1
    #          j -= 1
    #      elif dp[i+1][j+1] == 0:
    #          break
    #      else:
    #          if dp[i][j+1] > dp[i+1][j]:
    #              i -= 1
    #          else:
    #              j -= 1

    #  print(lcs_str[::-1])
    print_lcs(n, m)


def print_lcs(i, j):
    global s, dp
    if not i or not j:
        return ''

    ret = dp[i][j]
    if ret == dp[i-1][j]:
        print_lcs(i - 1, j)
    elif ret == dp[i][j-1]:
        print_lcs(i, j-1)
    else:
        print_lcs(i - 1, j - 1)
        print(s[i-1], end='', flush=True)


main()

Submission status: Runtime Error

Solution code:
s=[ord(ch) for ch in input()]
t=[ord(ch) for ch in input()]
# 
#print("#")
 
# minimize
mnmz={i for i in s} & {j for j in t}
if len(mnmz)==0:
    print("")
    exit()
s=[ z for z in s if z in mnmz]
t=[ z for z in t if z in mnmz]
if len(s)>len(t): s, t = t, s
#print(s)
#print(t)
# init
dp=[0]*len(s)
res={}
#dp
for i in range(len(t)):
    #print(dp)
    prev=dp[0]
    if dp[0]==0 and t[i]==s[0]:
        dp[0]=1
        res[1]=[s[0]]
    acc={}
    for j in range(1, len(s)):
        temp = max(dp[j-1], dp[j])
        if s[j]==t[i]:
            if temp<prev+1:
                temp=prev+1
                acc[temp]=res[prev].copy()+[s[j]]
        prev, dp[j] = dp[j], temp
    res.update(acc)
    if dp[-1]==len(s): break
 
#print(dp)
 
print("".join([ chr(i) for i in res[dp[-1]]]))

Submission status: Runtime Error

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

# minimize
mnmz={ch for ch in s} & {ch for ch in t}
if len(mnmz)==0:
    print("")
    exit()
s="".join([ z for z in s if z in mnmz])
t="".join([ z for z in t if z in mnmz])
if len(s)>len(t): s, t = t, s

# init
dp=[0]*len(s)
res={}
#dp
for i in range(len(t)):
    #print(dp)
    prev=dp[0]
    if dp[0]==0 and t[i]==s[0]:
        dp[0]=1
        res[1]=[s[0]]
        collector={}
    for j in range(1, len(s)):
        temp = max(dp[j-1], dp[j])
        if s[j]==t[i]:
            if temp<prev+1:
                temp=prev+1
                if temp not in res: res[temp]=[]
                collector[temp]=res[prev]+[s[j]]
        prev, dp[j] = dp[j], temp
    res.update(collector)
    if dp[-1]==len(s): break

#print(dp)

print("".join(res[dp[-1]]))

Submission status: Runtime Error

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

# minimize
mnmz={ch for ch in s} & {ch for ch in t}
if len(mnmz)==0:
    print("")
    exit()
s="".join([ z for z in s if z in mnmz])
t="".join([ z for z in t if z in mnmz])
if len(s)>len(t): s, t = t, s
#print(s)
#print(t)
# init
dp=[0]*len(s)
res={}
#dp
for i in range(len(t)):
    #print(dp)
    prev=dp[0]
    if dp[0]==0 and t[i]==s[0]:
        dp[0]=1
        res[1]=[s[0]]
    for j in range(1, len(s)):
        temp = max(dp[j-1], dp[j])
        if s[j]==t[i]:
            if temp<prev+1:
                temp=prev+1
                res[temp]=res[prev]+[s[j]]
        prev, dp[j] = dp[j], temp
    if dp[len(s)-1]==len(s): break

#print(dp)

print("".join(res[dp[len(s)-1]]))

Submission status: Runtime Error

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

# minimize
mnmz={ch for ch in s} & {ch for ch in t}
if len(mnmz)==0:
    print("")
    exit()
s="".join([ z for z in s if z in mnmz])
t="".join([ z for z in t if z in mnmz])
if len(s)>len(t): s, t = t, s
#print(s)
#print(t)
# init
dp=[0]*len(s)
res={}
#dp
for i in range(len(t)):
    #print(dp)
    prev=dp[0]
    if dp[0]==0 and t[i]==s[0]:
        dp[0]=1
        res[1]=[s[0]]
    for j in range(1, len(s)):
        temp = max(dp[j-1], dp[j])
        if s[j]==t[i]:
            if temp<prev+1:
                temp=prev+1
                res[temp]=res[prev]+[s[j]]
        prev, dp[j] = dp[j], temp
    if dp[len(s)]==len(s): break

#print(dp)

print("".join(res[dp[len(s)-1]]))

Submission status: Runtime Error

Solution code:
s=input()
t=input()
# minimize
mnmz={ch for ch in s} & {ch for ch in t}
if len(mnmz)==0:
    print("")
    exit()
s="".join([ z for z in s if z in mnmz])
t="".join([ z for z in t if z in mnmz])
# init
dp=[0]*len(s)
res={}
#dp
for i in range(len(t)):
    prev=dp[0]
    if dp[0]==0 and t[i]==s[0]:
        dp[0]=1
        res[1]=[s[0]]
    for j in range(1, len(s)):
        temp = max(dp[j-1], dp[j])
        if s[j]==t[i]:
            if temp<prev+1:
                temp=prev+1
                res[temp]=res[prev]+[s[j]]
        prev, dp[j] = dp[j], temp

print("".join(res[dp[len(s)-1]]))

Submission status: Runtime Error

Solution code:
lenmax = lambda x, y: x if len(x) > len(y) else y
dp = {("","") : ""}

def lcs(x,y):
    if (x,y) in dp:
        return dp[(x,y)]

    if x == "" or y == "":
        a = ""
    elif x[-1] == y[-1]:
        a = lcs(x[:-1],y[:-1]) + x[-1]
    else:
        a = lenmax(lcs(x[:-1],y), lcs(x,y[:-1]))
    dp[(x,y)] = a
    return a

print(lcs(input(),input()))

Submission status: Runtime Error

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

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

s="@"+s
t="_"+t


dp=[ [ 0 for j in range(len_t+1) ] for i in range(len_s+1)   ]
S=""
l=0

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


ans=""
def lcs(i,j):
	global ans
	if dp[i][j]==0:
		return
	else:
		if s[i]==t[j]:
			lcs(i-1,j-1)
			ans+=s[i]
		else:
			if dp[i-1][j]>=dp[i][j-1]:
				lcs( i-1, j )
			else:
				lcs( i, j-1)

lcs(len_s, len_t)
print ans

Submission status: Runtime Error

Solution code:
len_s=len(s)
len_t=len(t)

s="@"+s
t="_"+t


dp=[ [ 0 for j in range(len_t+1) ] for i in range(len_s+1)   ]
S=[ [ "" for j in range(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]==t[j]:
			dp[i][j]=dp[i-1][j-1]+1
			S[i][j]=S[i-1][j-1]+s[i]
		else:			
			dp[i][j]=max( dp[i-1][j] , dp[i][j-1] )
			if dp[i-1][j]>=dp[i][j-1]:
				S[i][j]=S[i-1][j]
			else:
				S[i][j]=S[i][j-1]


print S[-1][-1]

Submission status: Runtime Error

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

  LS = len(s)
  LT = len(t)
      
  DP = [[0 for i in range(LT + 1)] for j in range(LS + 1)]
  L = [[0 for i in range(LT)] for j in range(LS)]
  for i in range(LS):
    for j in range(LT):
      a = DP[i+1][j]
      b = DP[i][j+1]
      c = DP[i][j] + 1
      if max(a, b) == a:
        DP[i+1][j+1] = a
        L[i][j] = 1
      else:
        DP[i+1][j+1] = b
        L[i][j] = 2
        a = b
      if s[i] == t[j]:
        if max(a, c) == c:
          DP[i+1][j+1] = c
          L[i][j] = 3       
        
  Ans = ""
  j = LS - 1
  k = LT - 1
  x = DP[j][k]
  for i in range(x, -1, -1):
    while True:
      if L[j][k] == 3:
        Ans += t[k]
        j -= 1
        k -= 1
        break
      elif L[j][k] == 2:
        j -= 1
      else:
        k -= 1
  print(Ans[::-1])
main()

Submission status: Runtime Error

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

LS = len(s)
LT = len(t)

num = LT
for i in range(LT):
  if s[0] == t[i]:
    num = i
    break

if LS == 1:
  if num == LT:
    print("")
  else:
    print (s)
  exit()
    
DP = [[0 if i < num or j != 0 else 1 for i in range(LT)] for j in range(LS)]
T = [1 if i == num else 0 for i in range(LT)]
if num != LT:
  L = [s[0]]
else:
  L = [[""]]
for i in range(1, LS):
  ma = DP[i-1][0]
  flag = 0
  for j in range(LT):
    if flag == 1:
      T[j] = 0
    if s[i] == t[j] and T[j] == 0:
      if flag == 0:
        T[j] = 1
        flag = 1
      Lt = DP[i-1][j]
      if len(L[ma-1]) <= len(L[Lt-1]):
        L.append(L[Lt-1] + s[i])
        ma = len(L)
    elif ma < DP[i-1][j]:
      ma = DP[i-1][j]
    DP[i][j] = ma

print(L[ma-1])

Submission status: Runtime Error

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

LS = len(s)
LT = len(t)

num = LT
for i in range(LT):
  if s[0] == t[i]:
    num = i
    break

if LS == 1:
  if num == LT:
    print("")
  else:
    print (s)
  exit()
    
DP = [0 if i < num else s[0] for i in range(LT)]
T = [1 if i == num else 0 for i in range(LT)]
for i in range(1, LS):
  ma = DP[0]
  flag = 0
  for j in range(LT):    
    if flag == 1:
      T[j] = 0
    if s[i] == t[j] and T[j] == 0:
      if flag == 0:
        T[j] = 1
        flag = 1
      ma = DP[j] + s[i]
    elif len(ma) < len(DP[j]):
      ma = DP[j]
    DP[j] = ma
print(DP[-1])

Submission status: Runtime Error

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

LS = len(s)
LT = len(t)

num = LT
for i in range(LT):
  if s[0] == t[i]:
    num = i
    break

if LS == 1:
  if num == LT:
    print("")
  else:
    print (s)
  exit()
    
DP = [[0 if i < num or j != 0 else s[0] for i in range(LT)] for j in range(LS)]
T = [1 if i == num else 0 for i in range(LT)]
for i in range(1, LS):
  ma = DP[i-1][0]
  flag = 0
  for j in range(LT):
    if flag == 1:
      T[j] = 0
    if s[i] == t[j] and T[j] == 0:
      if flag == 0:
        T[j] = 1
        flag = 1   
      ma = DP[i-1][j] + s[i]
    elif len(ma) < len(DP[i-1][j]):
      ma = DP[i-1][j]
    DP[i][j] = ma
print(DP[-1][-1])

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout

INF = float('inf')
s = stdin.readline().strip()
f = stdin.readline().strip()

n, m = len(s), len(f)
dp = [[0 for i in range(n + 5)] for j in range(m + 5)]

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

n -= 1
m -= 1
ans = ''

while n >= 0 and m >= 0:
    if s[n] == f[m]:
        ans += s[n]
        n -= 1
        m -= 1
    elif dp[n - 1][m] > dp[n][m - 1]:
        n -= 1
    else:
        m -= 1
        
stdout.write(ans[::-1])

Submission status: Runtime Error

Solution code:
import itertools as itr

s = input()
t = input()

ls = len(s)
lt = len(t)

dp = [['']*(lt+1) for _ in range(ls+1)]

for i, j in itr.product(range(1, ls+1), range(1, lt+1)):
    if s[i-1] == t[j-1]:
        if len(dp[i][j-1]) > len(dp[i-1][j]):
            dp[i][j] = dp[i][j-1]+s[i-1]
        else:
            dp[i][j] = dp[i-1][j]+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]
    print((i,j), dp[i][j])

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