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:
def lcs(s,t):
    n=len(s)
    m=len(t)
    dp=[[0 for i in range(m+1)] for j in range(n+1)]
    for i in range(n+1):
        for j in range(m+1):
            if i==0 or j==0:
                dp[i][j]=0
            elif 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=n
    j=m
    ans=""
    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
    return ans
  
s=input()
t=input()
ans=lcs(s,t)
for i in range(len(ans)-1,-1,-1):
    print(ans[i],end="")

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = input()
  t = input()
  sn, tn = len(s), len(t)
  dp = [[0]*(tn+1) for _ in range(sn+1)]
  for i, si in enumerate(s):
    di, di2 = dp[i], dp[i+1]
    for j, ti in enumerate(t):
      if si == ti:
        di2[j+1] = di[j] + 1
      else:
          if di[j+1] > di[j]:
              di2[j+1] = di[j+1]
          else:
              di2[j+1] = di2[j]
    dp[i+1] = di2
  ans = ""
  while sn and tn:
    di = dp[sn][tn]
    if di == dp[sn][tn-1]:
      tn -= 1
    elif di == dp[sn-1][tn]:
      sn -= 1
    else:
      tn -= 1
      sn -= 1
      ans += s[sn]
      
  print(ans[::-1])

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = input()
  t = input()
  sn, tn = len(s), len(t)
  dp = [[""]*(tn+1) for _ in range(sn+1)]
  for i, si in enumerate(s):
    di, di2 = dp[i], dp[i+1]
    for j, ti in enumerate(t):
      ji = j+1
      if si == ti:
        di2[ji] = di[j] + si
      else:
          if len(di[ji]) > len(di2[j]):
              di2[ji] = di[ji]
          else:
              di2[ji] = di2[j]
    dp[i+1] = di2
  print(dp[sn][tn])

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = input()
  t = input()
  sn, tn = len(s), len(t)
  dp = [[""]*(tn+1) for _ in range(sn+1)]
  for i, si in enumerate(s):
    di, di2 = dp[i], dp[i+1]
    for j, ti in enumerate(t):
      if si == ti:
        di2[j+1] = di[j] + si
      else:
          if len(di[j+1]) > len(di[j]):
              di2[j+1] = di[j+1]
          else:
              di2[j+1] = di2[j]
    dp[i+1] = di2
  print(dp[sn][tn])

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

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

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

res = ""
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:
        res = s[x-1] + res
        x -= 1
        y -= 1
print(res)

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

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

Submission status: Time Limit Exceeded

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

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


print(word[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
def lcs(S,T):
    m = len(S)
    n = len(T)
    dp = [[0]*(n+1) for x in range(m+1)]
    
#計算量はO(MN)、DP表の作成
    for i in range(m):
        for j in range(n):
            if S[i] == T[j]:#同じやったときは+1延ばし斜めに移動
                dp[i+1][j+1] = dp[i][j] + 1
            else:#違うかったら、最長は上と左の大きいほうをもってくる
                dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
# if I want to know the length of the Lcs, return dp[m][n]
#文字列の復元（複数の場合は、そのうちの一つ）
    ans = ''
    while m!=0 and n!=0:#どっちも0になるまで、後ろから復元
        if dp[m][n] == dp[m-1][n]:#dp表を上に動かす
            m-=1
        elif dp[m][n] == dp[m][n-1]:#dp表を左に動かす
            n-=1
        else:#斜めの移動(S[i]==T[j])のときだけ、LCS伸びているので延ばす
            m-=1
            n-=1
            ans=S[m]+ans#これはT[n]でもいい
    return ans
#----------------------------------------------------------------
S = input()
T = input()
print(lcs(S,T))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
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 LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	s = IS()
	t = IS()
	n = len(s)
	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(s[i]==t[j]):
				c = [dp[i+1][j],dp[i][j+1],dp[i][j]+s[i]]
				p = np.argmax(list(map(len, c)))
				dp[i+1][j+1] = c[p]
			else:
				c = [dp[i+1][j],dp[i][j+1]]
				p = np.argmax(list(map(len, c)))
				dp[i+1][j+1] = c[p]
	print(dp[n][m])

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

import sys

def main():
    S = input()
    T = input()
    N, M = len(S), len(T)
    # Sのi文字目までTのj文字目までのLCSの長さ
    dp = [[0]*(M+1) for _ in range(N+1)]
    for i in range(1,N+1):
        for j in range(1,M+1):
            if S[i-1] == T[j-1]:
                dp[i][j] = dp[i-1][j-1]+1
            dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1])
    i, j = N, M
    ret = ''
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:    # i-1から更新された
            i -= 1
        elif dp[i][j] == dp[i][j-1]:  # j-1から更新された
            j -= 1
        else:                         # i-1, j-1から更新された
            i -= 1
            j -= 1
            ret += S[i]
#    print(dp)
    print(ret[::-1])

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math


def main():
    s1 = input()   
    s2 = input()
    
    dp = [[0]*(len(s2)+1) for x in range(len(s1)+1)]
    for x in range(len(s1)):
        dp[x][0] = 0
    for x in range(len(s2)):
        dp[0][x] = 0
    
    for x in range(1,len(s1)+1):
        for y in range(1,len(s2)+1):
            if s1[x-1]==s2[y-1]:
                dp[x][y] = dp[x-1][y-1]+1
            else:
                dp[x][y] = max(dp[x][y-1],dp[x-1][y])
    x = len(s1)
    y = len(s2)
    s = ""
    while x > 0 and y > 0:
        if(s1[x-1]==s2[y-1]):
            s+=s1[x-1]
            x-=1
            y-=1
        elif dp[x-1][y] > dp[x][y-1]:
            x-=1
        else:
            y-=1
    print(s[::-1])
    
main()

Submission status: Time Limit Exceeded

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def solve():

    S = input()
    T = input()

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

    dp = [[0] * (LT + 1) for _ in range(LS + 1)]
    pre = [[None] * (LT + 1) for _ in range(LS + 1)]
    for i in range(LS):
        for j in range(LT):
            now = 0
            if S[i] == T[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
                pre[i+1][j+1] = 1
            else:
                if dp[i + 1][j] < dp[i][j + 1]:
                    dp[i + 1][j + 1] = dp[i][j + 1]
                    pre[i+1][j+1] = 2
                else:
                    dp[i + 1][j + 1] = dp[i + 1][j]
                    pre[i+1][j+1] = 3

    # print(dp)

    # for p in pre:
        # print(p)

    si = LS
    ti = LT
    ans = []

    while not ((si == 0) and (ti == 0)):
        frm = pre[si][ti]
        if frm == 1:
            si -= 1
            ti -= 1
            ans.append(S[si])
        elif frm == 2:
            si -= 1
        elif frm == 3:
            ti -= 1
        elif frm == None:
            break

    return ans[::-1]


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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
import sys
sys.setrecursionlimit(100000)


def read():
    s = input()
    t = input()
    return s, t


def lcs(s, t):
    S = len(s)
    T = len(t)
    dp = [[0 for j in range(T+1)] for i in range(S+1)]
    maxpos = (0, 0)
    for i, j in product(range(S), range(T)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
            if dp[maxpos[0]+1][maxpos[1]+1] < dp[i+1][j+1]:
                maxpos = (i, j)
        else:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])
    return maxpos, dp


def dfs(s, t, i, j, dp):
    if i < 0 or j < 0:
        return list()
    if s[i] == t[j]:
        x = dfs(s, t, i-1, j-1, dp)
        return x + [i]
    else:
        x = dfs(s, t, i-1, j, dp)
        y = dfs(s, t, i, j-1, dp)
        return x if len(x) > len(y) else y


def solve(s, t):
    maxpos, dp = lcs(s, t)
    i, j = maxpos
    x = dfs(s, t, i, j, dp)
    ans = ''.join([s[i] for i in x])
    return ans


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Time Limit Exceeded

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

NS = len(s)
NT = len(t)

dp = [[0] * (NT+2) for i in range(NS+2)]
dp2 = [[""] * (NT+2) for i in range(NS+2)]

for i in range(1,NS+1):
    for j in range(1,NT+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = max(dp[i-1][j-1]+1, dp[i-1][j], dp[i][j-1])
            if dp[i-1][j-1]+1 > dp[i-1][j] and dp[i-1][j-1]+1 > dp[i][j-1]:
                dp2[i][j] = dp2[i-1][j-1] + s[i-1]
            elif dp[i-1][j] > dp[i][j-1]:
                dp2[i][j] = dp2[i-1][j]
            else:
                dp2[i][j] = dp2[i][j-1]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            if dp[i-1][j] > dp[i][j-1]:
                dp2[i][j] = dp2[i-1][j]
            else:
                dp2[i][j] = dp2[i][j-1]
print(dp2[NS][NT])

Submission status: Time Limit Exceeded

Solution code:
def LCS_Length(string1, string2):
    len1 = len(string1)
    len2 = len(string2)
    #print(len1, len2)
    count = [[0 for i in range(len2 + 1)] for j in range(len1 + 1)]
    backtrack = [[0 for i in range(len2 + 1)] for j in range(len1 + 1)]
    for i in range(1, len1 + 1):
        for j in range(1, len2 + 1):
            if string1[i - 1] == string2[j - 1]:
                count[i][j] = count[i - 1][j - 1] + 1
                backtrack[i][j] = 45
            elif count[i - 1][j] >= count[i][j - 1]:
                count[i][j] = count[i - 1][j]
                backtrack[i][j] = 90
            else:
                count[i][j] = count[i][j - 1]
                backtrack[i][j] = 180

    return count, backtrack


def Print_LCS(backtrack, string1, i, j):
    if i == 0 or j == 0:
        return
    if backtrack[i][j] == 45:
        Print_LCS(backtrack, string1, i - 1, j - 1)
        print(string1[i - 1], end='')
    elif backtrack[i][j] == 90:
        Print_LCS(backtrack, string1, i - 1, j)
    else:
        Print_LCS(backtrack, string1, i, j - 1)


s = input()
t = input()
count, backtrack = LCS_Length(s, t)
Print_LCS(backtrack, s, len(s), len(t))

Submission status: Time Limit Exceeded

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
# import sys
# sys.setrecursionlimit(10**9)

def resolve():
    s = str(input())
    t = str(input())


    # 文字列S, Tのlongest common subsequenceを返す
    # なお、longest common substringではない
    # （要素同士がとなりあっていなくてもいい）ことに注意！
    def lcs(S, T):
        # 初期化
        dp = [[0] * (len(T) + 1) for j in range(len(S) + 1)]

        # dp[i][j]はS[:i]とT[:j]のlcsの長さを表す
        for i in range(len(S)):
            for j in range(len(T)):
                # その前までの値引き継ぎ
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
                # 望まれたニューカマーが来たら足す
                if S[i] == T[j]:
                    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)

        # If you want to know just the length of the lcs, return dp[i + 1][j + 1].
        # Here we'll try to print the lcs.

        lcs_str = ''
        i, j = len(S)-1, len(T)-1
        while i >= 0 and j >= 0:
            if S[i] == T[j]:
                lcs_str += S[i]
                i -= 1
                j -= 1
            else:
                if dp[i][j+1] > dp[i+1][j]:
                    i -= 1
                else:
                    j -= 1

        return lcs_str[::-1]

    print(lcs(s, t))


resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


class LinkedList:
    def __init__(self, val, pre):
        self.prev = pre
        self.value = val


s = input()
t = input()

info = deque(deque() for _ in range(26))
check = []
for i in range(len(s)):
    info[ord(s[i]) - 97].appendleft(i)
ans = [INF] * (max(len(s), len(t)) + 10)
link = [0] * (max(len(s), len(t)) + 10)
for i in t:
    for l in info[ord(i) - 97]:
        ind = bisect_left(ans, l)
        ans[ind] = l
        a = LinkedList(i, link[ind-1])
        link[ind] = a
num = bisect_left(ans, INF)
ans = deque()
a = link[num-1]
while len(ans) < num:
    ans.appendleft(a.value)
    a = a.prev
print("".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


class LinkedList:
    def __init__(self, val, pre):
        self.prev = pre
        self.value = val


s = input()
t = input()

info = deque(deque() for _ in range(26))
check = []
for i in range(len(s)):
    info[ord(s[i]) - 97].appendleft(i)
ans = [INF] * (max(len(s), len(t)) + 10)
link = [0] * (max(len(s), len(t)) + 10)
for i in t:
    for l in info[ord(i) - 97]:
        ind = bisect_left(ans, l)
        ans[ind] = l
        a = LinkedList(i, link[ind-1])
        link[ind] = a
num = bisect_left(ans, INF)
ans = deque()
a = link[num-1]
while len(ans) < num:
    ans.appendleft(a.value)
    a = a.prev
print("".join(ans))

Submission status: Time Limit Exceeded

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

N = len(S)
M = len(T)
dp = [[0 for _ in range(N+1)] for _ in range(M+1)]

for i in range(1, M+1):
    for j in range(1, N+1):
        if S[j-1]==T[i-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 = M, N
lcs = ""
while i>0 and j>0:
    if T[i-1]==S[j-1]:
        lcs += T[i-1]
        i -= 1
        j -= 1
    else:
        if dp[i-1][j]>dp[i][j-1]:
            i -= 1
        else:
            j -= 1
print(lcs[::-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


class LinkedList:
    def __init__(self, val, pre):
        self.prev = pre
        self.value = val


s = input()
t = input()

info = [deque() for _ in range(26)]
check = []
for i in range(len(s)):
    info[ord(s[i]) - 97].appendleft(i)
ans = [INF] * (max(len(s), len(t)) + 10)
link = [0] * (max(len(s), len(t)) + 10)
for i in t:
    for l in info[ord(i) - 97]:
        ind = bisect_left(ans, l)
        ans[ind] = l
        a = LinkedList(i, link[ind-1])
        link[ind] = a
num = bisect_left(ans, INF)
ans = deque()
a = link[num-1]
while len(ans) < num:
    ans.appendleft(a.value)
    a = a.prev
print("".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

s = input()
t = input()

info = [deque() for _ in range(26)]
check = []
for i in range(len(s)):
    info[ord(s[i]) - 97].appendleft(i)
ans = [INF] * (max(len(s), len(t)) + 10)
link = [[0, 0, 0] for _ in range(max(len(s), len(t)) + 10)]
info2 = deque()
time = 0
for i in t:
    for l in info[ord(i) - 97]:
        ind = bisect_left(ans, l)
        ans[ind] = l
        info2.append([time, link[ind-1][0], i])
        link[ind] = [time, link[ind-1][0], i]
        time += 1
num = bisect_left(ans, INF)
ans = deque()
a = link[num-1]
while len(ans) < num:
    ans.appendleft(a[2])
    a = info2[a[1]]
print("".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque
import copy

input = sys.stdin.readline

s = input()
t = input()

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

for i in range(1, len(s)):
    for l in range(1, len(t)):
        if s[i - 1] == t[l - 1]:
            dp[i][l] = max(max(dp[i - 1][l - 1] + 1, dp[i][l - 1]), dp[i - 1][l])
        else:
            dp[i][l] = max(dp[i][l - 1], dp[i - 1][l])
length = dp[len(s) - 1][len(t) - 1]
if length == 0:
    print("")
else:
    ans = ''
    i = len(s) - 1
    l = len(t) - 1
    while i > 0 and l > 0:
        if dp[i-1][l] == dp[i][l] and i >= 1:
            i -= 1
        elif dp[i][l-1] == dp[i][l] and l >= 1:
            l -= 1
        else:
            ans = s[i - 1] + ans
            i -= 1
            l -= 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# F - LCS
s=input()
t=input()
ns=len(s)
nt=len(t)
dp=[[0]*(nt+1) for i in range(ns+1)]

for i in range(ns):
    for j in range(nt):
        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,j=ns,nt
while i>0 and j>0:
    # (i-1, j) -> (i, j) と更新されていた場合
    if dp[i][j]==dp[i-1][j]:
        i-=1
    #  (i, j-1) -> (i, j) と更新されていた場合
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    #  (i-1, j-1) -> (i, j) と更新されていた場合
    else:
        ans=s[i-1]+ans
        i-=1
        j-=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
S = len(s)
T = len(t)
dp = [[0 for i in range(T+1)] for j in range(S+1)]

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

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

for tc in range(1, len(t) + 1):
    for sc in range(1, len(s) + 1):
        if s[sc - 1] == t[tc - 1]:
            dp[sc][tc] = dp[sc - 1][tc - 1] + 1
            result[sc][tc] = result[sc - 1][tc - 1] + s[sc - 1]
        else:
            if  dp[sc][tc - 1] > dp[sc - 1][tc]:
                dp[sc][tc] = dp[sc][tc - 1]
                result[sc][tc] = result[sc][tc - 1]
            else:
                dp[sc][tc] = dp[sc - 1][tc]
                result[sc][tc] = result[sc - 1][tc]
                
                
print(result[len(s)][len(t)])

Submission status: Time Limit Exceeded

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

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

    dp = [[""] * (tl+1) for i in range(sl+1)]

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

    print(dp[sl][tl])


lcs()

Submission status: Time Limit Exceeded

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

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


def lcs():
    dp = [[""] * (tl+1) for i in range(sl+1)]

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

    print(dp[sl][tl])


lcs()

Submission status: Time Limit Exceeded

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

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

dp = [[""] * (tl+1) for i in range(sl+1)]

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

print(dp[sl][tl])

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

ans = ''
i = ls
j = 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 numpy as np
s = input()
t = input()

dp = np.zeros((len(s) + 1, len(t) + 1), dtype=int)

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

answer = ''
i, j = len(s), len(t)
now = dp[i, j]
while i > 0 and j > 0:
    if dp[i-1, j] == now:
        i -= 1
        continue
    if dp[i, j-1] == now:
        j -= 1
        continue
    answer += s[i-1]
    i -= 1
    j -= 1
    now -= 1

print(answer[::-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
t = input()

dp = np.zeros((len(s) + 1, len(t) + 1))

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

answer = ''
i, j = len(s), len(t)
now = dp[i, j]
while i > 0 and j > 0:
    if dp[i-1, j] == now:
        i -= 1
        continue
    if dp[i, j-1] == now:
        j -= 1
        continue
    answer += s[i-1]
    i -= 1
    j -= 1
    now -= 1

print(answer[::-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):
        char = s[i-1]
        if char == 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])

answer = ''
i, j = len(s), len(t)
now = dp[i][j]
while i > 0 and j > 0:
    if dp[i-1][j] == now:
        i -= 1
        continue
    if dp[i][j-1] == now:
        j -= 1
        continue
    answer += s[i-1]
    i -= 1
    j -= 1
    now -= 1

print(answer[::-1])

Submission status: Time Limit Exceeded

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

dp = {}
for i in range(-1, len_s):
    dp[(i, -1)] = 0
for j in range(-1, len_t):
    dp[(-1, j)] = 0

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

answer = ''
i, j = len_s - 1, len_t - 1
now = dp[(i, j)]
while i > -1 and j > -1:
    if dp[(i-1, j)] == now:
        i -= 1
        continue
    if dp[(i, j-1)] == now:
        j -= 1
        continue
    answer += s[i]
    i -= 1
    j -= 1
    now -= 1

print(answer[::-1])

Submission status: Time Limit Exceeded

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

dp = {}
for i in range(-1, len_s):
    dp[(i, -1)] = 0
for j in range(-1, len_t):
    dp[(-1, j)] = 0

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

answer = ''
i, j = len_s - 1, len_t - 1
while i > -1 and j > -1:
    now = dp[(i, j)]
    if dp[(i-1, j)] == now:
        i -= 1
        continue
    if dp[(i, j-1)] == now:
        j -= 1
        continue
    answer += s[i]
    i -= 1
    j -= 1

print(answer[::-1])

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:
import numpy as np
s = input()
t = input()
n,m = len(s),len(t)
dp = [[0]*(n+1) for i in range(m+1)]

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

v,u = n,m
ans = ""
while u > 0 and v > 0:
    if s[v-1] == t[u-1]:
        ans = s[v-1] + ans
        v -= 1
        u -= 1
    else:
        if dp[u][v] == dp[u][v-1]:
            v -= 1
        else:
            u -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
t = input()
n,m = len(s),len(t)
dp = np.zeros((m+1,n+1), dtype = int)

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

v = n
u = m
ans = ""
while u > 0 and v > 0:
    if s[v-1] == t[u-1]:
        ans += s[v-1]
        v -= 1
        u -= 1
    else:
        if dp[u][v] == dp[u][v-1]:
            v -= 1
        else:
            u -= 1
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
t = input()
n,m = len(s),len(t)
dp = np.zeros((m+1,n+1), dtype = int)

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

v = n
u = m
ans = ""
while u > 0 and v > 0:
    if s[v-1] == t[u-1]:
        ans = s[v-1] + ans
        v -= 1
        u -= 1
    else:
        if dp[u][v] == dp[u][v-1]:
            v -= 1
        else:
            u -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
t = input()
dp = np.zeros((len(t)+1,len(s)+1), dtype = int)

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

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

Submission status: Time Limit Exceeded

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

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

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] = max(DP[i][j]+1, DP[i+1][j+1])
        else:
            DP[i+1][j+1] = max(DP[i+1][j], DP[i+1][j+1])
            DP[i+1][j+1] = max(DP[i][j+1], DP[i+1][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:
from copy import deepcopy
s = ['_']
s.extend(list(input()))
t = ['.']
t.extend(list(input()))
N = len(s)
M = len(t)
DP = [[[0,[]] for j in range(M+1)] for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+1):
        if s[i-1] == t[j-1]:
            DP[i][j] = deepcopy(DP[i-1][j-1])
            DP[i][j][0] += 1
            DP[i][j][1].append(s[i-1])
        else:
            DP[i][j] = deepcopy(DP[i-1][j]) if DP[i-1][j][0] >= DP[i][j-1][0] else deepcopy(DP[i][j-1])
print(*DP[N][M][1],sep="")