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()
n = len(s)
t = input()
m = len(t)
dp = [['']*(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]
        else:
            dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j],key = lambda x:len(x))
print(dp[n][m])

Submission status: Time Limit Exceeded

Solution code:
#dp[i+1][j+1]:sのi番目までの文字、tのj番目までの文字のLCS
#dp[i+1][j+1] = max(dp[i+1][j]+1, dp[i][j+1]+1, dp[i][j]+1) (s[i]==t[j])
#dp[i+1][j+1] = max(dp[i+1][j]+1, dp[i][j+1]+1) (s[i]!=s[j])
#dp[i]]j]<=(dp[i+1][j],dp[i][j+1])
s = input()
t = input()

n = len(s)
m = len(t)
dp = [['' for j in range(m+1)] for i in range(n+1)]

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 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[n][m])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
n,m = map(len,[s,t])

dp = [['' 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]
        else:
            dp[i+1][j+1] = dp[i][j]
        dp[i+1][j+1] = dp[i+1][j] if len(dp[i+1][j])>len(dp[i+1][j+1]) else dp[i+1][j+1]
        dp[i+1][j+1] = dp[i][j+1] if len(dp[i][j+1])>len(dp[i+1][j+1]) else dp[i+1][j+1]
print(dp[n][m])

Submission status: Time Limit Exceeded

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

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

for i in range(len(t)):
  for j in range(len(s)):
    if t[i] == s[j]:
      dp[i+1][j+1] = dp[i][j] + t[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
import numpy as np

sys.setrecursionlimit(10 ** 9)

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

dp = [['' for _ in range(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]+ s[i-1]
        elif 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]

ans = ''
for j in range(M+1):
    if len(dp[-1][j]) > len(ans):
        ans = dp[-1][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
lenS = len(S)
lenT = len(T)
dp = [[0]*(lenT+1)for _ in range(lenS+1)]

for i in range(1,lenS+1):
    for j in range(1,lenT+1):
        if S[i-1]==T[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
ans = ""
m = lenS
n = lenT
while m and n:
    if dp[m][n]==dp[m-1][n]:
        m -= 1
    elif dp[m][n]==dp[m][n-1]:
        n -= 1
    else:
        m -= 1
        n -= 1
        ans = T[n]+ans

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#dp[i+1][j+1]:=Sのi文字目までとTのj文字目までのLCSの長さ
def main():
    S=input()
    T=input()
    ls=len(S)
    lt=len(T)

    dp=[["" for j in range(lt+1)] for i 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]+S[i],dp[i+1][j],dp[i][j+1],key=len)
            else:
                dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1],key=len)
    print(dp[ls][lt])

main()

Submission status: Time Limit Exceeded

Solution code:
#dp[i+1][j+1]:=Sのi文字目までとTのj文字目までのLCSの長さ
S=input()
T=input()
ls=len(S)
lt=len(T)

dp=[["" for j in range(lt+1)] for i 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]+S[i],dp[i+1][j],dp[i][j+1],key=len)
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1],key=len)
print(dp[ls][lt])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(s: str, t: str):
    dp = [["" for i in range(len(t)+1)]for j in range(len(s)+1)]
    for i in range(1,len(s)+1):
        for j in range(1,len(t)+1):
            if s[i-1] == t[j-1]:
                dp[i][j]=dp[i-1][j-1]+s[i-1]
            else:
                dp[i][j] = dp[i-1][j] if len(dp[i-1][j]) >= len(dp[i][j-1]) else dp[i][j-1]
    print(dp[-1][-1])
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
#dp[i+1][j+1]:=Sのi文字目までとTのj文字目までのLCSの長さ
S=input()
T=input()
ls=len(S)
lt=len(T)

dp=[["" for j in range(lt+1)] for i 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]+S[i],dp[i+1][j],dp[i][j+1],key=len)
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1],key=len)
print(dp[ls][lt])

Submission status: Time Limit Exceeded

Solution code:
def make_lcs(a,b):
    a_size = len(a)
    b_size = len(b)
    lcs = [[0 for _ in range(a_size+1)] for _ in range(b_size+1)]
    for i in range(1,b_size+1):
        for j in range(1,a_size+1):
            if a[j-1] == b[i-1]:
                match = 1
            else:
                match = 0
            lcs[i][j] = max(lcs[i-1][j-1]+match, lcs[i-1][j], lcs[i][j-1])
    # ここまではlcs()と同じ

    # lcsを使用して復元
    res = ''
    i,j = b_size,a_size
    while((i>0) & (j>0)):
        if lcs[i][j] == lcs[i-1][j]:
            i -= 1
        elif lcs[i][j] == lcs[i][j-1]:
            j -= 1
        else:
            res = b[i-1] + res
            i -= 1
            j -= 1
    return res

def main():
    a = list(input())
    b = list(input())
    print(make_lcs(a,b))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
 
def lis(A: list):
    L = [A[0]]
    for a in A[1:]:
        if a > L[-1]:
            # Lの末尾よりaが大きければ増加部分列を延長できる
            L.append(a)
        else:
            # そうでなければ、「aより小さい最大要素の次」をaにする
            # 該当位置は、二分探索で特定できる
            L[bisect_left(L, a)] = a
    return len(L)

# l = [7,5,3,1,8]
# n = int(input())
# l = list(map(int,input().split()))

def dp_bubunnwa(l):
    n = len(l)
    m = sum(l)
    dp = [[0]*(m+1) for _ in range(n+1)]

    dp[0][0] = 1
    for i in range(n):
        for j in range(m+1):
            if l[i] <= j:
                dp[i+1][j] = dp[i][j-l[i]]+dp[i][j]
            else:
                dp[i+1][j] = dp[i][j]
    return dp

def bfs(G,start):
    from collections import deque
    dist = [-1] * n
    dist[start] = 0
    q = deque([start])
    add,pop=q.append,q.popleft
    while q:
        v = pop()
        for nv in G[v]:
            if dist[nv] < 0:
                dist[nv] = dist[v]+1
                add(nv)
            # 2部グラフ判定
            # else:
            #     if dist[v]%2 == dist[nv]%2:
            #         is_bipartite = False
    return dist


def lcs(a,b):
    a_size = len(a)
    b_size = len(b)
    lcs = [[0 for _ in range(a_size+1)] for _ in range(b_size+1)]
    for i in range(1,b_size+1):
        for j in range(1,a_size+1):
            if a[j-1] == b[i-1]:
                match = 1
            else:
                match = 0
            lcs[i][j] = max(lcs[i-1][j-1]+match, lcs[i-1][j], lcs[i][j-1])
    return lcs

def make_lcs(a,b):
    a_size = len(a)
    b_size = len(b)
    lcs = [[0 for _ in range(a_size+1)] for _ in range(b_size+1)]
    for i in range(1,b_size+1):
        for j in range(1,a_size+1):
            if a[j-1] == b[i-1]:
                match = 1
            else:
                match = 0
            lcs[i][j] = max(lcs[i-1][j-1]+match, lcs[i-1][j], lcs[i][j-1])
    # ここまではlcs()と同じ

    # lcsを使用して復元
    res = ''
    i,j = b_size,a_size
    while((i>0) & (j>0)):
        if lcs[i][j] == lcs[i-1][j]:
            i -= 1
        elif lcs[i][j] == lcs[i][j-1]:
            j -= 1
        else:
            res = b[i-1] + res
            i -= 1
            j -= 1
    return res
a = list(input())
b = list(input())
print(make_lcs(a,b))

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
lenS = len(S)
lenT = len(T)

dp = [[0]*(lenS+1)for _ in range(lenT+1)]
for i in range(1,lenT+1):
  t = T[i-1]
  for j in range(1,lenS+1):
    s = S[j-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 = ""
m=lenT
n=lenS
while m and n:
  if dp[m][n] == dp[m-1][n]:
    m = m-1
  elif dp[m][n] == dp[m][n-1]:
    n = n-1
  else:
    m = m-1
    n = n-1
    ans = "".join([S[n],ans])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
S = list(input())
T = list(input())
m, n = len(S), len(T)
C = [[[] for j in range(n+1)] for i in range(m+1)]
for i in range(m):
    for j in range(n):
        if S[i] == T[j]:
            Cij = copy.copy(C[i][j])
            Cij.append(S[i])
            C[i+1][j+1] = Cij
        elif len(C[i+1][j]) >= len(C[i][j+1]):
            C[i+1][j+1] = C[i+1][j]
        else:
            C[i+1][j+1] = C[i][j+1]
print(''.join(C[m][n]))

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
T = list(input())
m, n = len(S), len(T)
C = [['' for j in range(n+1)] for i in range(m+1)]
for i in range(m):
    for j in range(n):
        if S[i] == T[j]:
            C[i+1][j+1] = C[i][j]+S[i]
        elif len(C[i+1][j]) >= len(C[i][j+1]):
            C[i+1][j+1] = C[i+1][j]
        else:
            C[i+1][j+1] = C[i][j+1]
print(C[m][n])

Submission status: Time Limit Exceeded

Solution code:
s,t=[input() for i in (0,0)]
T,S=len(t),len(s)
dp=[["" for j in range(T+1)] for i 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:dp[i+1][j+1]=max(dp[i][j],dp[i+1][j],dp[i][j+1],key=lambda x:len(x))
print(dp[S][T])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
lenS = len(s)
lenT = len(t)

dp = [[0]*(lenT+1)for _ in range(lenS+1)]

for i in range(1,lenS+1):
  for j in range(1,lenT+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])
      
m = lenS
n = lenT
ans = ""
while m or n:
  if m:
    if dp[m][n] == dp[m-1][n]:
      m -= 1
      continue
  if n:
    if dp[m][n] == dp[m][n-1]:
      n -= 1
      continue
    else:
      m -= 1
      n -= 1
      ans = "".join([s[m],ans])
    continue
print(ans)

Submission status: Time Limit Exceeded

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

ls,lt = len(s), len(t)
# dp[i][j] : siとtjにおけるLCS
dp = [['']*(lt+1) for _ in range(ls+1)]

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

Submission status: Time Limit Exceeded

Solution code:
def get_lcs_table(s1, s2):
    l1, l2 = len(s1)+1, len(s2)+1
    dp = [[0]*l2 for _ in range(l1)]
    for i in range(l1):
        for j in range(l2):
            dp[i][j] = 0 if i==0 or j==0 else dp[i-1][j-1]+1 if s1[i-1]==s2[j-1] else max(dp[i][j-1], dp[i-1][j])
    return dp


def restore_lcs(s1, s2, dp):
    x, y = len(s1), len(s2)
    l = []
    while x and y:
        if dp[x][y] == dp[x-1][y]:
            x -= 1
        elif dp[x][y] == dp[x][y-1]:
            y -= 1
        else:
            x -= 1
            y -= 1
            l.append(s1[x])
    return "".join(l[::-1])


if __name__ == "__main__":
    s = input()
    t = input()
    dp = get_lcs_table(s, t)
    print(restore_lcs(s, t, dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

##moji利用したらTLE
S = input()
T = input()
ls = len(S)+1
lt = len(T)+1
'''
dp = dp2(0, ls, lt)

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

for i in range(1, lt):
    for j in range(1, ls):
        if S[j-1]==T[i-1]:
            dp[i][j] = dp[i-1][j-1]+1
            #moji[i][j] = moji[i-1][j-1] + S[j-1]
        else:
            if dp[i-1][j] >= dp[i][j-1]:
                dp[i][j] = dp[i-1][j]
                #moji[i][j] = moji[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
                #moji[i][j] = moji[i][j-1]

#print(moji[lt-1][ls-1])
ans = ''
i = lt-1
j = ls-1
while i > 0 and j > 0:
    if dp[i][j] > dp[i-1][j-1] and S[j-1]==T[i-1]:
        ans += S[j-1]
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1

print(ans[::-1])
'''
'''
##TLE

dp = [[[0, ''] for j in range(ls)] for i in range(lt)]

for i in range(1, lt):
    for j in range(1, ls):
        if S[j-1]==T[i-1]:
            dp[i][j][0] = dp[i-1][j-1][0]+1
            dp[i][j][1] = dp[i-1][j-1][1] + S[j-1]
        else:
            if dp[i-1][j][0] >= dp[i][j-1][0]:
                dp[i][j][0] = dp[i-1][j][0]
                dp[i][j][1] = dp[i-1][j][1]
            else:
                dp[i][j][0] = dp[i][j-1][0]
                dp[i][j][1] = dp[i][j-1][1]
#print(dp)
print(dp[lt-1][ls-1][1])
'''

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

for i in range(1, lt):
    for j in range(1, ls):
        if S[j-1]==T[i-1]:
            dp[i][j] = dp[i-1][j-1] + S[j-1]
            #moji[i][j] = moji[i-1][j-1] + S[j-1]
        else:
            if len(dp[i-1][j]) >= len(dp[i][j-1]):
                dp[i][j] = dp[i-1][j]
                #moji[i][j] = moji[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
                #moji[i][j] = moji[i][j-1]
#print(dp)
print(dp[lt-1][ls-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

S = input()
T = input()
ls = len(S)+1
lt = len(T)+1
'''
dp = dp2(0, ls, lt)

moji = [['']*ls for i in range(lt)]
#print(moji)
for i in range(1, lt):
    for j in range(1, ls):
        if S[j-1]==T[i-1]:
            dp[i][j] = dp[i-1][j-1]+1
            moji[i][j] = moji[i-1][j-1] + S[j-1]
        else:
            if dp[i-1][j] >= dp[i][j-1]:
                dp[i][j] = dp[i-1][j]
                moji[i][j] = moji[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
                moji[i][j] = moji[i][j-1]
print(moji)
print(moji[lt-1][ls-1])
'''
#dp = dp2(0, ls, lt)

dp = [[[0, ''] for j in range(ls)] for i in range(lt)]
#print(moji)
#print(dp)

for i in range(1, lt):
    for j in range(1, ls):
        if S[j-1]==T[i-1]:
            dp[i][j][0] = dp[i-1][j-1][0]+1
            dp[i][j][1] = dp[i-1][j-1][1] + S[j-1]
        else:
            if dp[i-1][j][0] >= dp[i][j-1][0]:
                dp[i][j][0] = dp[i-1][j][0]
                dp[i][j][1] = dp[i-1][j][1]
            else:
                dp[i][j][0] = dp[i][j-1][0]
                dp[i][j][1] = dp[i][j-1][1]
#print(dp)
print(dp[lt-1][ls-1][1])

Submission status: Time Limit Exceeded

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

S = input()
T = input()
ls = len(S)+1
lt = len(T)+1

dp = dp2(0, ls, lt)

moji = [['']*ls for i in range(lt)]
#print(moji)

for i in range(1, lt):
    for j in range(1, ls):
        if S[j-1]==T[i-1]:
            dp[i][j] = dp[i-1][j-1]+1
            moji[i][j] = moji[i-1][j-1] + S[j-1]
        else:
            #print(i, j)
            if dp[i-1][j] >= dp[i][j-1]:
                dp[i][j] = dp[i-1][j]
                moji[i][j] = moji[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
                moji[i][j] = moji[i][j-1]

print(moji[lt-1][ls-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

    slen = len(s)
    tlen = len(t)
    dp = [[0 for _ in range(tlen + 1)] for _ in range(slen + 1)]

    for i in range(slen):
        for j in range(tlen):
            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][j+1])

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s=input()
f=input()
l=[]
for i in range(len(s)+1):
    l.append([0]*(len(f)+1))

for i in range(1,len(s)+1):
    for j in range(1,len(f)+1):
        if s[i-1]==f[j-1]:
            l[i][j]=l[i-1][j-1]+1
        else:
            l[i][j]=max(l[i-1][j],l[i][j-1])
ans=""
i,j=len(s),len(f)
while(i>=1 and j>=1):
    if s[i-1]==f[j-1]:
        ans+=f[j-1]
        i-=1
        j-=1
    elif l[i-1][j]>l[i][j-1]:
        i-=1
    else:
        j-=1
ans=ans[-1::-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import string
import random

str_ = string.ascii_lowercase

# S = np.array(random.choices(str_, k=3000))
# T = np.array(random.choices(str_, k=3000))
S = np.array(list(input()))
T = np.array(list(input()))
s_len = len(S)
t_len = len(T)

dp = np.zeros((s_len+1,t_len+1),dtype=int)


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

ans = ''
i = s_len
j = t_len
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans = S[i-1] + ans
        i -= 1
        j -= 1
        # print(ans)
        continue
    if dp[i-1][j] >= dp[i][j-1]:
        i -= 1
    else:
        j -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
p = input()
n, m = len(s), len(p)

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

for i in range(n + 1):
    for j in range(m + 1):
        if i == 0 or j == 0:
            # print(i,j)
            dp[i][j] = 0
        elif s[i - 1] == p[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 = n, m
ans = []

while i and j:
    if s[i - 1] == p[j - 1]:
        ans.append(s[i - 1])
        i -= 1
        j -= 1
    elif dp[i - 1][j] > dp[i][j - 1]:
        i -= 1
    else:
        j -= 1

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
LCS = ""
DP = [[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1] == t[j-1]:
            DP[i][j] = DP[i-1][j-1] + 1
        else:
            DP[i][j] = max(DP[i-1][j], DP[i][j-1])
k = DP[i][j]
while k > 0:
    if DP[i][j] == DP[i][j-1]:
        j -= 1
    elif DP[i][j] == DP[i-1][j]:
        i -= 1
    else:
        LCS += s[i-1]
        i -= 1
        j -= 1
        k -= 1
print(LCS[::-1])

Submission status: Time Limit Exceeded

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

#output
def lcs(s, t):
    m = len(s)
    n = len(t)
    matrix = [["" for x in range(n)] for x in range(m)]
    for i in range(m):
        for j in range(n):
            if s[i] == t[j]:
                if i == 0 or j == 0:
                    matrix[i][j] = s[i]
                else:
                    matrix[i][j] = matrix[i-1][j-1] + s[i]
            else:
                matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1], key=len)

    cs = matrix[-1][-1]

    return cs

print(lcs(s, t))

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
t = list(input())
ls = len(s)
lt = len(t)
dp = [[[] for i in range(lt+1)] for i in range(ls+1)]
for i in range(ls):
    flag = True
    for j in range(lt):
        if flag and s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i][j+1]+[s[i]],dp[i+1][j]+[s[i]],key=lambda x: len(x))
            flag= False
        elif s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i][j+1]+[s[i]],dp[i+1][j],key=lambda x: len(x))
        else:
            dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j],key=lambda x: len(x))
print(''.join(dp[ls][lt]))

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
T = list(input())
s_len = len(S)
t_len = len(T)
# Create array for DP which has over one element.
dp = [[0]*(t_len+1) for i in range(s_len+1)] 

# Get the length of　answer with DP
for i in range(s_len):
    for j in range(t_len):
        if S[i] == T[j]:
            dp[i+1][j+1] = max(dp[i][j+1]+1,dp[i+1][j])
        else:
            dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])

# Output
ans = ''
i = s_len
j = t_len
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans = S[i-1] + ans
        i -= 1
        j -= 1
        # print(ans)
        continue
    if dp[i-1][j] >= dp[i][j-1]:
        i -= 1
    else:
        j -= 1
print(ans)

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(1,N+1):
    for k in range(1,M+1):
        if S[i-1] == T[k-1]:
            dp[i][k] = dp[i-1][k-1] + 1
        else:
            dp[i][k] = max(dp[i-1][k],dp[i][k-1])
ans = ''
x = N
y = M
while x > 0 and y > 0:
    if dp[x][y] == dp[x-1][y]:
        x -= 1
    elif dp[x][y] == dp[x][y-1]:
        y -= 1
    else:
        x -= 1
        y -= 1
        ans += S[x]
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
T = list(input())
# Create array for DP which has over one element.
dp = [[str()]*(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] = max(dp[i][j+1]+S[i],dp[i+1][j],key = len)
        else:
            dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j],key = len)

print(dp[len(S)][len(T)])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input().strip()
t = input().strip()

dp = np.zeros((3100, 3100))

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:
import numpy as np
import sys
sys.setrecursionlimit(200000)

X = input()
Y = input()
lenX = len(X)
lenY = len(Y)
dp = np.full((lenX+1,lenY+1),"-1",dtype=object)
dp[0,:]=""
dp[:,0]=""
def f(i,j):
  if dp[i][j]=="-1":
    x = X[i-1]
    y = Y[j-1]
    lo = f(i-1,j-1)
    l = f(i,j-1)
    o = f(i-1,j)
    if x==y:
      dp[i][j]="".join([lo,x])
    else:
      if len(l)>=len(o):
        dp[i][j]=l
      else:
        dp[i][j]=o
  return dp[i][j]

print(f(lenX,lenY))

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
len_s, len_t = len(s), len(t)
dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
for index_s in range(len_s):
  char_s = s[index_s]
  dp_s = dp[index_s]
  dp_ss = dp[index_s + 1]
  for index_t in range(len_t):
    if char_s == t[index_t]:
      dp_ss[index_t + 1] = dp_s[index_t] + 1
    else:
      dp_ss[index_t + 1] = max(dp_s[index_t + 1], dp_ss[index_t])
index_s, index_t = len_s - 1, len_t - 1
lcs_reverse = []
len_lcs = dp_ss[-1]
while len_lcs > 0:
  if s[index_s] == t[index_t]:
    lcs_reverse.append(s[index_s])
    index_s -= 1
    index_t -= 1
    len_lcs -= 1
  elif dp[index_s][index_t + 1] == len_lcs:
    index_s -= 1
  else:
    index_t -= 1
print(''.join(lcs_reverse[::-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()
t = input()
len_s, len_t = len(s), len(t)
dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
for index_s in range(len_s):
  char_s = s[index_s]
  dp_s = dp[index_s]
  dp_ss = dp[index_s + 1]
  for index_t in range(len_t):
    if char_s == t[index_t]:
      dp_ss[index_t + 1] = dp_s[index_t] + 1
    else:
      dp_ss[index_t + 1] = max(dp_s[index_t + 1], dp_ss[index_t])
index_s, index_t = len_s - 1, len_t - 1
lcs_reverse = []
len_lcs = dp_ss[-1]
while len_lcs > 0:
  if s[index_s] == t[index_t]:
    lcs_reverse.append(s[index_s])
    index_s -= 1
    index_t -= 1
    len_lcs -= 1
  elif dp[index_s][index_t + 1] == len_lcs:
    index_s -= 1
  else:
    index_t -= 1
print(''.join(lcs_reverse[::-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()
t = input()
len_s, len_t = len(s), len(t)
dp = np.zeros((len_s + 1, len_t + 1), dtype=np.int)
for index_s in range(len_s):
  char_s = s[index_s]
  for index_t in range(len_t):
    if char_s == t[index_t]:
      dp[index_s + 1, index_t + 1] = dp[index_s, index_t] + 1
    else:
      dp[index_s + 1, index_t + 1] = max(
        dp[index_s, index_t + 1], dp[index_s + 1, index_t])
index_s, index_t = len_s - 1, len_t - 1
lcs_reverse = []
len_lcs = dp[-1, -1]
while len_lcs > 0:
  if s[index_s] == t[index_t]:
    lcs_reverse.append(s[index_s])
    index_s -= 1
    index_t -= 1
    len_lcs -= 1
  elif dp[index_s, index_t + 1] == len_lcs:
    index_s -= 1
  elif dp[index_s + 1, index_t] == len_lcs:
    index_t -= 1
  else:
    raise ValueError
print(''.join(lcs_reverse[::-1]))

Submission status: Time Limit Exceeded

Solution code:


def submit():
    s = input()
    t = input()

    # dp[i][j] : sをi、tをjまで見た時のlcs長
    # dp[i + 1][j + 1] = {
    #   dp[i][j] + 1, 
    #   dp[i + 1][j] or dp[i][j + 1]のいずれか
    # }

    dp = [[0 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
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
    
    # 再構成する
    i = len(s)
    j = len(t)
    ans = ""
    while dp[i][j]:
        if s[i - 1] == t[j - 1]:
            ans = s[i - 1] + ans
            i -= 1
            j -= 1
        else:
            if dp[i][j] == dp[i - 1][j]:
                i -= 1
            else:
                j -= 1
    print(ans)


submit()

Submission status: Time Limit Exceeded

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

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


    check = 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][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:
            ans = s[i-1] + ans
            i -= 1
            j -= 1
    print(ans)        
if __name__ == "__main__":
    main()