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 math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離

s = input()
t = input()
sl = len(s)
tl = len(t)

dp = [[0 for _ in range(tl+1)] for _ in range(sl+1)]

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

ans = ''
while sl > 0 and tl > 0:
    if dp[sl][tl] == dp[sl][tl-1]:
        tl -= 1
    elif dp[sl][tl] == dp[sl-1][tl]:
        sl -= 1
    else:
        ans = s[sl-1] + ans
        sl -= 1
        tl -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(s, t):
  S = len(s)
  T = len(t)

  # dp[i][j] LCS for s[:i] and t[:j]
  dp = [[0 for _ in range(T + 1)] for _ in range(T + 1)]
  dp[0][0] = 1

  for i in range(1, S + 1):
    for j in range(1, T + 1):
      if s[i - 1] == t[j - 1]:
        dp[i][j] = 1 + dp[i - 1][j - 1]
      else:
        # dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        if dp[i - 1][j] > dp[i][j - 1]:
          dp[i][j] = dp[i - 1][j]
        else:
          dp[i][j] = dp[i][j - 1]

  ans = ""
  i, j = S, T
  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(input(), input())

Submission status: Time Limit Exceeded

Solution code:
def solve(s, t):
  S = len(s)
  T = len(t)

  # dp[i][j] LCS for s[:i] and t[:j]
  dp = [[0 for _ in range(T + 1)] for _ in range(T + 1)]
  dp[0][0] = 1

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

  ans = ""
  i, j = S, T
  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(input(), input())

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
t = input()
m = len(t)

dp = [[0 for _ in range(m+1)] for _ in range(n+1)]

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

ans = ''

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

print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
t = input()
m = len(t)

dp = [['' for _ in range(m+1)] for _ in range(n+1)]

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

print(dp[n][m])

Submission status: Time Limit Exceeded

Solution code:

s = input()
t = input()

ans = [ [[0]*2 for j in range(len(t)+1)] for i in range(len(s)+1) ]
#print (ans)

for i in range(len(s)):
    i += 1

    for j in range(len(t)):
        j += 1

        #print (i,j)

        if s[i-1] == t[j-1]:
            ans[i][j][0] = ans[i-1][j-1][0] + 1
            ans[i][j][1] = 0

        else:
            if ans[i-1][j][0] > ans[i][j-1][0]:
                ans[i][j][0] = ans[i-1][j][0]
                ans[i][j][1] = 1
            else:
                ans[i][j][0] = ans[i][j-1][0]
                ans[i][j][1] = 2

ret = []

x = len(s)
y = len(t)

while x != 0 and y != 0:

    if ans[x][y][1] == 0:
        ret.append(s[x-1])
        x -= 1
        y -= 1
    elif ans[x][y][1] == 1:
        x -= 1
    else:
        y -= 1

ret.reverse()

print ("".join(ret))

Submission status: Time Limit Exceeded

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

ans = [ [""] * (len(t)+1) for i in range(len(s)+1) ]
#print (ans)

for i in range(len(s)):
    i += 1

    for j in range(len(t)):
        j += 1

        #print (i,j)

        if s[i-1] == t[j-1]:
            ans[i][j] = ans[i-1][j-1] + s[i-1]

        else:
            if len(ans[i-1][j]) > len(ans[i][j-1]):
                ans[i][j] = ans[i-1][j]
            else:
                ans[i][j] = ans[i][j-1]

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

Submission status: Time Limit Exceeded

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

li = [["" for _ in range(len(S)+1)] for _ in range(len(T)+1)]

for s in range(1,len(S)+1):
    for t in range(1,len(T)+1):
        if S[s-1] == T[t-1]:
            if len(li[t-1][s]) == max(len(li[t-1][s]), len(li[t][s-1]), len(li[t-1][s-1])+1):
                li[t][s] = li[t-1][s]
            elif len(li[t][s-1]) == max(len(li[t-1][s]), len(li[t][s-1]), len(li[t-1][s-1])+1):
                li[t][s] = li[t][s-1]
            elif len(li[t-1][s-1])+1 == max(len(li[t-1][s]), len(li[t][s-1]), len(li[t-1][s-1])+1):
                li[t][s] = li[t-1][s-1] + S[s-1]

        else:
            if len(li[t-1][s]) == max(len(li[t-1][s]), len(li[t][s-1])):
                li[t][s] = li[t-1][s]
            elif len(li[t][s-1]) == max(len(li[t-1][s]), len(li[t][s-1])):
                li[t][s] = li[t][s-1]
            
print(li[t][s])

Submission status: Time Limit Exceeded

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

dp = [['']*(len(t)+1) for _ in range(2)]
for ss in s:
    for i, tt in enumerate(t):
        a = dp[0][i+1]
        b = dp[1][i]
        if ss == tt:
            c = "".join((dp[0][i], ss))
            if len(c) > len(a):
                if len(c) > len(b):
                    r = c
                else:
                    r = b
            elif len(a) > len(b):
                r = a
            else:
                r = b
            dp[1][i+1] = r
        else:
            if len(a) > len(b):
                dp[1][i+1] = a
            else:
                dp[1][i+1] = b
    dp[0], dp[1] = dp[1], dp[0]
print(dp[0][-1])

Submission status: Time Limit Exceeded

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

import numpy as np

EDPC = "https://atcoder.jp/contests/DP/"
TDPC = "https://atcoder.jp/contests/tdpc/tasks"

############### TESTCASE ###############
test = ""
#test = \
"""
axyb
abyxb
ans axb
ans ayb
"""

"""
xayaz
aa
ans aa
"""

"""
a
z
ans 
"""

"""
abracadabra
avadakedavra
ans aaadara
"""

"""
314159265
141421356
ans 14126
ans 14125
ans 14156
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
################# MAIN ################# 

s = input2()
t = input2()
slen = len(s)
tlen = len(t)
sv = np.array(["A"] + list(s))
tv = np.array(["B"] + list(t))

dp = np.zeros((slen+1, tlen+1), dtype="int")
for i in range(slen):    
    dp[i+1] = dp[i]
    dp[i+1] += np.array(sv[i+1] == tv, dtype="int")
    for j in range(tlen):
        dp[i+1][j+1] = max(dp[i+1][j], dp[i+1][j+1])
    
#print(dp)    

ans = ""
si, ti = slen, tlen
while si:
    while dp[si][ti] == dp[si][ti-1] and ti:
        ti -= 1
        
    if dp[si][ti] > dp[si-1][ti]:
        ans += tv[ti]
        
    si -= 1

print(ans[::-1])

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

Submission status: Time Limit Exceeded

Solution code:
s,t=[input() for u in (1,1)]
l,li=[['' for i in range(len(s)+1)] for j in (1,1)]
for j in range(len(t)):
  for i in range(len(s)):
    if t[j]==s[i]:
      l[i+1]=li[i]+t[j]
    else:l[i+1]=li[i+1] if len(li[i+1])>len(l[i]) else l[i]
    li=l
print(l[-1])

Submission status: Time Limit Exceeded

Solution code:
s,t=[tuple(input()) for u in (1,1)]
l,li=[['' for i in range(len(s)+1)] for j in (1,1)]
for j in range(len(t)):
  for i in range(len(s)):
    if t[j]==s[i]:
      l[i+1]=li[i]+t[j]
    else:l[i+1]=li[i+1] if len(li[i+1])>len(l[i]) else l[i]
    li=l
print(l[-1])

Submission status: Time Limit Exceeded

Solution code:
s,t=[tuple(input()) for u in (1,1)]
l=[['' for i in range(len(s)+1)] for j in range(len(t)+1)]
for j in range(len(t)):
  for i in range(len(s)):
    if t[j]==s[i]:
      l[j+1][i+1]=l[j][i]+t[j]
    else:l[j+1][i+1]=l[j][i+1] if len(l[j][i+1])>len(l[j+1][i]) else l[j+1][i]
print(l[len(t)][len(s)])

Submission status: Time Limit Exceeded

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

dp = [[0] * (len(T)+1) for i in range(len(S)+1)]
for i, s in enumerate(S, 1):
  for j, t in enumerate(T, 1):
    if s == t:
      dp[i][j] = dp[i-1][j-1] + 1
    else:
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])

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

print(ans[::-1])

Submission status: Time Limit Exceeded

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

dp = [[[] for j in range(len(T)+1)] for i in range(len(S)+1)]
for i, s in enumerate(S):
  for j, t in enumerate(T):
    if s == t:
      dp[i+1][j+1] = dp[i][j]
      dp[i+1][j+1].append(s)
    else:
      if len(dp[i][j+1]) > len(dp[i+1][j]):
        dp[i+1][j+1] = list(''.join(dp[i][j+1]))
      else:
        dp[i+1][j+1] = list(''.join(dp[i+1][j]))

print(''.join(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, s in enumerate(S):
  for j, t in enumerate(T):
    if s == t:
      dp[i+1][j+1] = dp[i][j] + s
    else:
      a1, a2 = dp[i][j+1], dp[i+1][j]
      if len(a1) > len(a2):
        dp[i+1][j+1] = a1
      else:
        dp[i+1][j+1] = a2

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

Submission status: Time Limit Exceeded

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

def lcs(S, T):
  LS = len(S)
  LT = len(T)
 
  dps=[["" for _ in range(LT + 1)] for _j in range(LS + 1)]
  dpl=[[0 for _ in range(LT + 1)] for _j in range(LS + 1)]
  # dp[Sのi番目][Tのj番目] := それまでの最大長
 
  for i in range(LS):
    for j in range(LT):
      if S[i] == T[j]:
        dpl[i + 1][j + 1] += dpl[i][j] + 1
        dps[i + 1][j + 1] += dps[i][j] + S[i]
      else:
        if dpl[i + 1][j] >= dpl[i][j + 1]:
          dpl[i + 1][j + 1] = dpl[i + 1][j]
          dps[i + 1][j + 1] = dps[i + 1][j]
        else:
          dpl[i + 1][j + 1] = dpl[i][j + 1]
          dps[i + 1][j + 1] = dps[i][j + 1]
  return dps[-1][-1]

print(lcs(S, T))

Submission status: Time Limit Exceeded

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

def lcs(S, T):
  LS = len(S)
  LT = len(T)
 
  dp=[["" for _ in range(LT + 1)] for _j in range(LS + 1)]
  # dp[Sのi番目][Tのj番目] := それまでの最大長
 
  for i in range(LS):
    for j in range(LT):
      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]
  return dp[-1][-1]

print(lcs(S, T))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = input()
t = input()
n = len(s)
m = len(t)
dp = [['']*(m+5) for i in range(n+5)]
for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + s[i]
        else:
            dp[i+1][j+1] = dp[i][j+1] if len(dp[i][j+1]) >= len(dp[i+1][j]) else dp[i+1][j]
print(dp[n][m])

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
T = list(input())
MAX_LEN = 3007
dp = [[0] * MAX_LEN for _ in range(MAX_LEN)]

for i in range(len(S)):
    for j in range(len(T)):
        ii = i + 1
        jj = j + 1
        if S[i] == T[j]:
            dp[ii][jj] = dp[ii - 1][jj - 1] + 1
        else:

            dp[ii][jj] = max(dp[ii - 1][jj],
                             dp[ii][jj - 1]
                             )

i = len(S)
j = len(T)
from collections import deque

ans = deque(maxlen=dp[i][j])
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:
        ans.appendleft(S[i - 1])
        i -= 1
        j -= 1
print(*ans, sep='')

Submission status: Time Limit Exceeded

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

ans = ""
i = len(s)
j = len(t)
while (i > 0 and j > 0):
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input().strip()
t = input().strip()
ls = len(s)
lt = len(t)

dp = [[0]*(lt+1) for i in range(ls+1)]

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

ans = ''
i, j = ls, lt
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1]+ans
        i -= 1
        j -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)

s = input().strip()
t = input().strip()
ls = len(s)
lt = len(t)

dp = [['']*lt for i in range(ls)]


def answer(si, ti):
    if si == ls or ti == lt:
        return ''

    if dp[si][ti] != '':
        return dp[si][ti]

    if s[si] == t[ti]:
        return s[si]+answer(si+1, ti+1)

    a = answer(si+1, ti)
    b = answer(si, ti+1)
    r = a if len(a) > len(b) else b
    dp[si][ti] = r
    return dp[si][ti]


print(answer(0, 0))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(S: str, T: str):
    lenS, lenT = len(S), len(T)
    DP = [[0]*(lenT+1) for _ in range(lenS+1)]
    for i in range(lenS):
        for j in range(lenT):
            if S[i] == T[j]:
                DP[i+1][j+1] = max(DP[i][j]+1, DP[i+1][j+1])
            DP[i+1][j+1] = max(DP[i+1][j], DP[i][j+1], DP[i+1][j+1])

    ans = ""
    i, j = lenS, lenT
    while i > 0 and j > 0:
        if DP[i][j] == DP[i-1][j]:
            i -= 1
        elif DP[i][j] == DP[i][j-1]:
            j -= 1
        else:
            ans = S[i-1] + ans
            i -= 1
            j -= 1
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def LCS(S, T):
    lenS, lenT = len(S), len(T)
    DP = [[[] for __ in range(lenT+1)] for _ in range(lenS+1)]
    for i in range(lenS):
        for j in range(lenT):
            if S[i] == T[j]:
                if len(DP[i+1][j+1]) < len(DP[i][j])+1:
                    DP[i+1][j+1] = DP[i][j]+[i]
            if len(DP[i+1][j+1]) < len(DP[i+1][j]):
                DP[i+1][j+1] = DP[i+1][j]
            if len(DP[i+1][j+1]) < len(DP[i][j+1]):
                DP[i+1][j+1] = DP[i][j+1]
    return "".join(S[i] for i in DP[-1][-1])


def solve(S: str, T: str):
    print(LCS(S, T))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def LCS(S, T):
    lenS, lenT = len(S), len(T)
    DP = [[[] for __ in range(lenT+1)] for _ in range(lenS+1)]
    for i in range(lenS):
        for j in range(lenT):
            if S[i] == T[j]:
                if len(DP[i+1][j+1]) < len(DP[i][j])+1:
                    DP[i+1][j+1] = DP[i][j]+[S[i]]
            if len(DP[i+1][j+1]) < len(DP[i+1][j]):
                DP[i+1][j+1] = DP[i+1][j]
            if len(DP[i+1][j+1]) < len(DP[i][j+1]):
                DP[i+1][j+1] = DP[i][j+1]
    return "".join(DP[-1][-1])


def solve(S: str, T: str):
    print(LCS(S, T))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(S: str, T: str):
    lenS, lenT = len(S), len(T)
    DP = [[""]*(lenT+1) for _ in range(lenS+1)]
    for i in range(lenS):
        for j in range(lenT):
            if S[i] == T[j]:
                if len(DP[i+1][j+1]) < len(DP[i][j])+1:
                    DP[i+1][j+1] = DP[i][j]+S[i]
            if len(DP[i+1][j+1]) < len(DP[i+1][j]):
                DP[i+1][j+1] = DP[i+1][j]
            if len(DP[i+1][j+1]) < len(DP[i][j+1]):
                DP[i+1][j+1] = DP[i][j+1]
    print(DP[-1][-1])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)


if __name__ == '__main__':
    main()

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()
t = input()

dp = np.full(len(t) , '', dtype=object)
# dp_len = [0]* len(t)

for i in range(len(s)):
    s_temp = s[i]
    temp_max = ''
    max_len = 0
    for j in range(len(t)):
        before = dp[j]
        if(s_temp == t[j]):
            dp[j] = temp_max + s_temp
        if(max_len < len(before)):
            temp_max = before
            max_len = len(temp_max)

ans = ''
for j in range(len(t)):
    if(len(dp[j]) > len(ans)):
        ans = dp[j]

print(ans)

Submission status: Time Limit Exceeded

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

dp = ['']* len(t)
# dp_len = [0]* len(t)

for i in range(len(s)):
    s_temp = s[i]
    temp_max = ''
    max_len = 0
    for j in range(len(t)):
        before = dp[j]
        if(s_temp == t[j]):
            dp[j] = temp_max + s_temp
        if(max_len < len(before)):
            temp_max = before
            max_len = len(temp_max)

ans = ''
for j in range(len(t)):
    if(len(dp[j]) > len(ans)):
        ans = dp[j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
s=list(input())
t=list(input())
n=len(s)
m=len(t)
dp=[['' for i in range(m+1)] for j in range(n+1)]
dps=[[0 for i in range(m+1)] for j 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]+s[i]
            dps[i+1][j+1]=dps[i][j]+1
        else:
            if (dps[i+1][j])>(dps[i][j+1]):
                dp[i+1][j+1]=dp[i+1][j]
                dps[i+1][j+1]=dps[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]
                dps[i+1][j+1]=dps[i][j+1]
print(dp[n][m])

Submission status: Time Limit Exceeded

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

ss = len(s)
tt = len(t)

dp = [['' for _ in range(tt)] for __ in range(ss)]

if s[0] == t[0]:
    dp[0][0] = s[0]

for i in range(1,ss):
    if s[i] == t[0]:
        dp[i][0] = t[0]
    else:
        dp[i][0] = dp[i-1][0]

for j in range(1,tt):
    if s[0] == t[j]:
        dp[0][j] = s[0]
    else:
        dp[0][j] = dp[0][j-1]

for i in range(1, ss):
    for j in range(1, tt):
        if s[i] == t[j]:
            dp[i][j] = dp[i-1][j-1] + s[i]
            if len(dp[i][j]) < len(dp[i][j-1]):
                dp[i][j] = dp[i][j-1]
            if len(dp[i][j]) < len(dp[i-1][j]):
                dp[i][j] = dp[i-1][j]
        else:
            if len(dp[i][j-1]) < len(dp[i-1][j]):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]

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

Submission status: Time Limit Exceeded

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

ss = len(s)
tt = len(t)

dp = [[[] for _ in range(tt)] for __ in range(ss)]

if s[0] == t[0]:
    dp[0][0].append(s[0])

for i in range(1,ss):
    if s[i] == t[0]:
        dp[i][0].append(t[0])
    else:
        dp[i][0] = dp[i-1][0][:]

for j in range(1,tt):
    if s[0] == t[j]:
        dp[0][j].append(s[0])
    else:
        dp[0][j] = dp[0][j-1][:]

for i in range(1, ss):
    for j in range(1, tt):
        if s[i] == t[j]:
            dp[i][j] = dp[i-1][j-1][:]
            dp[i][j].append(s[i])
            if len(dp[i][j]) < len(dp[i][j-1]):
                dp[i][j] = dp[i][j-1][:]
            if len(dp[i][j]) < len(dp[i-1][j]):
                dp[i][j] = dp[i-1][j][:]
        else:
            if len(dp[i][j-1]) < len(dp[i-1][j]):
                dp[i][j] = dp[i-1][j][:]
            else:
                dp[i][j] = dp[i][j-1][:]

print(''.join(dp[ss-1][tt-1]))

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

Submission status: Time Limit Exceeded

Solution code:
s1=input()
s2=input()
m=len(s1)
n=len(s2)
lcs=[[(0,'') for i in range(n+1)] for j in range(m+1)]
for i in range(m):
    for j in range(n):
        if s1[i]==s2[j]:
            lcs[i+1][j+1]=(lcs[i][j][0]+1,s1[i])
        else:
            if lcs[i][j+1]>lcs[i+1][j]:
                lcs[i+1][j+1]=lcs[i][j+1]
            else:
                lcs[i+1][j+1]=lcs[i+1][j]
ans=''
i=m
j=n
while i!=0 and j!=0:
    if lcs[i-1][j]==lcs[i][j-1] and lcs[i][j-1]==lcs[i][j]:
        i-=1
        j-=1
    elif lcs[i-1][j][0]==lcs[i][j-1][0]:
        ans+=lcs[i][j][1]
        i-=1
        j-=1
    elif lcs[i][j-1][0]>lcs[i-1][j][0]:
        j-=1
    else:
        i-=1
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout 
def main():
    s1=stdin.readline()
    s2=stdin.readline()
    m=len(s1)
    n=len(s2)
    lcs=[[(0,'') for i in range(n+1)] for j in range(m+1)]
    for i in range(m):
        for j in range(n):
            if s1[i]==s2[j]:
                lcs[i+1][j+1]=(lcs[i][j][0]+1,lcs[i][j][1]+s1[i])
            else:
                if lcs[i][j+1]>lcs[i+1][j]:
                    lcs[i+1][j+1]=lcs[i][j+1]
                else:
                    lcs[i+1][j+1]=lcs[i+1][j]
    stdout.write(lcs[m][n][1])
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s1=input()
    s2=input()
    m=len(s1)
    n=len(s2)
    lcs=[[(0,'') for i in range(n+1)] for j in range(m+1)]
    for i in range(m):
        for j in range(n):
            if s1[i]==s2[j]:
                lcs[i+1][j+1]=(lcs[i][j][0]+1,lcs[i][j][1]+s1[i])
            else:
                if lcs[i][j+1]>lcs[i+1][j]:
                    lcs[i+1][j+1]=lcs[i][j+1]
                else:
                    lcs[i+1][j+1]=lcs[i+1][j]
    print(lcs[m][n][1])
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s1=input()
s2=input()
m=len(s1)
n=len(s2)
lcs=[[(0,'') for i in range(n+1)] for j in range(m+1)]
for i in range(m):
    for j in range(n):
        if s1[i]==s2[j]:
            lcs[i+1][j+1]=(lcs[i][j][0]+1,lcs[i][j][1]+s1[i])
        else:
            if lcs[i][j+1]>lcs[i+1][j]:
                lcs[i+1][j+1]=lcs[i][j+1]
            else:
                lcs[i+1][j+1]=lcs[i+1][j]
print(lcs[m][n][1])

Submission status: Time Limit Exceeded

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

s = input().split()[0]
t = input().split()[0]

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

i = len(s)
j = len(t)
ans = ''
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:
        i -= 1
        j -= 1
        ans = s[i] + ans
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
n, m = len(s), len(t)
dpString = [[""]*(m+1) for _ in range(n+1)]
dpNum = [[0]*(m+1) for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    if s[i] == t[j]:
      dpString[i+1][j+1] = dpString[i][j] + s[i]
      dpNum[i+1][j+1] = dpNum[i][j] + 1
    else:
      if dpNum[i+1][j] >= dpNum[i][j+1]:
        dpString[i+1][j+1] = dpString[i+1][j]
        dpNum[i+1][j+1] = dpNum[i+1][j]
      else:
        dpString[i+1][j+1] = dpString[i][j+1]
        dpNum[i+1][j+1] = dpNum[i][j+1]
print(dpString[n][m])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
t = list(input())
a = len(s)
b = len(t)
dp = [[""]*(b+1) for _ in range(a+1)]
#dp[i][j]はi文字目までのsとtのj文字目までの共通部分
for i in range(a):
  for j in range(b):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j]+s[i]
    else:
      dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j],key = len)
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    sl = len(s)
    t = input()
    tl = len(t)

    # dp[s][t]: value
    dp = [[(0, "") for _ in range(tl + 1)] for _ in range(sl + 1)]

    for si in range(sl):
        for ti in range(tl):
            if s[si] == t[ti]:
                dp[si + 1][ti + 1] = (dp[si][ti][0] + 1, dp[si][ti][1] + s[si])
            else:
                dp[si + 1][ti + 1] = max(dp[si + 1][ti], dp[si][ti + 1])

    # import pprint
    # print("dp={}".format(pprint.pformat(dp)))

    print(dp[sl][tl][1])


main()

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
n,m=len(s),len(t)
dp=[[0]*(m+1) for i in range(n+1)]
dp[0][0]=1

for i in range(n+1):
    for j in range(m+1):
        dp[i][j]=max(dp[i][j-1],dp[i-1][j])
        if i*j!=0 and s[i-1]==t[j-1]:
            dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j])

ans=""
i,j=n,m
while 0<i and 0<j:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans+=s[i-1]
        i-=1
        j-=1

print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
s1 = input()
s2 = input()
dp = [[0 for i in range(len(s2) + 1)] for j in range(len(s1) + 1)]
pred = [[[-1,-1, 0] for i in range(len(s2) + 1)] for j in range(len(s1) + 1)]

for i in range(len(s1) + 1):
    for j in range(len(s2) + 1):
        if i - 1 >= 0 and j - 1 >= 0 and s1[i - 1] == s2[j - 1] and dp[i - 1][j] + 1 > dp[i][j]:
            dp[i][j] = max(dp[i][j], dp[i - 1][j] + 1)
            pred[i][j] = [i-1, j, i - 1]
        elif i - 1 >= 0 and j - 1 >= 0 and dp[i - 1][j] > dp[i][j]:
            dp[i][j] = max(dp[i][j], dp[i - 1][j])
            pred[i][j] = [i-1, j, -1]

        if j - 1 >= 0 and i - 1 >= 0 and s1[i - 1] == s2[j - 1] and dp[i][j - 1] > dp[i][j]:
            dp[i][j] = max(dp[i][j], dp[i][j - 1] + 1)
            pred[i][j] = [i, j - 1, j - 1]
        elif i - 1 >= 0 and j - 1 >= 0 and dp[i][j - 1] > dp[i][j]:
            dp[i][j] = max(dp[i][j], dp[i][j - 1])
            pred[i][j] = [i, j - 1, -1]
res = ''
j = pred[len(s1)][len(s2)]
while j[0] != -1 and j[1] != -1:
    if j[2] != -1:
        res += s1[j[0]]
    j = pred[j[0]][j[1]]
print(res[::-1])