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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

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: Time Limit Exceeded

Solution code:
# dpF - LCS
def main():
    S, T = tuple(input().rstrip() for _ in range(2))
    n, m = len(S), len(T)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 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])
    ans = []
    while n > 0 and m > 0:
        if dp[n][m] == dp[n - 1][m]:
            n -= 1
        elif dp[n][m] == dp[n][m - 1]:
            m -= 1
        else:
            n -= 1
            m -= 1
            ans += [S[n]]
    print(*ans[::-1], sep="")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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('')
    sys.exit(0)
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: Time Limit Exceeded

Solution code:
import sys

s = input()
t = input()

cross = []
mti = -1
for si in range(len(s)):
    for ti in range(len(t)):
        if s[si] == t[ti]:
            cross.append(((si, ti), s[si]))
            if ti > mti:
                mti = ti
                break

if len(cross) == 0:
    print('')
    sys.exit(0)
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: Time Limit Exceeded

Solution code:
import sys

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('')
    sys.exit(0)
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: Time Limit Exceeded

Solution code:

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

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

def lenmax(*args):
    args_list = list(args)
    length_list = list(map(len, args_list))
    longest_length = max(length_list)
    longest_index = length_list.index(longest_length)
    return args_list[longest_index]
    

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

print("".join(cls_list[-1][-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
s=' '+input().rstrip()
t=' '+input().rstrip()
m=len(s)-1
n=len(t)-1
dp=[[0]*(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]==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=''
while m>0 and n>0:
    if dp[m][n]==dp[m][n-1]:
        n-=1
    elif dp[m][n]==dp[m-1][n]:
        m-=1
    elif dp[m][n]==dp[m-1][n-1]+1:
        ans=s[m]+ans
        m-=1
        n-=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline

S = input()
T = input()
DP = [[""]*(len(T)+1) for i 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] + S[i]
        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]
print(DP[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
DP = [[""]*(len(T)+1) for i 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] + S[i]
        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]
print(DP[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
s=' '+input().rstrip()
t=' '+input().rstrip()
dp=[['']*len(t) for i in range(len(s))]
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]+s[i]
        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(dp[len(s)-1][len(t)-1])

Submission status: Time Limit Exceeded

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

dp = [[[] for _ in range(len(t))] for _ in range(2)]

import copy

for i in range(1, len(s)):
    i0 = i % 2
    i1 = (i - 1) % 2
    for j in range(1, len(t)):
        if len(dp[i1][j]) > len(dp[i0][j - 1]):
            dp[i0][j] = dp[i1][j]
        else:
            dp[i0][j] = copy.copy(dp[i0][j - 1])
        if s[i] == t[j]:
            if len(dp[i1][j - 1]) + 1 > len(dp[i0][j]):
                dp[i1][j - 1].append(s[i])
                dp[i0][j] = dp[i1][j - 1]
print("".join(dp[(len(s) - 1) % 2][len(t) - 1]))

Submission status: Time Limit Exceeded

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

dp = [[[] for _ in range(len(t))] for _ in range(2)]

import copy

for i in range(1, len(s)):
    i0 = i % 2
    i1 = (i - 1) % 2
    for j in range(1, len(t)):
        if len(dp[i1][j]) > len(dp[i0][j - 1]):
            dp[i0][j] = copy.copy(dp[i1][j])
        else:
            dp[i0][j] = copy.copy(dp[i0][j - 1])
        if s[i] == t[j]:
            if len(dp[i1][j - 1]) + 1 > len(dp[i0][j]):
                dp[i1][j - 1].append(s[i])
                dp[i0][j] = dp[i1][j - 1]
print("".join(dp[(len(s) - 1) % 2][len(t) - 1]))

Submission status: Time Limit Exceeded

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

dp = [[[] for _ in range(len(t))] for _ in range(len(s))]

import copy
for i in range(1, len(s)):
    for j in range(1, len(t)):
        if len(dp[i-1][j]) > len(dp[i][j-1]):
            dp[i][j] = copy.copy(dp[i-1][j])
        else:
            dp[i][j] = copy.copy(dp[i][j-1])
        if s[i] == t[j]:
            tp = dp[i - 1][j - 1]
            tp.append(s[i])
            if len(tp) > len(dp[i][j]):
                dp[i][j] = tp
print("".join(dp[len(s) - 1][len(t) - 1]))

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
t = str(input())
s_length = len(s) 
t_length = len(t)

if s_length < t_length:
    s, t = t, s
    s_length, t_length = t_length, s_length

dp = [[0 for j in range(s_length + 1)] for i in range(t_length + 1)]

for i in range(0, t_length):
    for j in range(0, s_length):
        if s[j] == t[i]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

lcs = ""
i = t_length
j = s_length

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:
        lcs += s[j-1]
        i -= 1
        j -= 1

print(lcs[::-1])

Submission status: Time Limit Exceeded

Solution code:

s = raw_input()
t = raw_input()

dp = [[""]*len(list(t)) for _ in xrange(len(list(s)))]

for i, es in enumerate(list(s)):
    for j, et in enumerate(list(t)):
        if es == et:
            if i>0 and j>0:
                dp[i][j] = dp[i-1][j-1] + es
            else:
                dp[i][j] = es

        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 dp[-1][-1]

Submission status: Time Limit Exceeded

Solution code:
def solve():
  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 and 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)

solve()

Submission status: Time Limit Exceeded

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 and 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: Time Limit Exceeded

Solution code:
from bisect import bisect_right
s = input().rstrip()
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: Time Limit Exceeded

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

N = len(s)
M = len(t)

dp = [[0 for i in range(3010)] for j in range(3010)]

for i in range(N):
    for j in range(M):
        if s[i] == t[j]:
            if dp[i+1][j+1] < dp[i][j]+1:
                dp[i+1][j+1] = dp[i][j]+1
        if dp[i+1][j+1] < dp[i+1][j]:
            dp[i+1][j+1] = dp[i+1][j]
        if dp[i+1][j+1] < dp[i][j+1]:
            dp[i+1][j+1] = dp[i][j+1]

ans = []
while N > 0 and M > 0:
    if dp[N][M] == dp[N-1][M]:
        N -= 1
    elif dp[N][M] == dp[N][M-1]:
        M -= 1
    else:
        N -= 1
        M -= 1
        ans.append(s[N])

ans.reverse()
ans = "".join(ans)
print(ans)

Submission status: Time Limit Exceeded

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

res = ""
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:
        res = S[i-1] + res
        i -= 1
        j -= 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()

lens = len(S)
lent = len(T)

dp = [['']*(lent+1) for _ in range(lens+1)]
for s in range(lens):
    for t in range(lent):
        if S[s] == T[t]:
            dp[s+1][t+1] = max(dp[s+1][t],dp[s][t+1],dp[s][t]+S[s],key = len)
        else:
            dp[s+1][t+1] = max(dp[s+1][t],dp[s][t+1],key = len)
print(dp[lens][lent])

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = input()
  t = input()
  n = len(s)
  m = len(t)
  dp = [[0]*(m+1) for _ 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])
  i,j = n,m
  ans = ""
  while i and j:
    if dp[i][j] == dp[i-1][j]:
      i -= 1
    elif dp[i][j] == dp[i][j-1]:
      j -= 1
    else:
      i -= 1
      j -= 1
      ans += s[i]
  print(ans[::-1])

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0]*(m+1) for _ 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])
i,j = n,m
ans = ""
while i and j:
  if dp[i][j] == dp[i-1][j]:
    i -= 1
  elif dp[i][j] == dp[i][j-1]:
    j -= 1
  else:
    i -= 1
    j -= 1
    ans += s[i]
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
a=[[""]*(len(t)+1)for i in range(len(s)+1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            a[i+1][j+1]=a[i][j]+s[i]
        else:
            a[i+1][j+1]=(a[i][j+1] if len(a[i][j+1])>len(a[i+1][j]) else a[i+1][j])
print(a[-1][-1])

Submission status: Time Limit Exceeded

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()
    s = [ord(c) - 97 for c in s]
    t = S()
    t = [ord(c) - 97 for c in t]
    ss = len(s)
    tt = len(t)
    dp = [[0] * (tt + 1) for _ in range(ss + 1)]
    dpi1 = dp[0]
    for i, si in enumerate(s):
        dpi = dpi1
        dpi1 = dp[i + 1]
        for j, tj in enumerate(t):
            dpij = dpi[j]
            dpi1j = dpi1[j]
            if si == tj:dpi1[j + 1] = dpij + 1
            else:
                if dpi[j + 1] < dpi1j:
                    dpi1[j + 1] = dpi1j
                else:
                    dpi1[j + 1] = dpi[j + 1]
    ans = []
    si = ss
    ti = tt
    dps = dp[si]
    dps1 = dp[si - 1]
    while si > 0 and ti > 0:
        if dps[ti] == dps1[ti]:
            si -= 1
            dps = dp[si]
            dps1 = dp[si - 1]
        elif dps[ti] == dps[ti - 1]:
            ti -= 1
        else:
            si -= 1
            ti -= 1
            dps = dp[si]
            dps1 = dp[si - 1]
            ans.append(s[si] + 97)
    print("".join(map(chr,ans[::-1])))
    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
def K():
    n, k = LI()
    an = LI()
    dp = [0 for i in range(k + 1)]
    dp[0] = 0
    ans = ["First","Second"]
    for i in range(k + 1):
        if i in an:
            dp[i] = 0
        else:
            for num, a in enumerate(an):
                if a < i:
                    if dp[i - a] == 1:
                        dp[i] = 0
                        break
            else:
                dp[i] = 1
        #print(dp,i)

    print(ans[dp[k]])

#L
def L():
    N, K = LI()
    an = LI()
    dp = [[1 for k in range(K + 2)] for n in range(N)]
    an.sort()
    for a in range(K + 2):
        if a == 0:
            continue
        elif a <= an[0]:
            dp[0][a] = (dp[0][a - 1] + 1) % mod
    for n in range(1,N):
        for k in range(1,K + 2):
            if k - an[n] <= 0:
                dp[n][k] = (dp[n - 1][k] + dp[n][k - 1]) % mod
            else:
                dp[n][k] =  dp[n][k-1] + (dp[n - 1][k] - dp[n - 1][k - an[n]]) % mod
    print(dp)

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


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

Submission status: Time Limit Exceeded

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()
    ss = len(s)
    tt = len(t)
    dp = [[0] * (tt + 1) for _ in range(ss + 1)]
    dpi1 = dp[0]
    for i, si in enumerate(s):
        dpi = dpi1
        dpi1 = dp[i + 1]
        for j, tj in enumerate(t):
            dpij = dpi[j]
            dpi1j = dpi1[j]
            if si == tj:dpi1[j + 1] = dpij + 1
            else:
                if dpi[j + 1] < dpi1j:
                    dpi1[j + 1] = dpi1j
                else:
                    dpi1[j + 1] = dpi[j + 1]
    ans = []
    si = ss
    ti = tt
    dps = dp[si]
    dps1 = dp[si - 1]
    while si > 0 and ti > 0:
        if dps[ti] == dps1[ti]:
            si -= 1
            dps = dp[si]
            dps1 = dp[si - 1]
        elif dps[ti] == dps[ti - 1]:
            ti -= 1
        else:
            si -= 1
            ti -= 1
            dps = dp[si]
            dps1 = dp[si - 1]
            ans.append(s[si])
    print("".join(ans[::-1]))
    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
def K():
    n, k = LI()
    an = LI()
    dp = [0 for i in range(k + 1)]
    dp[0] = 0
    ans = ["First","Second"]
    for i in range(k + 1):
        if i in an:
            dp[i] = 0
        else:
            for num, a in enumerate(an):
                if a < i:
                    if dp[i - a] == 1:
                        dp[i] = 0
                        break
            else:
                dp[i] = 1
        #print(dp,i)

    print(ans[dp[k]])

#L
def L():
    N, K = LI()
    an = LI()
    dp = [[1 for k in range(K + 2)] for n in range(N)]
    an.sort()
    for a in range(K + 2):
        if a == 0:
            continue
        elif a <= an[0]:
            dp[0][a] = (dp[0][a - 1] + 1) % mod
    for n in range(1,N):
        for k in range(1,K + 2):
            if k - an[n] <= 0:
                dp[n][k] = (dp[n - 1][k] + dp[n][k - 1]) % mod
            else:
                dp[n][k] =  dp[n][k-1] + (dp[n - 1][k] - dp[n - 1][k - an[n]]) % mod
    print(dp)

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


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