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:
s = "#" + input()
t = "$" + input()

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

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

Submission status: Time Limit Exceeded

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

#sの文字数行*tの文字数列のDP
import numpy as np
dp=[[0]*(lt+1) for _ in range(ls+1)]
dp=np.array(dp)

for i in range(1,ls+1):
    for j in range(1,lt+1):
        if s[i-1]==t[j-1]:
        # sとtの見た文字が一致
        # →sとtの双方の1個前までの共通最大連続数に+1追加
            dp[i][j]=dp[i-1][j-1]+1
        else:
        # 一致しないとき
        # sの1個前までか、tの1個前の共通最大連続数の
        # 大きいほうを採用
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])

# 復元はs,tとも後ろから見ていく
ans = ''
i=ls
j=lt
while i != 0 and j != 0:
    if dp[i][j] == dp[i-1][j]:
        # DP上でsの一個前から更新されてない
        # 即ちs[i-1]は共通列に入ってない
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        # 上と同じ論法でtの場合
        j -= 1
    else:
        # 今見ているs[i-1]とt[j-1]が共通になっているとき
        # 答えに採用（s[i-1]は頭につける）
        ans = s[i-1] + ans 
        i -= 1
        j -= 1
        
print(ans)

Submission status: Time Limit Exceeded

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

#sの文字数行*tの文字数列のDP
dp=[[0]*(lt+1) for _ in range(ls+1)]


for i in range(1,ls+1):
    for j in range(1,lt+1):
        if s[i-1]==t[j-1]:
        # sとtの見た文字が一致
        # →sとtの双方の1個前までの共通最大連続数に+1追加
            dp[i][j]=dp[i-1][j-1]+1
        else:
        # 一致しないとき
        # sの1個前までか、tの1個前の共通最大連続数の
        # 大きいほうを採用
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])

# 復元はs,tとも後ろから見ていく
ans = ''
i=ls
j=lt
while i != 0 and j != 0:
    if dp[i][j] == dp[i-1][j]:
        # DP上でsの一個前から更新されてない
        # 即ちs[i-1]は共通列に入ってない
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        # 上と同じ論法でtの場合
        j -= 1
    else:
        # 今見ているs[i-1]とt[j-1]が共通になっているとき
        # 答えに採用（s[i-1]は頭につける）
        ans = s[i-1] + ans 
        i -= 1
        j -= 1
        
print(ans)

Submission status: Time Limit Exceeded

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

LS=len(S)
LT=len(T)

DP=[[["",0] for j in range(LT+1)] for i in range(LS+1)]

for s in range(LS):
    for t in range(1,LT+1):
        if T[t-1]==S[s]:
            temp1=DP[s][t][0]+S[s]
            temp2=DP[s+1][t-1][0]+S[s]
            if len(temp1)<len(temp2) and DP[s+1][t-1][1]==0:
                DP[s+1][t][0]=temp2

            else:
                DP[s+1][t][0]=temp1
            DP[s + 1][t][1] = 1
        else:
            temp1 = DP[s][t][0]
            temp2 = DP[s + 1][t - 1][0]
            if len(temp1)<len(temp2):
                DP[s+1][t][0]=temp2
                DP[s+1][t][1]=DP[s+1][t-1][1]
            else:
                DP[s+1][t][0]=temp1
                DP[s+1][t][1]=0


ans=""
for i in range(LT+1):
    if len(DP[LS][i][0])>len(ans):
        ans=DP[LS][i][0]

print(ans)

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
dp1 = [["" for _ in range(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] + 1
            dp1[i + 1][j + 1] = dp1[i][j] + s[i]
        else:
            if dp[i+1][j] >= dp[i][j+1]:
                dp[i+1][j+1] = dp[i+1][j]
                dp1[i + 1][j + 1] = dp1[i + 1][j]
            else:
                dp[i + 1][j + 1] = dp[i][j+1]
                dp1[i + 1][j + 1] = dp1[i][j+1]

print(dp1[-1][-1])

Submission status: Time Limit Exceeded

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

dp = [["" for _ in range(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] + s[i]
        else:
            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]

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

Submission status: Time Limit Exceeded

Solution code:
### LCS 
# dp[i][j]: s[i],t[j]までの最長部分文字列の長さ
# s[i]==t[j]だったらs[i-1][j-1]+1,
# それ以外の場合はmax(s[i-1][j],s[i][j-1])

s= input()
t= input()

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for i, si in enumerate(s):
    for j, tj in enumerate(t):
        if si==tj:
            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 =""
n = dp[-1][-1]
i = len(s)
j =len(t)
while n >0:
    if dp[i][j]==dp[i-1][j]:
        i-= 1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    elif dp[i][j]==dp[i-1][j-1]+1:
        ans = s[i-1]+ans
        n-=1
        i-=1
        j-=1

print(ans)

Submission status: Time Limit Exceeded

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

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

for i in range(len(s)):
    for g in range(len(t)):
        if t[g]==s[i]:
            dp[g+1][i+1][0] = dp[g][i][0]+1
            dp[g+1][i+1][1] = dp[g][i][1] + t[g]
        else:
            if dp[g+1][i][0]>=dp[g][i+1][0]:
                dp[g+1][i+1]=dp[g+1][i]
            else:
                dp[g+1][i+1]=dp[g][i+1]

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

Submission status: Time Limit Exceeded

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

dp = [[-1]*3100 for _ in range(3100)]
# dp[i+1][j+1]: s[i], t[j]まで見たときのLCSの長さ

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5000)
S = input()
T = input()
r = ""
def dp(S,T,r):
    res = []
    #print("##",S,T,r)
    if len(T) == 0:
        return [r]
    res += dp(S,T[1:],r)
    if T[0] in S:
        r += T[0]
        S = S[S.index(T[0])+1:]
        if len(T) > 1:
            res += dp(S,T[1:],r)
        else:
            return [r]
    return res
R = dp(S,T,r)
ml = (0,"")
for r in R:
    l = len(r)
    if l > ml[0]:
        ml = (l,r)
print(ml[1])

Submission status: Time Limit Exceeded

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

Ls = len(S)
Lt = len(T)

dp = [[0] * (Lt + 1) for _ in range(Ls + 1)]

for i in range(Ls):
    for j in range(Lt):
        if S[i] == T[j]:
            # dp[i+1][j+1] = max(dp[i][j]+1, dp[i][j+1], dp[i+1][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])

match = []
now_row = Ls
now_column = Lt
while now_row > 0 and now_column > 0:
    if dp[now_row][now_column] == dp[now_row-1][now_column]:
        now_row -= 1
    elif dp[now_row][now_column] == dp[now_row][now_column-1]:
        now_column -= 1
    else:
        match.append(T[now_column-1])
        now_column -= 1
        now_row -= 1


match.reverse()
print("".join(match))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

# @profile
def calc_lcs(s, t):
  dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
  # dp = numpy.zeros((len(s)+1, len(t)+1))
  for i, si in enumerate(s, 1):
    for j, tj in enumerate(t, 1):
      dp[i][j] = max((dp[i-1][j-1] + 1) if si==tj else 0, dp[i-1][j], dp[i][j-1])

  lcs = ''
  i, j = len(s), 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
    elif dp[i][j] == dp[i-1][j-1]+1:
      lcs = s[i-1] + lcs
      i -= 1
      j -= 1
  return lcs

def main():
  s = input().strip()
  t = input().strip()
  print(calc_lcs(s, t))


if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

def calc_lcs(s, t):
  dp = numpy.zeros((len(s)+1, len(t)+1))
  for i, si in enumerate(s, 1):
    for j, tj in enumerate(t, 1):
      dp[i][j] = max((dp[i-1][j-1] + (1 if si==tj else 0), dp[i-1][j], dp[i][j-1]))

  lcs = ''
  i, j = len(s), len(t)
  while i > 0 and j > 0:
    if   dp[i][j] == dp[i-1][j-1]+1:
      lcs = s[i-1] + lcs
      i -= 1
      j -= 1
    elif dp[i][j] == dp[i-1][j]:
      i -= 1
    elif dp[i][j] == dp[i][j-1]:
      j -= 1
  return lcs

def main():
  s = input().strip()
  t = input().strip()
  print(calc_lcs(s, t))


if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def lcs(s, t):
  dp = [['' for _ in range(len(t)+1)] for _ in range(len(s)+1)]
  for i, si in enumerate(s, 1):
    for j, tj in enumerate(t, 1):
      dp[i][j] = max([''.join([dp[i-1][j-1], si]) if si==tj else '', dp[i-1][j], dp[i][j-1]], key=lambda x: len(x))
  return dp[-1][-1]

def main():
  s = input().strip()
  t = input().strip()
  print(lcs(s, t))


if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def lcs(s, t):
  dp = [['' for _ in range(len(t)+1)] for _ in range(len(s)+1)]
  for i, si in enumerate(s, 1):
    for j, tj in enumerate(t, 1):
      dp[i][j] = max([(dp[i-1][j-1]+si) if si==tj else '', dp[i-1][j], dp[i][j-1]], key=lambda x: len(x))
  return dp[-1][-1]

def main():
  s = input().strip()
  t = input().strip()
  print(lcs(s, t))


if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def lcs(s, t):
  dp = [['' for _ in range(len(t)+1)] for _ in range(len(s)+1)]
  for i, si in enumerate(s, 1):
    for j, tj in enumerate(t, 1):
      dp[i][j] = (dp[i-1][j-1] + si) if si==tj else (dp[i-1][j] if len(dp[i-1][j]) > len(dp[i][j-1]) else dp[i][j-1])
  return dp[-1][-1]

def main():
  s = input().strip()
  t = input().strip()
  print(lcs(s, t))


if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def lcs(s, t):
  dp = [['' for _ in range(len(t)+1)] for _ in range(len(s)+1)]
  for i, si in enumerate(s, 1):
    for j, tj in enumerate(t, 1):
      dp[i][j] = (dp[i-1][j-1] + si) if si==tj else max([dp[i-1][j], dp[i][j-1]], key=lambda x: len(x))
  return dp[-1][-1]

def main():
  s = input().strip()
  t = input().strip()
  print(lcs(s, t))


if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

def lcs(s, t):
  dp = [['' for _ in range(len(t)+1)] for _ in range(len(s)+1)]
  for i, si in enumerate(s, 1):
    for j, tj in enumerate(t, 1):
      dp[i][j] = max([(dp[i-1][j-1]+si) if si==tj else '', dp[i-1][j], dp[i][j-1]], key=lambda x: len(x))
  return dp[-1][-1]

def main():
  s = input().strip()
  t = input().strip()
  print(lcs(s, t))


if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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

dp = [[0 for i in range(len(S)+1)] for j in range(len(T)+1)]

for i in range(1,len(T)+1):
    for j in range(1,len(S)+1):
        if T[i-1]==S[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-1][j-1],dp[i][j-1],dp[i-1][j])
    # print(dp)


i = len(S)
j = len(T)
ans = []
while (i>0  and j>0):
    if dp[j][i] == dp[j-1][i]:
        j -= 1
    elif dp[j][i] == dp[j][i-1]:
        i -= 1
    else:
        ans.append(T[j-1]) 
        i -= 1
        j -= 1


print("".join(reversed(ans)))

Submission status: Time Limit Exceeded

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

ls = len(s)
lt = len(t)
ans = ""
dp = [[0]*(ls+1) for i in range(lt+1)]
memo = [[""]*(ls+1) for i in range(lt+1)]

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

i = lt
j = ls
while i-1>=0 and j-1>=0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
        continue
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
        continue
    else:

        i -= 1
        j -= 1
        ans = s[j] + ans

print(ans)

Submission status: Time Limit Exceeded

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

ls = len(s)
lt = len(t)
ans = ""
dp = [[0]*(ls+1) for i in range(lt+1)]
memo = [[""]*(ls+1) for i in range(lt+1)]

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

i = lt
j = ls
while i-1>=0 and j-1>=0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
        continue
    if dp[i][j] == dp[i][j-1]:
        j -= 1
        continue

    i -= 1
    j -= 1
    ans = s[j] + ans

print(ans)

Submission status: Time Limit Exceeded

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

    res = ""
    i = S
    j = T
    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]+res
            i -= 1
            j -= 1
    print(res)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    S = len(s)
    T = len(t)
    dp = [["" for j in range(T+1)] for _ in range(S+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:
                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[S][T])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    S = len(s)
    T = len(t)
    dp = [[[0, ""] for j in range(T+1)] for _ in range(S+1)]
    for i in range(S):
        for j in range(T):
            if s[i] == t[j]:
                dp[i+1][j+1][0] = dp[i][j][0]+1
                dp[i+1][j+1][1] = dp[i][j][1]+s[i]
            else:
                if dp[i+1][j][0] >= dp[i][j+1][0]:
                    dp[i+1][j+1][0] = dp[i+1][j][0]
                    dp[i+1][j+1][1] = dp[i+1][j][1]
                else:
                    dp[i+1][j+1][0] = dp[i][j+1][0]
                    dp[i+1][j+1][1] = dp[i][j+1][1]
    print(dp[S][T][1])


main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()
t = input()

num_s = len(s)
num_t = len(t)

dp = np.zeros((num_s + 1, num_t +1), dtype='int64')


for i in range(num_s):
    for j in range(num_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]])

# print(dp)

is_search = True
res=''
pos_s = num_s
pos_t = num_t


while len(res) < np.max(dp):
    temp = dp[pos_s, pos_t]
    # print(temp)
    if dp[pos_s-1, pos_t] == temp:
        pos_s -= 1

    if dp[pos_s, pos_t-1] == temp:
        pos_t -= 1

    if dp[pos_s-1, pos_t-1] != temp:
        res += s[pos_s-1]
        pos_s -= 1
        pos_t -= 1

    # print(res, pos_s-1)
        

print(res[::-1])

Submission status: Time Limit Exceeded

Solution code:
def solve(n, m, s, 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] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = 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:
            ans = s[n - 1] + ans
            n -= 1
            m -= 1
    print(ans)
    return

s = input()
t = input()

solve(len(s), len(t), s, t)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def solve():
    S = input()
    T = input()
    len_t = len(T)
    len_s = len(S)
    dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
    for i, s in enumerate(S):
        pre_dp_i = dp[i]
        dp_i = dp[i+1]
        for j, t in enumerate(T):
            tmp_dp = max((pre_dp_i[j] + 1) * (s == t),
                         pre_dp_i[j+1],
                         dp_i[j])
            dp_i[j+1] = tmp_dp
    res = ''
    while len_t > 0 and len_s > 0:
        current = dp[len_s][len_t]
        if current == dp[len_s - 1][len_t]:
            len_s -= 1
        elif current == dp[len_s][len_t - 1]:
            len_t -= 1
        else:
            res = S[len_s - 1] + res
            len_s -= 1
            len_t -= 1
    return res


if __name__ == "__main__":
    answer = solve()
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    S = input()
    T = input()
    len_t = len(T)
    len_s = len(S)
    dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
    for i, s in enumerate(S):
        pre_dp = 0
        pre_dp_i = dp[i][0]
        for j, t in enumerate(T):
            dp_i = dp[i][j+1]
            pre_dp = max((pre_dp_i + 1) * (s == t),
                         dp_i,
                         pre_dp)
            dp[i + 1][j + 1] = pre_dp
            pre_dp_i = dp_i
    res = ''
    while len_t > 0 and len_s > 0:
        current = dp[len_s][len_t]
        if current == dp[len_s - 1][len_t]:
            len_s -= 1
        elif current == dp[len_s][len_t - 1]:
            len_t -= 1
        else:
            res = S[len_s - 1] + res
            len_s -= 1
            len_t -= 1
    return res


if __name__ == "__main__":
    answer = solve()
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    S = input()
    T = input()
    len_t = len(T)
    len_s = len(S)
    dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
    for i, s in enumerate(S):
        pre_dp = 0
        pre_dp_i = dp[i][0]
        for j, (t, dp_i) in enumerate(zip(T, dp[i][1:])):
            pre_dp = max((pre_dp_i + 1) * (s == t),
                         dp_i,
                         pre_dp)
            dp[i + 1][j + 1] = pre_dp
            pre_dp_i = dp_i
    res = ''
    while len_t > 0 and len_s > 0:
        current = dp[len_s][len_t]
        if current == dp[len_s - 1][len_t]:
            len_s -= 1
        elif current == dp[len_s][len_t - 1]:
            len_t -= 1
        else:
            res = S[len_s - 1] + res
            len_s -= 1
            len_t -= 1
    return res


if __name__ == "__main__":
    answer = solve()
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    S = input()
    T = input()
    len_t = len(T)
    len_s = len(S)
    dp = [[0] * (len_t+1) for _ in range(len_s+1)]
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            dp[i+1][j+1] = max(dp[i][j]+1 * (s == t),
                               dp[i][j+1],
                               dp[i+1][j])
    res = ''
    while len_t > 0 and len_s > 0:
        current = dp[len_s][len_t]
        if current == dp[len_s-1][len_t]:
            len_s -= 1
        elif current == dp[len_s][len_t-1]:
            len_t -= 1
        else:
            res = S[len_s-1] + res
            len_s -= 1
            len_t -= 1
    return res


if __name__ == "__main__":
    answer = solve()
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys

input=sys.stdin.readline
s=input()
t=input()
n,m=len(s),len(t)

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

for i in range(n):
  for j in range(m):
    if s[i]!=t[j]:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
    else:
      dp[i+1][j+1]=dp[i][j]+1
      
i,j=n,m      
while i>0 and j>0:
  if s[i-1]==t[j-1]:
    ans.append(s[i-1])
    i-=1
    j-=1
  elif dp[i][j]==dp[i-1][j]:
    i-=1
  else:
    j-=1
print(''.join(ans[::-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys

input=sys.stdin.readline
s=input()
t=input()
n,m=len(s),len(t)

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

for i in range(n):
  for j in range(m):
    if s[i]!=t[j]:
      x=dp[i+1][j]
      y=dp[i][j+1]
      if x>y:
        dp[i+1][j+1]=dp[i+1][j]
        ans[i+1][j+1]=ans[i+1][j]
      else:
        dp[i+1][j+1]=dp[i][j+1]
        ans[i+1][j+1]=ans[i][j+1]
    else:
      x=dp[i][j]+1
      y=dp[i+1][j]
      z=dp[i][j+1]
      tmp=max(x,y,z)
      if x==tmp:
        dp[i+1][j+1]=dp[i][j]+1
        ans[i+1][j+1]=ans[i][j]+s[i]
      elif  y==tmp:
        dp[i+1][j+1]=dp[i+1][j]
        ans[i+1][j+1]=ans[i+1][j]
      else:
        ans[i+1][j+1]=ans[i][j+1]
        dp[i+1][j+1]=dp[i][j+1]
print(ans[n][m])

Submission status: Time Limit Exceeded

Solution code:
import sys

input=sys.stdin.readline
s=input()
t=input()
n,m=len(s),len(t)

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

for i in range(n):
  for j in range(m):
    if s[i]!=t[j]:
      x=len(dp[i+1][j])
      y=len(dp[i][j+1])
      if x>y:
        dp[i+1][j+1]=dp[i+1][j]
      else:
        dp[i+1][j+1]=dp[i][j+1]
    else:
      x=len(dp[i][j])+1
      y=len(dp[i+1][j])
      z=len(dp[i][j+1])
      tmp=max(x,y,z)
      if x==tmp:
        dp[i+1][j+1]=dp[i][j]+s[i]
      elif  y==tmp:
        dp[i+1][j+1]=dp[i+1][j]
      else:
        dp[i+1][j+1]=dp[i][j+1]
print(dp[n][m])

Submission status: Time Limit Exceeded

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

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

table = [['' for _ in range(lt + 1)] for __ in range(ls + 1)]

for ns in range(ls):
    for nt in range(lt):
        if s[ns] == t[nt]:
            table[ns + 1][nt + 1] = max(table[ns][nt] + s[ns], table[ns + 1][nt + 1], key=lambda x:len(x))
        table[ns + 1][nt + 1] = max(table[ns + 1][nt + 1], table[ns + 1][nt], table[ns][nt + 1] , key=lambda x:len(x))

print(table[-1][-1])

Submission status: Time Limit Exceeded

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

dp = [[0]*3100 for _ in range(3100)]
# dp[i+1][j+1]: s[i], t[j]まで見たときのLCSの長さ

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

Submission status: Time Limit Exceeded

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

def find_lcs_2(s, t):
    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] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    i, j = len(s), len(t)
    buffer = []
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j-1] + 1:
            buffer.append(s[i - 1])
            i, j = 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:
            raise Exception('wtf')
    return ''.join(reversed(buffer))
 
print(find_lcs_2(s, t))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    S=input()
    T=input()
    dp=[['']*(len(T)+1) for _ in range(len(S)+1)]
    for s in range(len(S)):
        for t in range(len(T)):
            if S[s]==T[t]:
                dp[s+1][t+1]=dp[s][t]+S[s]
            else:
                if len(dp[s+1][t])>len(dp[s][t+1]):
                    dp[s+1][t+1]=dp[s+1][t]
                else:
                    dp[s+1][t+1]=dp[s][t+1]
    print(dp[len(S)][len(T)])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

dp = [[""]*(len(s)+1) for _ in range(len(t)+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[j][i] = dp[j-1][i-1]+s[i-1]
			dp[j][i] = "{}{}".format(dp[j-1][i-1],s[i-1])
		else:
			if len(dp[j-1][i]) > len(dp[j][i-1]):
				dp[j][i] = dp[j-1][i]
			else:
				dp[j][i] = dp[j][i-1]

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

Submission status: Time Limit Exceeded

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

dp = [[""]*(len(s)+1) for _ in range(len(t)+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[j][i] = dp[j-1][i-1]+s[i-1]
		else:
			if len(dp[j-1][i]) > len(dp[j][i-1]):
				dp[j][i] = dp[j-1][i]
			else:
				dp[j][i] = dp[j][i-1]

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

Submission status: Time Limit Exceeded

Solution code:
def find_lcs(s, t):
    Len, Seq = range(2)
    ilen = len(s)
    jlen = len(t)
    dp = [[[0, ''] for _ in range(jlen + 1)] for _ in range(ilen + 1)]
    for i in range(1, ilen + 1):
        for j in range(1, jlen + 1):
            i_letter = s[i - 1]
            j_letter = t[j - 1]
            if i_letter == j_letter:
                dp[i][j][Len] = dp[i-1][j-1][Len] + 1
                dp[i][j][Seq] = dp[i - 1][j - 1][Seq] + i_letter
            else:
                l1, l2 = dp[i-1][j][Len], dp[i][j-1][Len]
                if l1 >= l2:
                    dp[i][j][Len] = l1
                    dp[i][j][Seq] = dp[i-1][j][Seq]
                else:
                    dp[i][j][Len] = l2
                    dp[i][j][Seq] = dp[i][j-1][Seq]
    return dp[-1][-1][Seq]
 
def read_input():
    s = str(input())
    t = str(input())
    print(find_lcs(s, t))
    
read_input()

Submission status: Time Limit Exceeded

Solution code:
def find_lcs(s, t):
    Len, Seq = range(2)
    ilen = len(s)
    jlen = len(t)
    dp = [[[0, ''] for _ in range(jlen + 1)] for _ in range(ilen + 1)]
    for i in range(1, ilen + 1):
        for j in range(1, jlen + 1):
            i_letter = s[i - 1]
            j_letter = t[j - 1]
            if i_letter == j_letter:
                dp[i][j][Len] = dp[i-1][j-1][Len] + 1
                dp[i][j][Seq] = dp[i - 1][j - 1][Seq] + i_letter
            else:
                l1, l2 = dp[i-1][j][Len], dp[i][j-1][Len]
                if l1 >= l2:
                    dp[i][j][Len] = l1
                    dp[i][j][Seq] = dp[i-1][j][Seq]
                else:
                    dp[i][j][Len] = l2
                    dp[i][j][Seq] = dp[i][j-1][Seq]
    return dp[-1][-1][Seq]

def read_input():
    s = str(input())
    t = str(input())
    print(find_lcs(s, t))
    
read_input()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    dp = [[0]*(len(s)+1) for _ in range((len(t)+1))]
    ans = ""
    for i in range(len(t)):
        for j in range(len(s)):
            tmp1 = dp[i+1][j]
            tmp2 = dp[i][j+1]
            tmp3 = dp[i][j]
            if t[i] == s[j]:
                tmp3 += 1
            dp[i+1][j+1] = max(tmp1,tmp2,tmp3)
    i = len(t)
    j = len(s)
    for k in range(10**6):
        if i < 0 or j < 0:
            break
        if dp[i-1][j-1]+1 == dp[i][j] and t[i-1] == s[j-1]:
            ans += t[i-1]
            i -= 1
            j -= 1
        elif dp[i-1][j] == dp[i][j]:
            i -= 1
        else:
            j -= 1
    # while i > 0 and j > 0:
    #     if dp[i-1][j-1]+1 == dp[i][j] and t[i-1] == s[j-1]:
    #         ans += t[i-1]
    #         i -= 1
    #         j -= 1
    #     elif dp[i-1][j] == dp[i][j]:
    #         i -= 1
    #     else:
    #         j -= 1
    print(ans[::-1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    dp = [[0]*(len(s)+1) for _ in range((len(t)+1))]
    ans = ""
    for i in range(len(t)):
        for j in range(len(s)):
            tmp1 = dp[i+1][j]
            tmp2 = dp[i][j+1]
            tmp3 = dp[i][j]
            if t[i] == s[j]:
                tmp3 += 1
            dp[i+1][j+1] = max(tmp1,tmp2,tmp3)
    i = len(t)
    j = len(s)
    for k in range(10**9):
        if i < 0 or j < 0:
            break
        if dp[i-1][j-1]+1 == dp[i][j] and t[i-1] == s[j-1]:
            ans += t[i-1]
            i -= 1
            j -= 1
        elif dp[i-1][j] == dp[i][j]:
            i -= 1
        else:
            j -= 1
    # while i > 0 and j > 0:
    #     if dp[i-1][j-1]+1 == dp[i][j] and t[i-1] == s[j-1]:
    #         ans += t[i-1]
    #         i -= 1
    #         j -= 1
    #     elif dp[i-1][j] == dp[i][j]:
    #         i -= 1
    #     else:
    #         j -= 1
    print(ans[::-1])

if __name__ == '__main__':
    main()