Problem:


Score : 100 points

Problem Statement

You are given strings s and t.
Find one longest string that is a subsequence of both s and t.

Notes

A subsequence of a string x is the string obtained by removing zero or more characters from x and concatenating the remaining characters without changing the order.

Constraints

s and t are strings consisting of lowercase English letters.

1 \leq |s|, |t| \leq 3000

Input

Input is given from Standard Input in the following format:

s
t

Output

Print one longest string that is a subsequence of both s and t.
If there are multiple such strings, any of them will be accepted.

Sample Input 1

axyb
abyxb

Sample Output 1

axb

The answer is axb or ayb; either will be accepted.

Sample Input 2

aa
xayaz

Sample Output 2

aa

Sample Input 3

a
z

Sample Output 3

The answer is  (an empty string).

Sample Input 4

abracadabra
avadakedavra

Sample Output 4

aaadara



Sample input:
axyb
abyxb


Sample output:
axb

Submission status: Time Limit Exceeded

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

def Main(s, t):
    ls = len(s)
    lt = len(t)
    dp = [[[] for _ in range(ls+1)] for _ in range(lt+1)]
    for i in range(lt):
        for j in range(ls):
            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]
                
    return "".join(dp[lt][ls])

def main():
    s = input().rstrip('\n')
    t = input().rstrip('\n')
    print(Main(s, t))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
L=[]
for i in s:
	for j in range(len(t)):
		if(t[j]==i):
			L.append([j,i])
for i in range(len(L)-2,-1,-1):
	maxlen=-1
	index1=-1
	for j in range (i+1,len(L)):
		if(L[j][0]>L[i][0] and len(L[j][1])>maxlen):
			maxlen=len(L[j][1])
			index1=j
	if(index1>=0):
		L[i][1]=L[i][1]+L[index1][1]
if(len(L)==0):
	print('')
else:
	print(L[0][1])

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
L=[]
for i in s:
	for j in range(len(t)):
		if(t[j]==i):
			L.append([j,i])
for i in range(len(L)-2,-1,-1):
	maxlen=-1
	index1=-1
	for j in range (i+1,len(L)):
		if(L[j][0]>L[i][0] and len(L[j][1])>maxlen):
			maxlen=len(L[j][1])
			index1=j
	if(index1>=0):
		L[i][1]=L[i][1]+L[index1][1]
if(len(L)==0):
	print('')
else:
	print(L[0][1])

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
L=[]
for i in s:
	for j in range(len(t)):
		if(t[j]==i):
			L.append([j,i])
for i in range(len(L)-2,-1,-1):
	maxlen=0
	maxstr=''
	for j in range (i+1,len(L)):
		if(L[j][0]>L[i][0] and len(L[j][1])>maxlen):
			maxlen=len(L[j][1])
			maxstr=L[j][1]
	L[i][1]=L[i][1]+maxstr
if(len(L)==0):
	print('')
else:
	print(L[0][1])

Submission status: Time Limit Exceeded

Solution code:
def LCS(X, Y):
    for i in range(m+1):
        c[i][0] = 0
    for j in range(n+1):
        c[0][j] = 0
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i] == Y[j]:
                c[i][j] = c[i-1][j-1] + 1
                d[i][j] = d[i-1][j-1] + X[i]
            else:
                if c[i-1][j] >= c[i][j-1]:
                  c[i][j] = c[i-1][j]
                  if c[i][j] > c[i-1][j-1]:
                    d[i][j] = d[i-1][j-1] + Y[j]
                  else:
                    d[i][j] = d[i-1][j-1]
                else: #if c[i-1][j] < c[i][j-1]:
                  c[i][j] = c[i][j-1]
                  d[i][j] = d[i-1][j-1] + X[i]
                
s1 = input()
s2 = input()
m = len(s1)
n = len(s2)
X = [''] + list(s1)
Y = [''] + list(s2)

c = [[None]*(n+1) for i in range(m+1)]
d = [['']*(n+1) for i in range(m+1)] 
   
LCS(X, Y)
#print(c[m][n])
print(d[m][n])

Submission status: Time Limit Exceeded

Solution code:
# EDP F-LCS
import sys
input = sys.stdin.readline


def main():
    S = input()
    T = input()

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

    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if s == t:
                dp[i+1][j+1] = [dp[i][j][0]+1, dp[i][j][1]+s]
            else:
                if dp[i+1][j][0] >= dp[i][j+1][0]:
                    dp[i+1][j+1] = dp[i+1][j]
                else:
                    dp[i+1][j+1] = dp[i][j+1]

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# EDP F-LCS
import sys
input = sys.stdin.readline


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

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

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

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# EDP F-LCS
def main():
    s = input()
    t = input()

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

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

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#F-LCS
def L_d(s1,s2):
    mp=[[0]*(len(s1)+1) for _ in range(len(s2)+1)]
    for n in range(1,len(s2)+1):
        mp[n][0]+=mp[n-1][0]+1
    for m in range(1,len(s1)+1):
        mp[0][m]+=mp[0][m-1]+1

    for i in range(1,len(s2)+1):
        for j in range(1,len(s1)+1):
            mp[i][j]=min(mp[i-1][j]+1,
                        mp[i][j-1]+1,
                        mp[i-1][j-1]+(s1[j-1]!=s2[i-1]))
    return mp[-1][-1]

s=input()
t=input()
i=0
while i<min(len(s),len(t)):
    if s[i]!=t[i]:
        d1=L_d(s[i+1:],t[i:])
        d2=L_d(s[i:],t[i+1:])
        if d1<=d2:
            s=s[:i]+s[i+1:]
        else:
            t=t[:i]+t[i+1:]
    else:
        i+=1
l_min=min(len(s),len(t))
if s[:l_min]==t[:l_min] :
    print(s[:l_min])
else:
    print(" ")

Submission status: Time Limit Exceeded

Solution code:
def lcs(x,y,n,m):
    l=[[0 for i in range(n+1)] for j in range(m+1)]
    c=""
    for i in range(m+1):
        for j in range(n+1):
            if i==0 or j==0:
                l[i][j]=0
            elif y[i-1]==x[j-1]:
                l[i][j]=1+max(l[i-1][j],l[i][j-1])
            else:
                l[i][j]=max(l[i-1][j],l[i][j-1])
    index=l[m][n]
    c=[""]*(index+1)
    i=m
    j=n
    c[index]=""
    while(i>0 and j>0):
        if y[i-1]==x[j-1]:
            c[index-1]=y[i-1]
            index=index-1
            i-=1
            j-=1
        elif l[i-1][j]>l[i][j-1]:
            i-=1
        else:
            j-=1
    print("".join(c))
                



x=str(input())
y=str(input())
n=len(x)
m=len(y)
lcs(x,y,n,m)

Submission status: Time Limit Exceeded

Solution code:
import sys
# input処理を高速化する

# 入力
S = [ord(c) - 97 for c in input()]
T = [ord(c) - 97 for c in input()]
def chmax(a, b):
    if a >= b:
        return a
    else:
        return b

dp = [[0 for i in range(len(T)+1)] for j 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])

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 += chr(S[i-1]+97)
        i -= 1
        j -= 1

print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
# input処理を高速化する
input = sys.stdin.readline
# 入力
S = input()
T = input()
def chmax(a, b):
    if a >= b:
        return a
    else:
        return b

dp = [[0 for i in range(len(T)+1)] for j 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])

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

print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
# input処理を高速化する
input = sys.stdin.readline
# 入力
S = input()
T = input()
def chmax(a, b):
    if a >= b:
        return a
    else:
        return b
def lcs(s, t):
    dp = [[0 for i in range(len(T)+1)] for j 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] = chmax(dp[i+1][j+1], dp[i][j] + 1)
            dp[i+1][j+1] = chmax(dp[i+1][j+1], dp[i+1][j])
            dp[i+1][j+1] = chmax(dp[i+1][j+1], dp[i][j+1])
    ans = ''
    i = len(S)
    j = len(T)
    while (i>0  and j>0):
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans += s[i-1] 
            i -= 1
            j -= 1
    
    print(ans[::-1])
        
lcs(S, T)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
s_len = len(s)
t_len = len(t)
grid_len = [[0 for j in range(t_len+1)] for i in range(s_len+1)]
grid_str = [[[] for j in range(t_len+1)] for i in range(s_len+1)]
for i in range(s_len):
    for j in range(t_len):
        if s[i] == t[j]:
            if grid_len[i][j] + 1 > grid_len[i+1][j+1]:
                grid_len[i+1][j+1] = grid_len[i][j] + 1
                grid_str[i+1][j+1] = grid_str[i][j] + [s[i]]
        if grid_len[i][j] > grid_len[i+1][j]:
            grid_len[i+1][j] = grid_len[i][j]
            grid_str[i+1][j] = grid_str[i][j]
        if grid_len[i][j] > grid_len[i][j+1]:
            grid_len[i][j+1] = grid_len[i][j]
            grid_str[i][j+1] = grid_str[i][j]

ans_len = 0
ans_str = ''
for i in range(s_len+1):
    for j in range(t_len+1):
        if grid_len[i][j] > ans_len:
            ans_len = grid_len[i][j]
            ans_str = grid_str[i][j]
print(''.join(ans_str))

Submission status: Time Limit Exceeded

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

s = input()
t = input()

#dp[i][j] => s[i], t[j]までの最長部分文字列


dp = [[""] * (len(t) + 1) for j in range(len(s) + 1)]
for j in range(len(t)):
    for i in range(len(s)):
        if s[i] == t[j]:
            v =  [dp[i][j] + s[i], dp[i + 1][j],dp[i][j + 1]]
            v = sorted(v, key = lambda x:len(x))
            dp[i + 1][j + 1] = v[-1]
        else:
            v = [dp[i + 1][j],dp[i][j + 1]]
            v = sorted(v, key = lambda x:len(x))
            dp[i + 1][j + 1] = v[-1]
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
#dp[i][j] => s[i], t[j]までの最長部分文字列


dp = [["" for i in range(len(t) + 1)] for j in range(len(s) + 1)]
for j in range(len(t)):
    for i in range(len(s)):
        if s[i] == t[j]:
            v =  [dp[i][j] + s[i], dp[i + 1][j],dp[i][j + 1]]
            v = sorted(v, key = lambda x:len(x))
            dp[i + 1][j + 1] = v[-1]
        else:
            v =  [ dp[i + 1][j],dp[i][j + 1]]
            v = sorted(v, key = lambda x:len(x))
            dp[i + 1][j + 1] = v[-1]
print(dp[-1][-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(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])

ret_rev = []

i, j = len(s) - 1, len(t) - 1
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        ret_rev.append(s[i])
        i, j = i - 1, j - 1
    elif dp[i + 1][j + 1] == dp[i + 1][j]:
        i, j = i, j - 1
    else: # i.e. dp[i + 1][j + 1] == dp[i][j + 1]
        i, j = i - 1, j

ret = "".join(ret_rev[::-1])

print(ret)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import string
import sys
from itertools import chain, dropwhile, takewhile

INF = float("inf")


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    s, t = reads(2)
    dp = arr(len(s) + 1, len(t) + 1)
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1])

    ans = []
    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
        else:
            i -= 1
            j -= 1
            ans.append(s[i])

    print("".join(ans[::-1]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
s1 = list(input())
s2 = list(input())

dp = [[0 for _ in range(len(s2)+1)] for _ in range(len(s1)+1)]

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

if dp[-1][-1] == 0:
	print("")
else:
    res = []
    i = len(s1) 
    j = len(s2)
    while len(res) < dp[-1][-1]:
        if s1[i-1] == s2[j-1]:
            res.append(s1[i-1])
            i -= 1
            j -= 1
        else:
            if dp[i-1][j] > dp[i][j-1]:
                i -= 1
            else:
                j -= 1

    print("".join(reversed(res)))

Submission status: Time Limit Exceeded

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

ans = ''
#dp[i][j]:sをi文字目、tをj文字目まで見たときの最長部分列
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:
      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)
print(dp[len(s)][len(t)])

Submission status: Time Limit Exceeded

Solution code:
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

s = input()
t = input()
n = len(s)
m = len(t)

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

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

ans = ""
x = dp[-1][-1]
for i in range(n,-1,-1):
    for j in range(m,-1,-1):
        if dp[i][j]==x:
            if (dp[i-1][j]==x-1) and (dp[i][j-1]==x-1):
                ans = s[i-1]+ans
                x-=1
                break
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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


def solve(s: str, t: str):
    N = len(s)
    W = len(t)
    dp = [[''] * (W+1) for i in range(N+1)]

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

    print(dp[N][W])

    return


# Generated by 1.1.4 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:
def lcs(s,t):
    m,n = len(s),len(t)
    a = [[0 for j in range(n+1)]for i in range(m+1)]
    k,p = "",0
    for i in range(m+1):
        for j in range(n+1):
            if i==0 or j==0:
                a[i][j]=0
            elif s[i-1]==t[j-1]:
                a[i][j]=a[i-1][j-1]+1
            else:
                a[i][j] = max(a[i-1][j],a[i][j-1])
    i,j = m,n
    while i>0 and j>0:
        if s[i-1]==t[j-1]:
            k+=s[i-1]
            i-=1
            j-=1
        elif a[i-1][j]>a[i][j-1]:
            i-=1
        else:
            j-=1
    return k[::-1]
s = input()
t = input()
k = lcs(s,t)
print(k)

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
  S=list(sys.stdin.readline())[:-1]
  T=list(sys.stdin.readline())[:-1]
  lS=len(S)
  lT=len(T)
  ans=[[[] for _ in range(lS)] for _ in range(lT)]
  for iT in range(lT):
    for iS in range(lS):
      if S[iS]==T[iT]:
        if iS-1>=0 and iT-1>=0:
          ans[iT][iS].extend(ans[iT-1][iS-1])
        ans[iT][iS].append(S[iS])
      else:
        if iS-1>=0 and (iT-1<0 or len(ans[iT][iS-1])>=len(ans[iT-1][iS])):
          ans[iT][iS].extend(ans[iT][iS-1])
        elif iT-1>=0 and (iS-1<0 or len(ans[iT-1][iS])>=len(ans[iT][iS-1])):
          ans[iT][iS].extend(ans[iT-1][iS])
  print(*ans[lT-1][lS-1],sep='')

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()

lA = len(a)
lB = len(b)

dp = [['']*(lA+1) for i in range(lB+1)]

for i in range(1,lB+1):
    this = b[i-1]
    for j in range(1,lA+1):
        if this==a[j-1]:
            dp[i][j] = dp[i-1][j-1]+this
        else:
            x,y = dp[i-1][j],dp[i][j-1]
            dp[i][j] = (x if len(x)>len(y) else y)

ans = dp[-1][-1]   
print(' ' if ans=='' else ans)

Submission status: Time Limit Exceeded

Solution code:
S=input()
T=input()
lS=len(S)
lT=len(T)
ans=[[""]*lS for _ in range(lT)]
for iT in range(lT):
  for iS in range(lS):
    if S[iS]==T[iT]:
      if iS-1>=0 and iT-1>=0:
        ans[iT][iS]=ans[iT-1][iS-1]+S[iS]
      else:
        ans[iT][iS]=S[iS]
    else:
      if iS-1>=0 and (iT-1<0 or len(ans[iT][iS-1])>=len(ans[iT-1][iS])):
        ans[iT][iS]=ans[iT][iS-1]
      elif iT-1>=0 and (iS-1<0 or len(ans[iT-1][iS])>=len(ans[iT][iS-1])):
        ans[iT][iS]=ans[iT-1][iS]
print(ans[lT-1][lS-1])

Submission status: Time Limit Exceeded

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

def lcs(X , Y): 
    m = len(X) 
    n = len(Y) 
  
    L = [[None]*(n+1) for i in range(m+1)] 
    res = [['']*(n+1) for i in range(m+1)]
    for i in range(m+1): 
        for j in range(n+1): 
            if i == 0 or j == 0 : 
                L[i][j] = 0
                res[i][j] = ''
            elif X[i-1] == Y[j-1]: 
                L[i][j] = L[i-1][j-1]+1
                res[i][j] = res[i-1][j-1]+X[i-1]
            else: 
                L[i][j] = max(L[i-1][j] , L[i][j-1]) 
                if L[i-1][j]>L[i][j-1]:
                    res[i][j] = res[i-1][j]
                else:
                    res[i][j] = res[i][j-1]
  
    return L[m][n], res[m][n]


l1 = len(s)
l2 = len(t)
c, r = lcs(s,t)
print(r)

Submission status: Time Limit Exceeded

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

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

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

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

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:
"""
https://qiita.com/drken/items/03c7db44ccd27820ea0d


"""
def main():
        
    S = input()
    T = input()

    """
    dp[i+1]][j+1]
    Sのi番目とtのｊ番目まで見たときの共通する部分列の最大長さ
    """
    dp = [[0 for _ in range(len(T)+1)] for _ in range(len(S)+1)]

    prev = {}
    # 部分列の最大長さを求める
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if s == t:
                #i番目とｊ番目が同じなら、dp[i+1][j+1]はそれまでの最大長さ＋１
                dp[i+1][j+1] = dp[i][j] + 1
                prev[(i+1, j+1)] = (i,j)
            else:
                #異なる場合はdp[i][j]かd[i+1][j]かdp[i][j+1]のどれかだけども、後者ふたつがi,jより小さいことはないから後ろ二つの大きいほうを採用
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
                prev[(i+1, j+1)] = (i+1,j) if dp[i+1][j] >= dp[i][j+1] else (i,j+1)

    i, j = len(S), len(T)

    substr = ""
    while i != 0 and j != 0:
        if S[i-1] == T[j-1]:
            substr +=S[i-1] 
        i,j = prev[(i,j)]

    print(substr[::-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
"""
https://qiita.com/drken/items/03c7db44ccd27820ea0d


"""
def main():
        
    S = input()
    T = input()

    """
    dp[i+1]][j+1]
    Sのi番目とtのｊ番目まで見たときの共通する部分列の最大長さ
    """
    dp = [[0 for _ in range(len(T)+1)] for _ in range(len(S)+1)]

    next = {}
    prev = {}
    # 部分列の最大長さを求める
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if s == t:
                #i番目とｊ番目が同じなら、dp[i+1][j+1]はそれまでの最大長さ＋１
                dp[i+1][j+1] = dp[i][j] + 1
                prev[(i+1, j+1)] = (i,j)
            else:
                #異なる場合はdp[i][j]かd[i+1][j]かdp[i][j+1]のどれかだけども、後者ふたつがi,jより小さいことはないから後ろ二つの大きいほうを採用
                if dp[i+1][j] >= dp[i][j+1]:
                    dp[i+1][j+1] = dp[i+1][j]
                    prev[(i+1, j+1)] = (i+1,j)
                else:
                    dp[i+1][j+1] = dp[i][j+1]
                    prev[(i+1, j+1)] = (i,j+1)

    i, j = len(S), len(T)

    substr = ""
    while i != 0 and j != 0:
        if S[i-1] == T[j-1]:
            substr +=S[i-1] 
        i,j = prev[(i,j)]

    print(substr[::-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
"""
https://qiita.com/drken/items/03c7db44ccd27820ea0d


"""

S = input()
T = input()

"""
dp[i+1]][j+1]
Sのi番目とtのｊ番目まで見たときの共通する部分列の最大長さ
"""
dp = [[0 for _ in range(len(T)+1)] for _ in range(len(S)+1)]

next = {}
prev = {}
# 部分列の最大長さを求める
for i, s in enumerate(S):
    for j, t in enumerate(T):
        if s == t:
            #i番目とｊ番目が同じなら、dp[i+1][j+1]はそれまでの最大長さ＋１
            dp[i+1][j+1] = dp[i][j] + 1
            prev[(i+1, j+1)] = (i,j)
        else:
            #異なる場合はdp[i][j]かd[i+1][j]かdp[i][j+1]のどれかだけども、後者ふたつがi,jより小さいことはないから後ろ二つの大きいほうを採用
            if dp[i+1][j] >= dp[i][j+1]:
                dp[i+1][j+1] = dp[i+1][j]
                prev[(i+1, j+1)] = (i+1,j)
            else:
                dp[i+1][j+1] = dp[i][j+1]
                prev[(i+1, j+1)] = (i,j+1)

i, j = len(S), len(T)

substr = ""
while i != 0 and j != 0:
    if S[i-1] == T[j-1]:
        substr +=S[i-1] 
    i,j = prev[(i,j)]

print(substr[::-1])

Submission status: Time Limit Exceeded

Solution code:

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

dp_list = [ [ ("",0) for i in range(ls+1) ] for j in range(lt+1) ]

for i in range(lt):
    for j in range(ls):
        if t[i] == s[j]:
            a = dp_list[i][j][1] + 1 
            b = dp_list[i+1][j][1]
            c = dp_list[i][j+1][1]
            p = [a,b,c].index(max(a,b,c))
            if p == 0:
                dp_list[i+1][j+1] = ( dp_list[i][j][0] + s[j] , a) 
            elif p == 1:
                dp_list[i+1][j+1] = dp_list[i+1][j]
            elif p == 2:
                dp_list[i+1][j+1] = dp_list[i][j+1]
        else:
            a = dp_list[i][j][1] 
            b = dp_list[i+1][j][1]
            c = dp_list[i][j+1][1]
            p = [a,b,c].index(max(a,b,c))
            if p == 0:
                dp_list[i+1][j+1] = dp_list[i][j]
            elif p == 1:
                dp_list[i+1][j+1] = dp_list[i+1][j]
            elif p == 2:
                dp_list[i+1][j+1] = dp_list[i][j+1]            
print(dp_list[-1][-1][0])

Submission status: Time Limit Exceeded

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

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

for i in range(lt):
    for j in range(ls):
        if t[i] == s[j]:
            a = "".join([dp_list[i][j], t[i]])
            b = dp_list[i+1][j]
            c = dp_list[i][j+1]
            p = list(map(len,[a,b,c])).index(max(map(len,[a,b,c])))
            
            dp_list[i+1][j+1] = [a,b,c][p]
        else:
            a = dp_list[i][j]
            b = dp_list[i+1][j]
            c = dp_list[i][j+1]
            p = list(map(len,[a,b,c])).index(max(map(len,[a,b,c])))
            
            dp_list[i+1][j+1] = [a,b,c][p]

print(dp_list[-1][-1])

Submission status: Time Limit Exceeded

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

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

for i in range(lt):
    for j in range(ls):
        if t[i] == s[j]:
            a = dp_list[i][j] + t[i]
            b = dp_list[i+1][j]
            c = dp_list[i][j+1]
            p = list(map(len,[a,b,c])).index(max(map(len,[a,b,c])))
            
            dp_list[i+1][j+1] = [a,b,c][p]
        else:
            a = dp_list[i][j]
            b = dp_list[i+1][j]
            c = dp_list[i][j+1]
            p = list(map(len,[a,b,c])).index(max(map(len,[a,b,c])))
            
            dp_list[i+1][j+1] = [a,b,c][p]

print(dp_list[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
s = sys.stdin.readline().rstrip()
t = sys.stdin.readline().rstrip()

sn = len(s)
tn = len(t)

dp =[[0 for _ in range(tn+1)] for _ in range(sn+1)]

for i in range(sn):
    for j in range(tn):
        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)

L =[]
while sn>0 and tn>0:
    if dp[sn][tn] == dp[sn-1][tn]: #縦優先
        sn-=1
    elif dp[sn][tn] == dp[sn][tn-1]:
        tn-=1
    elif dp[sn][tn] == dp[sn-1][tn-1]+1:
        L.append(s[sn-1])
        sn-=1
        tn-=1
        
print(''.join(L[::-1]))

Submission status: Time Limit Exceeded

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

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

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

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  ans = []
  ans_append = ans.append
  s = input()
  t = input()
  a = len(s)
  b = len(t)
  dp = [[0]*(b+1) for _ in range(a+1)]
  prev_w = [[None]*(b+1) for _ in range(a+1)]
  for i in range(a):
    for j in range(b):
      if s[i]==t[j]:
        if dp[i][j]+1>dp[i+1][j+1]:
          dp[i+1][j+1] = dp[i][j]+1
          prev_w[i+1][j+1] = [i,j]
      else:
        if dp[i+1][j]>dp[i][j+1]:
          dp[i+1][j+1]=dp[i+1][j]
          prev_w[i+1][j+1] = (i+1,j)
        else:
          dp[i+1][j+1]=dp[i][j+1]
          prev_w[i+1][j+1] = (i,j+1)
  while a!=0 and b !=0:
    l = dp[a][b]
    a,b=prev_w[a][b]
    if l>dp[a][b]:
      ans_append(s[a])
  ans ="".join(ans)
  ans =ans[::-1]
  print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  ans = []
  ans_append = ans.append
  s = input()
  t = input()
  a = len(s)
  b = len(t)
  dp = [[0]*(b+1) for _ in range(a+1)]
  prev_w = [[0]*(b+1) for _ in range(a+1)]
  for i in range(a):
    for j in range(b):
      if s[i]==t[j]:
        if dp[i][j]+1>dp[i+1][j+1]:
          dp[i+1][j+1] = dp[i][j]+1
          prev_w[i+1][j+1] = [i,j]
      else:
        if dp[i+1][j]>dp[i][j+1]:
          dp[i+1][j+1]=dp[i+1][j]
          prev_w[i+1][j+1] = (i+1,j)
        else:
          dp[i+1][j+1]=dp[i][j+1]
          prev_w[i+1][j+1] = (i,j+1)
  #print(dp[a][b])
  #print(prev_w[1][3])
  while a!=0 and b !=0:
    l = dp[a][b]
    a,b=prev_w[a][b]
    if l>dp[a][b]:
      ans_append(s[a])
  ans ="".join(ans)
  ans =ans[::-1]
  print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
  s = input()
  t = input()
  a = len(s)
  b = len(t)
  dp = [[0]*(b+1) for _ in range(a+1)]
  prev_w = [[0]*(b+1) for _ in range(a+1)]
  for i in range(a):
    for j in range(b):
      if s[i]==t[j]:
        if dp[i][j]+1>dp[i+1][j+1]:
          dp[i+1][j+1] = dp[i][j]+1
          prev_w[i+1][j+1] = [i,j]
      else:
        if dp[i+1][j]>dp[i][j+1]:
          dp[i+1][j+1]=dp[i+1][j]
          prev_w[i+1][j+1] = (i+1,j)
        else:
          dp[i+1][j+1]=dp[i][j+1]
          prev_w[i+1][j+1] = (i,j+1)
  #print(dp[a][b])
  #print(prev_w[1][3])
  ans = []
  while a!=0 and b !=0:
    l = dp[a][b]
    a,b=prev_w[a][b]
    if l>dp[a][b]:
      ans.append(s[a])
  ans ="".join(ans)
  ans =ans[::-1]
  print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
  s = input()
  t = input()
  a = len(s)
  b = len(t)
  dp = [[0]*(b+1) for _ in range(a+1)]
  prev_w = [[0]*(b+1) for _ in range(a+1)]
  for i in range(a):
    for j in range(b):
      if s[i]==t[j]:
        if dp[i][j]+1>dp[i+1][j+1]:
          dp[i+1][j+1] = dp[i][j]+1
          prev_w[i+1][j+1] = [i,j]
      else:
        if dp[i+1][j]>dp[i][j+1]:
          dp[i+1][j+1]=dp[i+1][j]
          prev_w[i+1][j+1] = (i+1,j)
        else:
          dp[i+1][j+1]=dp[i][j+1]
          prev_w[i+1][j+1] = (i,j+1)
  #print(dp[a][b])
  #print(prev_w[1][3])
  ans = ''
  while a!=0 and b !=0:
    l = dp[a][b]
    a,b=prev_w[a][b]
    if l>dp[a][b]:
      ans =s[a]+ans
  print(ans)
if __name__ == '__main__':
    main()