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 = list(input())
t = list(input())

Lt = len(t)
Ls = len(s)

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

# 通常のDP
for i in range(1,Lt+1):
  for j in range(1,Ls+1):
    if t[i-1] == s[j-1]: 
      dp[i][j] = max(dp[i-1][j-1]+1, dp[i][j], dp[i][j-1], dp[i-1][j]) #末尾が同じなら+1
    else:
      dp[i][j] = max(dp[i][j], dp[i][j-1], dp[i-1][j]) #同じでないなら特に増えない

# 復元i=Ls, j=Ltから前にたどる；値が同じならそこから遷移したということ
i, j = Lt, Ls
lcs = ''
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:
    lcs = s[j-1] + lcs
    i -= 1
    j -= 1
print(lcs)

Submission status: Time Limit Exceeded

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

Lt = len(t)
Ls = len(s)

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

# 通常のDP
for i in range(1,Lt+1):
  for j in range(1,Ls+1):
    if t[i-1] == s[j-1]: 
      dp[i][j] = max(dp[i-1][j-1]+1, dp[i][j]) #末尾が同じなら+1
    dp[i][j] = max(dp[i][j-1], dp[i][j]) #特に増えない
    dp[i][j] = max(dp[i-1][j], dp[i][j]) #特に増えない

# 復元i=Ls, j=Ltから前にたどる；値が同じならそこから遷移したということ
i, j = Lt, Ls
lcs = ''
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:
    lcs = s[j-1] + lcs
    i -= 1
    j -= 1
print(lcs)

Submission status: Time Limit Exceeded

Solution code:
S=input()
T=input()
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)):
        dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j],dp[i][j]+(S[i]==T[j]))

st=[]
x=len(S)
y=len(T)
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
        st+=S[x]
print("".join(reversed(st)))

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)
    dp = [[0] * (lt+1) for _ in range(ls+1)]

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

    #import numpy as np
    #print(np.array(dp))

    #from collections import deque
    #ans = deque()

    ans = ''
    i, j = ls, lt
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            i -= 1
            j -= 1
            #ans.appendleft(s[i])
            ans = s[i] + ans
    #print(''.join(ans))
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0] * (lt+1) for _ in range(ls+1)]

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

#import numpy as np
#print(np.array(dp))

from collections import deque
ans = deque()

#ans = []
i, j = ls, lt
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        i -= 1
        j -= 1
        ans.appendleft(s[i])
        #ans = s[i] + ans
print(''.join(ans))

#print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0] * (lt+1) for _ in range(ls+1)]

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

#import numpy as np
#print(np.array(dp))

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

Submission status: Time Limit Exceeded

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

dp = [[""]*(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]):
            if (len(dp[i][j])+1>=len(dp[i+1][j]) and len(dp[i][j])+1>=len(dp[i][j+1])):
                dp[i+1][j+1] = dp[i][j]+s[i]
            elif (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]
        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 = [[""]*(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]):
            if (len(dp[i][j])+1>=len(dp[i+1][j]) and len(dp[i][j])+1>=len(dp[i][j+1])):
                dp[i+1][j+1] = dp[i][j]+s[i]
            elif (len(dp[i+1][j])>=len(dp[i][j])+1 and 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]
        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:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    S = input().rstrip()
    T = input().rstrip()
    s = len(S)
    t = len(T)

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

    #復元
    res = ''
    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:
            s -= 1
            t -= 1
            res = S[s] + res
    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
dp = [[-1 for i in range(len(S)+1)] for j in range(len(T)+1)]
sub = [["" for i in range(len(S)+1)] for j in range(len(T)+1)]
for a in range(len(S)+1):
	dp[0][a] = 0
for b in range(len(T)+1):
	dp[b][0] = 0
for p in range(1, len(T)+1):
	for q in range(1, len(S)+1):
		if T[p-1] == S[q-1]:
			dp[p][q] = 1 + dp[p-1][q-1]
			sub[p][q] = sub[p-1][q-1] + T[p-1]
		else:
			if dp[p-1][q] > dp[p][q-1]:
				dp[p][q] = dp[p-1][q]
				sub[p][q] = sub[p-1][q]
			else:
				dp[p][q] = dp[p][q-1]
				sub[p][q] = sub[p][q-1]
print(sub[len(T)][len(S)])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def main():
    s=tuple(input())
    t=tuple(input())
    n=len(s)
    m=len(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:
                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])
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
s=tuple(input())
t=tuple(input())
n=len(s)
m=len(t)
dp=[['' for i in range(m+1)] for j in range(n+1)]
#dps=[[0 for i in range(m+1)] for j in range(n+1)]
for i in range(n):
    for j in range(m):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+s[i]
            #dps[i+1][j+1]=dps[i][j]+1
        else:
            if len(dp[i+1][j])>len(dp[i][j+1]):
                dp[i+1][j+1]=dp[i+1][j]
                #dps[i+1][j+1]=dps[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]
                #dps[i+1][j+1]=dps[i][j+1]
print(dp[n][m])

Submission status: Time Limit Exceeded

Solution code:
def main():
    s=input()
    t=input()
    dp=[[""]*(len(t)+1) for _ in range(len(s)+1)]
    for i in range(1,len(s)+1):
        for j in range(1,len(t)+1):
            if s[i-1]==t[j-1]:
                dp[i][j]=dp[i-1][j-1]+s[i-1]
            else:
                if 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]
                    
    print(dp[len(s)][len(t)])
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
getFirstline = str(input())
getSecondline = str(input())
nfirst = len(getFirstline) 
nsecond = len(getSecondline) 
columns = [0 for _ in range(nfirst + 1)]
dp = [columns[::] for _ in range( nsecond + 1 ) ]

#print(dp)

dicts = {}

for i in range(nfirst + 1):
    curstrs = str(0) + "," + str(i)
    dicts[curstrs] = ""

for i in range(nsecond + 1):
    curstrs = str(i) + "," + str(0)
    dicts[curstrs] = ""


for i in range(nsecond):
    
    for j in range(nfirst):
        ii = i + 1 
        jj = j + 1
        curstrs = str(i) + "," + str(j)
        final = ""
        if getSecondline[i] == getFirstline[j]:
            if curstrs  in dicts:
                final = dicts[curstrs] + str(getSecondline[i])
            else:
                final = str(getSecondline[i])
                
            dp[ii][jj] = dp[ii -1][jj -1] + 1 
            
        else:
            if (dp[ii][jj-1] >= dp[ii-1][jj]):
                curstrs = str(ii) + "," + str(jj -1)
            else:
                curstrs = str(ii - 1) + "," + str(jj)
                
            dp[ii][jj] = max(dp[ii][jj - 1], dp[ii-1][jj])
            
            if curstrs not in dicts:
                final = ""
            else:
                final = dicts[curstrs]
        addcurstrs = str(ii) + "," + str(jj)
        dicts[addcurstrs] = final 
        
# for i in range(nsecond + 1):
#     print(dp[i])
#print(dicts)
finalstring = str(nsecond)+","+ str(nfirst)
#print(finalstring)
print(dicts[finalstring])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

# dp [n+1][m+1]

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

for i in range(n+1):
  dp[i][0] = 0
  
for j in range(m+1):
  dp[0][j] = 0
  
for i in range(1,n+1):
  for j in range(1,m+1):
    if s[i-1] == t[j-1]:
      dp[i][j] = 1 + dp[i-1][j-1]
    else:
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])
   
def path():
    ans=""
    ls=n;lt=m
    while ls>0 and lt>0:
        if dp[ls][lt]==dp[ls-1][lt]:
            ls-=1
        elif dp[ls][lt]==dp[ls][lt-1]:
            lt-=1
        else:
            ans=s[ls-1]+ans
            ls-=1
            lt-=1
 
    print(ans)
    
path()
#print(dp)

Submission status: Time Limit Exceeded

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

str_dp=[[""]*(len(s)+1) for g in range(len(t)+1)]

for i in range(len(s)):
    for g in range(len(t)):
        if s[i]==t[g]:
            str_dp[g+1][i+1]=str_dp[g+1][i+1].join(str_dp[g][i]+s[i])
        else:
            if len(str_dp[g+1][i])>=len(str_dp[g][i+1]):
                str_dp[g+1][i+1]=str_dp[g+1][i]
            else:
                str_dp[g+1][i+1]=str_dp[g][i+1]
            
print(str_dp[g+1][i+1])

Submission status: Time Limit Exceeded

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

for i in range(1,len(dp)):
    for j in range(1,len(dp[0])):
        if T[i - 1] == S[j-1]:
            dp[i ][j ] = "".join([dp[i-1][j-1],S[j-1]])
        else:
            res1 = dp[i - 1][j]
            res2 = dp[i][j - 1]
            l1 = len(res1)
            l2 = len(res2)
            if l1 > l2:
                dp[i ][j] = res1
            else:
                dp[i ][j] = res2
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:

S = input()
T = input()
dp = [[ "" ] * (len(S) + 1 ) for _ in range(len(T) + 1)]

for i in range(1,len(dp)):
    for j in range(1,len(dp[0])):
        if T[i - 1] == S[j-1]:
            dp[i ][j ] = dp[i-1][j-1] + S[j-1]
        else:
            res1 = dp[i - 1][j]
            res2 = dp[i][j - 1]
            l1 = len(res1)
            l2 = len(res2)
            if l1 > l2:
                dp[i ][j] = res1
            else:
                dp[i ][j] = res2
print(dp[-1][-1])

Submission status: Time Limit Exceeded

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

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

dp = []
for i in range(len(s)):
	dp.append([0] * len(t))

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

def find_sequence_dp(s):
	i = len(s) - 1
	j = len(t) - 1

	word = ""
	while i != 0 or j != 0:
		current = dp[i][j]

		if i > 0 and dp[i - 1][j] == current:
			i -= 1

		elif j > 0 and dp[i][j - 1] == current:
			j -= 1

		elif i > 0 and j > 0 and dp[i - 1][j - 1] < current:
			word = s[i] + word
			i -= 1
			j -= 1

		elif j > 0 and dp[i][j - 1] < current:
			word = s[j] + word
			j -= 1

		elif i > 0 and dp[i - 1][j] < current:
			word = s[i] + word
			i -= 1

		else:
			i -= 1
			j -= 1

	if dp[0][0] == 1:
		return s[0] + word
	return word

print(find_sequence_dp(s))

Submission status: Time Limit Exceeded

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

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

dp = []
for i in range(len(s)):
	dp.append([0] * len(t))

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

def find_sequence_dp(s):
	i = len(s) - 1
	j = len(t) - 1
	
	word = ""
	while i != 0 or j != 0:
		current = dp[i][j]

		if i > 0 and dp[i - 1][j] == current:
			i -= 1

		elif j > 0 and dp[i][j - 1] == current:
			j -= 1

		elif i > 0 and j > 0 and dp[i - 1][j - 1] < current:
			word = s[i] + word
			i -= 1
			j -= 1

		elif j > 0 and dp[i][j - 1] < current:
			word = s[j] + word
			j -= 1

		elif i > 0 and dp[i - 1][j] < current:
			word = s[i] + word
			i -= 1

	if dp[0][0] == 1:
		return s[0] + word
	return word

print(find_sequence_dp(s))

Submission status: Time Limit Exceeded

Solution code:
from numpy import zeros

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

table = zeros((ls+1, lt+1))
for ss in range(ls):
    for st in range(lt):
        table[ss+1][st+1] = table[ss][st] + 1 if s[ss] == t[st] else max(table[ss+1][st], table[ss][st+1] )

ans = ""
ss, st = ls, lt
while ss * st != 0:
    if table[ss][st] == table[ss-1][st]:
        ss -= 1
    elif table[ss][st] == table[ss][st-1]:
        st -= 1

    else:
        ss -= 1
        st -= 1
        ans = s[ss] + ans

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#LCS
s=input()
t=input()
dp=[[["",0] for i in range(len(t)+1)] for _ in range(len(s)+1)]
#dp[i][j]＝ｓのi番目の文字までと、tのj番目の文字までみたときに得られる、最大の長さの文字列
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][1]=dp[i-1][j-1][1]+1
            dp[i][j][0]=dp[i-1][j-1][0]+s[i-1]
        else:
            #s[i-1]!=t[j-1]: 二つの文字のsのi番目のものとtのj番目の値が一致しないとき
            if dp[i][j-1][1]>=dp[i-1][j][1]:
                dp[i][j]=dp[i][j-1]
            else:
                dp[i][j]=dp[i-1][j]
print(dp[len(s)][len(t)][0])

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

# DPを逆に辿って復元する
ans = ""
i = len(s)
j = len(t)
while( i>0 and j>0):
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1

print(ans)

Submission status: Time Limit Exceeded

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

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

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

# DPを逆に辿って復元する
ans = ""
i = len(s)
j = len(t)
while( i>=0 and j>=0):
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1

print(ans)

Submission status: Time Limit Exceeded

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

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

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

x = lt
y = ls

while x-1>=0 and y-1>=0:
    if dp[y][x] == dp[y][x-1]:
        x -= 1
    elif dp[y][x] == dp[y-1][x]:
        y -= 1
    else:
        ans = s[y-1] + ans
        x -= 1
        y -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)


def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)

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

    for i, sc in enumerate(s, 1):
        ary0 = dp[i-1]
        ary1 = dp[i]
        for j, tc in enumerate(t, 1):
            if sc == tc:
                ary1[j] = ary0[j-1] + 1
            else:
                ary1[j] = max(ary1[j-1], ary0[j])

    def to_s():
        i = ls
        j = lt
        ans = ""
        while i > 0 and j > 0:
            if dp[i][j] == dp[i - 1][j]:
                i -= 1
                continue
            if dp[i][j] == dp[i][j-1]:
                j -= 1
                continue
            ans = s[i-1] + ans
            i -= 1
            j -= 1

        return ans

    print(to_s())


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)


def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)

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

    for i, sc in enumerate(s):
        for j, tc in enumerate(t):
            if sc == tc:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

    def to_s():
        i = ls
        j = lt
        sb = []
        while i > 0 and j > 0:
            if dp[i][j] == dp[i - 1][j]:
                i -= 1
                continue
            if dp[i][j] == dp[i][j-1]:
                j -= 1
                continue
            sb.append(s[i-1])
            i -= 1
            j -= 1

        sb.reverse()
        return "".join(sb)

    print(to_s())


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)


def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)

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

    dp[0][0]

    for i in range(1, ls+1):
        for j in range(1, lt+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])

    def to_s():
        tary = dp[-1]

        i = ls
        j = lt
        sb = []
        while i > 0 and j > 0:
            if dp[i][j] == dp[i - 1][j]:
                i -= 1
                continue
            if dp[i][j] == dp[i][j-1]:
                j -= 1
                continue
            sb.append(s[i-1])
            i -= 1
            j -= 1

        sb.reverse()
        return "".join(sb)

    print(to_s())


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)


def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)

    def lcs(i, j, memo):
        if i >= ls or j >= lt:
            return ""
        if memo[i][j] is not None:
            return memo[i][j]
        if s[i] == t[j]:
            l = s[i] + lcs(i + 1, j + 1, memo)
        else:
            s1 = lcs(i + 1, j, memo)
            s2 = lcs(i, j + 1, memo)
            l = s1 if len(s1) >= len(s2) else s2
        memo[i][j] = l
        return l

    memo = [[None] * lt for _ in range(ls)]
    print(lcs(0, 0, memo))


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = str(input())
    T = str(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][j + 1], dp[i + 1][j])

    lst = []

    N = i + 1
    M = j + 1
    while (N - 1) >= 0 and (M - 1) >= 0:
        if S[N - 1] == T[M - 1]:
            lst.append(S[N - 1])
            N -= 1
            M -= 1
        else:
            if dp[N][M] == dp[N - 1][M]:
                N -= 1
            else:
                M -= 1

    print (*lst[::-1], sep = '')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
T = str(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][j + 1], dp[i + 1][j])

lst = []

N = i + 1
M = j + 1
while (N - 1) >= 0 and (M - 1) >= 0:
    if S[N - 1] == T[M - 1]:
        lst.append(S[N - 1])
        N -= 1
        M -= 1
    else:
        if dp[N][M] == dp[N - 1][M]:
            N -= 1
        else:
            M -= 1

print (*lst[::-1], sep = '')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)


def main():
    s = input()
    t = input()
    ret = []
    ret = search(s, t, 0, 0, ret)
    print("".join(ret))


def search(s, t, i, j, ret):
    if i >= len(s) or j >= len(t):
        return ret
    if s[i] != t[j]:
        ret1 = search(s, t, i, j+1, ret[:])
        ret2 = search(s, t, i + 1, j, ret)
        return ret1 if len(ret1) > len(ret2) else ret2

    ret.append(s[i])
    return search(s, t, i + 1, j + 1, ret)


main()

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
t = str(input())
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1]==t[j-1]:
            dp[i][j] = dp[i-1][j-1] +1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

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

Submission status: Time Limit Exceeded

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

dp = [ [ "" for i in range(3010)] for j in range(3010) ]

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    #1:初期化
    s = input()
    t = input()
    limit = 7
    dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

    #2:初期値(いらない)

    #3:dp実行部(貰うDP)or(配るDP)
    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])

    #4:出力
    #print(*dp,sep="\n")
    res = ""
    s_len = len(s)
    t_len = len(t)
    while s_len > 0 and t_len > 0:
        if dp[s_len][t_len] == dp[s_len-1][t_len]:
            s_len -= 1
        elif dp[s_len][t_len] == dp[s_len][t_len-1]:
            t_len -= 1
        else:
            res = s[s_len-1] + res
            s_len -= 1
            t_len -= 1
    print(res)
        

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import bisect
from collections import defaultdict
ti = defaultdict(list)

for i, c in enumerate(T):
  ti[c].append(i)

dp = {}
dp[-1] = []

for c in S:
  ndp = {}
  for k, v in dp.items():
    #j = T.find(c, k+1)
    l = bisect.bisect_left(ti[c], k+1)
    if l < len(ti[c]):
      j = ti[c][l]
    else:
      j = -1
    if k not in ndp or (len(v) > len(ndp[k])):
      ndp[k] = v[:]
    if j != -1:
      if j not in ndp or (len(v) + 1 > len(ndp[j])):
        ndp[j] = v[:] + [c]
  dp = ndp

ans = ''
for s in list(map(lambda x: ''.join(x), dp.values())):
  if len(s) > len(ans):
    ans = s
print(ans)

Submission status: Time Limit Exceeded

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

import bisect

dp = {}
dp[-1] = []

for c in S:
  ndp = {}
  for k, v in dp.items():
    j = T.find(c, k+1)
    if k not in ndp or (len(v) > len(ndp[k])):
      ndp[k] = v[:]
    if j != -1:
      if j not in ndp or (len(v) + 1 > len(ndp[j])):
        ndp[j] = v[:] + [c]
  dp = ndp

ans = ''
for s in list(map(lambda x: ''.join(x), dp.values())):
  if len(s) > len(ans):
    ans = s
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
S = len(s)
T = len(t)
dp = [[0 for _ in range(T+1)] for _ in range(S+1)]
for i in range(S):
    for j in range(T):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1])
ans = ''
i = S
j = T
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1
print(ans)

Submission status: Time Limit Exceeded

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

def longest(A):
  ans=A[0]
  for i in A:
    if len(ans)<len(i):
      ans=i
  return ans

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]
    dp[i+1][j+1]=longest([dp[i+1][j+1],dp[i][j+1],dp[i+1][j]])
print(dp[s][t])

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
#dp 0で初期化
#dp[i+1][j+1] sのi文字目までとtのj文字目までの最長部分列の長さ
#もしs[i] == t[j]なら、dp[i][j]に対して1文字増やせる => dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1) ...わかる
#dp[i+1][j+1] = max(dp[i+1][j],dp[i+1][j+1])　　...？
#dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j+1])　　...？
#dp[i+1][j+1]
dp = [[0]*(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+1][j+1],dp[i][j]+1)
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j+1])

#復元
i = len(s)
j = len(t)
res = ""
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:
def resolve():
    s = input()
    t = input()

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

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

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

    
    def remove_s(in_s, del_s):
        for s in del_s:
            idx = in_s.find(s)
            in_s = in_s[idx+1:]
        return in_s

    for i in range(len(s)):
        for j in range(len(t)):
            #print(i, j)
            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[len(s)][len(t)])

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
# 操作しやすいように1文字目を異なる文字で埋める
S = 'S' + input()
T = 'T' + input()

memo = [[''] * len(T) for _ in range(len(S))]

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

print(memo[-1][-1])