Problem:


Score : 100 points

Problem Statement

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

Notes

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

Constraints

s and t are strings consisting of lowercase English letters.

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

Input

Input is given from Standard Input in the following format:

s
t

Output

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

Sample Input 1

axyb
abyxb

Sample Output 1

axb

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

Sample Input 2

aa
xayaz

Sample Output 2

aa

Sample Input 3

a
z

Sample Output 3

The answer is  (an empty string).

Sample Input 4

abracadabra
avadakedavra

Sample Output 4

aaadara



Sample input:
axyb
abyxb


Sample output:
axb

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s, t = input(), input()
n, m = len(s), len(t)
dp = np.zeros([n + 1, m + 1], dtype=int)

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

res = ''
while n or m:
    if n and m and s[n - 1] == t[m - 1] and dp[n][m] == dp[n - 1][m - 1] + 1:
        n -= 1
        m -= 1
        res += s[n]
    elif n and dp[n][m] == dp[n - 1][m]:
        n -= 1
    else:
        m -= 1

res = ''.join(reversed(res))
print(res)

Submission status: Time Limit Exceeded

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

ans = [[''] * len(t)] * len(s)

for i, a in enumerate(s):
    for j, b in enumerate(t):
        if i == 0 and a == b:
            ans[i][j] = a
        elif i == 0:
            ans[i][j] = ''
        elif j == 0 and a == b:
            ans[i][j] = a
        elif j == 0:
            ans[i][j] = max(ans[i-1][j], '', key=len)
        elif a == b:
            ans[i][j] = ans[i-1][j-1] + a
        else:
            ans[i][j] = max(ans[i-1][j], ans[i][j-1], key=len)
            
print(ans[-1][-1])

Submission status: Time Limit Exceeded

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

ans = [[''] * (len(t)+1)] * (len(s)+1)

for i, a in enumerate(s):
    for j, b in enumerate(t):
        if a == b:
            ans[i+1][j+1] = ans[i][j] + a
        else:
            ans[i+1][j+1] = max(ans[i][j+1], ans[i+1][j], key=len)
            
print(ans[-1][-1])

Submission status: Time Limit Exceeded

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

def mymax(a,b):
	if a > b:
		return a
	else:
		return b
	
dp = [[0]*(len(s)+1) for i in range(len(t)+1)]

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

i = len(t)
j = len(s)
ans = []
while i>0 and j>0:
	if dp[i][j] > dp[i-1][j-1] and dp[i][j] > dp[i-1][j] and dp[i][j] > dp[i][j-1]:
		ans.append(s[j-1])
		i-=1
		j-=1
	elif dp[i][j] == dp[i][j-1]:
		j-=1
	elif dp[i][j] == dp[i-1][j]:
		i-=1
ans = ans[::-1]		
print("".join(ans))

Submission status: Time Limit Exceeded

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

ans = [[''] * (len(t)+1)] * (len(s)+1)

for i, a in enumerate(s):
    for j, b in enumerate(t):
        if a == b:
            ans[i+1][j+1] = ans[i][j] + a
        else:
            if len(ans[i][j+1]) >= len(ans[i+1][j]):
                ans[i+1][j+1] = ans[i][j+1]
            else:
                ans[i+1][j+1] = ans[i+1][j]
            
print(ans[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


def main():
    s = list(input())
    n = len(s)
    t = list(input())
    m = len(t)
    # LCSの長さを状態として持つ
    dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

    # See:
    # https://qiita.com/drken/items/03c7db44ccd27820ea0d
    # LCSの求め方は蟻本のpp.56-57も参照
    # △文字列s, tを二次元配列の形で扱う
    for i in range(n):
        for j in range(m):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

    ans = ''
    i = n
    j = m

    # △復元
    # dp tableの値を見てどこから更新されたかを特定
    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)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input().strip()
t = input().strip()
n = len(s)
m = len(t)
dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
A = [[[(-1,-1),""] for _ in range(m+1)] for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        if s[i-1]==t[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
            A[i][j] = [(i-1,j-1),s[i-1]]
        else:
            dp[i][j] = max(dp[i][j-1],dp[i-1][j])
            if dp[i][j]==dp[i][j-1]:
                A[i][j] = [(i,j-1),""]
            else:
                A[i][j] = [(i-1,j),""]
a = ""
x = (n,m)
while True:
    a = A[x[0]][x[1]][1]+a
    x = A[x[0]][x[1]][0]
    if x[0]<0:break
print(a)

Submission status: Time Limit Exceeded

Solution code:
s = input().strip()
t = input().strip()
n = len(s)
m = len(t)
dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
A = [["" for _ in range(m+1)] for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        if s[i-1]==t[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
            A[i][j] = A[i-1][j-1]+s[i-1]
        else:
            dp[i][j] = max(dp[i][j-1],dp[i-1][j])
            if dp[i][j]==dp[i][j-1]:
                A[i][j] = A[i][j-1]
            else:
                A[i][j] = A[i-1][j]
print(A[n][m])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    t=sys.stdin.readline()
    s=sys.stdin.readline()
    ls=len(s)
    lt=len(t)

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

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    t=input()
    s=input()
    ls=len(s)
    lt=len(t)

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

#dp[i][j]=sのi-1文字目までとtのj-1文字目までのLCS
main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s1 = input()
s2 = input()

dp = [['' for j in range(len(s2))] for i in range(len(s1))]

idx = s2.find(s1[0])
if idx != -1:
    for j in range(idx, len(s2)):
        dp[0][j] =  s1[0]
idx = s1.find(s2[0])
if idx != -1:
    for j in range(idx, len(s1)):
        dp[j][0] =  s2[0]
for i in range(1, len(s1)):
  for j in range(1, len(s2)):
    if s1[i] == s2[j]:
      dp[i][j] = dp[i-1][j-1] + s1[i]
    else:
      dp[i][j] = dp[i-1][j] if len(dp[i-1][j])>len(dp[i][j-1]) else dp[i][j-1]
print(dp[len(s1)-1][len(s2)-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s1 = input()
s2 = input()

dp = [['' for j in range(len(s2))] for i in range(len(s1))]

idx = s2.find(s1[0])
if idx != -1:
    for j in range(idx, len(s2)):
        dp[0][j] =  s1[0]
for i in range(1, len(s1)):
  for j in range(len(s2)):
    idx = s2[:j+1].rfind(s1[i])
    tmp1 = ''
    if idx != -1:
      if idx > 0:
        tmp1 = dp[i-1][idx-1] + s1[i]
      else:
        tmp1 = s1[i]
    tmp2 = dp[i-1][j]
    dp[i][j] = tmp1 if len(tmp1) > len(tmp2) else tmp2
print(dp[len(s1)-1][len(s2)-1])

Submission status: Time Limit Exceeded

Solution code:
def lcs(str1, str2):
    str1_len = len(str1)
    str2_len = len(str2)

    result = [[0]*(str1_len + 1) for i in range(str2_len + 1)]

    for i in range(str1_len + 1):
        for j in range(str2_len + 1):
            if i == 0 or j == 0:
                result[j][i] = 0
            elif str1[i - 1] == str2[j - 1]:
                result[j][i] = 1 + result[j - 1][i - 1]
            else:
                result[j][i] = max(result[j - 1][i], result[j][i - 1])

    return result


def print_lcs(str1, str2):
    table = lcs(str1, str2)

    common = ''

    i = len(str1)
    j = len(str2)

    while i > 0 and j > 0:
        if str1[i - 1] == str2[j - 1]:
            common = str1[i - 1] + common
            j -= 1
            i -= 1
        elif table[j - 1][i] > table[j][i - 1]:
            j -= 1
        else:
            i -= 1

    return common


str1 = input()
str2 = input()

print(print_lcs(str1, str2))

Submission status: Time Limit Exceeded

Solution code:
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 (dps[i+1][j])>(dps[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=list(input())
t=list(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])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
n=len(s)
m=len(t)
dp=[["" for _ in range(n+1)] for _ in range(m+1)]
for i in range(m):
    for j in range(n):
        if t[i] == s[j]:
            dp[i+1][j+1] = dp[i][j] + t[i]
        else:
            if len(dp[i+1][j]) >= len(dp[i][j+1]):
                dp[i+1][j+1] = dp[i+1][j]
            else:
                dp[i+1][j+1] = dp[i][j+1]
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

"""
20191121
"""


def main():
    INF = 10**9

    s = "X" + input()
    t = "X" + input()
    N = len(s)
    M = len(t)

    # initialize
    dp = [[{"cost": INF, "prev": None} for _ in range(M)] for _ in range(N)]
    dp[0][0] = {"cost": 0, "prev": None}
    for m in range(1, M):
        dp[0][m] = {"cost": m, "prev": [0, m-1]}
    for n in range(1, N):
        dp[n][0] = {"cost": n, "prev": [n-1, 0]}

    for n in range(1, N):
        for m in range(1, M):
            if s[n] == t[m]:
                dp[n][m] = {"cost": dp[n-1][m-1]["cost"], "prev": [n-1, m-1]}
            elif dp[n-1][m]["cost"] > dp[n][m-1]["cost"]:
                dp[n][m] = {"cost": dp[n][m-1]["cost"]+1, "prev": [n, m-1]}
            else:
                dp[n][m] = {"cost": dp[n-1][m]["cost"]+1, "prev": [n-1, m]}

    n, m = N-1, M-1
    ans_rev = ""
    while dp[n][m]["prev"] is not None:
        if s[n] == t[m]:
            ans_rev += s[n]
        n, m = dp[n][m]["prev"]

    ans = ans_rev[::-1]

    return ans


if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:

s = input()
t = input()

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

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

Submission status: Time Limit Exceeded

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

s_len = len(s)
t_len = len(t)

dp = [[0]*(t_len+1) for t_item in range(0, s_len+1)]


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

N=dp[s_len][t_len]
y=s_len
x=t_len
H=[]
while N>0:
    if dp[y][x-1]-dp[y][x]==0:
        x-=1
        continue
    if dp[y-1][x]-dp[y][x]==0:
        y-=1
        continue
    H.append(t[x-1])
    N-=1
    y-=1
    x-=1
print(''.join(H[::-1]))

Submission status: Time Limit Exceeded

Solution code:
s = list(" "+input())
t = list(" "+input())
record = [[[0,""] for _ in range(len(t))] for _ in range(len(s))]
for i in range(1,len(s)):
    for j in range(1,len(t)):
        if t[j] == s[i]:
            record[i][j] = [record[i-1][j-1][0] + 1, record[i-1][j-1][1]+t[j]]
        else:
            record[i][j] = record[i][j-1] if record[i-1][j][0] < record[i][j-1][0] else record[i-1][j]
print(record[len(s)-1][len(t)-1][1])

Submission status: Time Limit Exceeded

Solution code:
s = " "+input()
t = " "+input()
record = [[[0,""] for _ in range(len(t))] for _ in range(len(s))]
for i in range(1,len(s)):
    for j in range(1,len(t)):
        if t[j] == s[i]:
            record[i][j] = [record[i-1][j-1][0] + 1, record[i-1][j-1][1]+t[j]]
        else:
            record[i][j] = record[i][j-1] if record[i-1][j][0] < record[i][j-1][0] else record[i-1][j]
print(record[len(s)-1][len(t)-1][1])

Submission status: Time Limit Exceeded

Solution code:
def main(X, Y):
    M = len(Y)
    dp = [0]*(M+1)
    dp_s = [""]*(M+1)
    for i, x in enumerate(X):
        dp_pre = dp[:]
        dp_s_pre = dp_s[:]
        for j, y in enumerate(Y):
            if x == y:
                dp[j+1] = dp_pre[j] + 1
                dp_s[j+1] = dp_s_pre[j] + x
            elif dp[j+1] < dp[j]:
                dp[j+1] = dp[j]
                dp_s[j+1] = dp_s[j]
    return print(dp_s[M])


if __name__ == "__main__":
    X = input()
    Y = input()
    main(X, Y)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
t = list(input())
s_l = len(s)
t_l = len(t)
dp = []
for i in range(s_l+1):
    dp.append(["" for j in range(t_l+1)])

for i in range(s_l):
    for j in range(t_l):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + s[i]
        else:
            if len(list(dp[i+1][j])) > len(list(dp[i][j+1])):
                dp[i+1][j+1] = dp[i+1][j]
            else:
                dp[i+1][j+1] = dp[i][j+1]
print(dp[s_l][t_l])

Submission status: Time Limit Exceeded

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

import numpy as np
dp=np.zeros((len(S)+1,len(T)+1),dtype=int)
dp[0][0]=0

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

Submission status: Time Limit Exceeded

Solution code:
def lcsLength(s, t):
    n = len(s) + 1
    m = len(t) + 1
    c = [[-1] * (m) for x in [-1] * (n)]
    direction = [[-1] * (m) for x in [-1] * (n)]
    for i in range(n):
        c[i][0] = 0
    for j in range(m):
        c[0][j] = 0
    for i in range(1, n):
        for j in range(1, m):
            if s[i - 1] == t[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
                direction[i][j] = 0 # volta uma linha e uma coluna
            elif c[i][j - 1] >= c[i - 1][j]:
                c[i][j] = c[i][j - 1]
                direction[i][j] = 1 # volta uma coluna na mesma linha
            else:
                c[i][j] = c[i - 1][j]
                direction[i][j] = 2 # volta uma linha na mesma coluna
    return direction

def getLCS(direction, s, i, j, lcs=""):
    if i == 0 or j == 0:
        return lcs
    if direction[i][j] == 0: # volta uma linha e uma coluna
        lcs += getLCS(direction, s, i - 1, j - 1, lcs)
        lcs += s[i - 1]
        return lcs
    elif direction[i][j] == 2: # volta uma linha na mesma coluna
        lcs += getLCS(direction, s, i - 1, j, lcs)
    else: # volta uma coluna na mesma linha
        lcs += getLCS(direction, s, i, j - 1, lcs)
    return lcs

s = input()
t = input()
d = lcsLength(s, t)
print(getLCS(d, s, len(d) - 1, len(d[0]) - 1))

Submission status: Time Limit Exceeded

Solution code:

global gaa
global aru
aru = [[ "" for j in range(3002)] for i in range(3002)]

def main():
    a = input()
    b = input()
    for i in range(len(a)):
        for j in range(len(b)):
            if(i == 0 or j == 0):
                if(a[i] == b[j]): aru[i][j] = a[i]
                elif(a[i] != b[j]):
                    if(i == 0 and j == 0):
                        aru[i][j] = ""
                    elif(i == 0):
                        aru[i][j] = aru[i][j-1]
                    elif(j == 0):
                        aru[i][j] = aru[i-1][j]
            else:
                if(a[i] == b[j]):
                   aru[i][j] = aru[i-1][j-1] + a[i]
                else:
                    
                    if(len(aru[i][j-1]) < len(aru[i-1][j])):
                        aru[i][j] = aru[i-1][j]
                    else:
                        aru[i][j] = aru[i][j-1]


    print(aru[len(a)-1][len(b)-1])



main()

Submission status: Time Limit Exceeded

Solution code:
s=str(input())
t=str(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]
        elif len(dp[i][j+1])!=0 and len(dp[i+1][j])==len(dp[i][j+1]):
            #print(dp[i][j+1],dp[i+1][j])
            dp[i+1][j+1]=min(dp[i][j+1],dp[i+1][j])
            #print(dp[i+1][j+1])
        else:
            #print(dp[i][j+1],dp[i+1][j])
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
            #print(dp[i+1][j+1])
print(dp[n][m])

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
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):
    for j in range(m):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
ans = ''
while(dp[n][m]>0):
  if dp[n][m] == dp[n-1][m-1] +1 and dp[n][m] == dp[n-1][m] +1 and dp[n][m] == dp[n][m-1] +1:
    ans += s[n-1]
    n -= 1
    m -= 1
  elif dp[n-1][m] > dp[n][m-1]:
    n -= 1
  else:
    m -= 1
print(''.join(reversed(list(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(len(s)):
    for j in range(len(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][j + 1], dp[i + 1][j])

# print(dp[-1][-1]) # 最長文字数
i, j = len(s), len(t)

ans = []
while i > 0 and j > 0:
    if s[i - 1] == t[j - 1] and dp[i][j] == dp[i - 1][j - 1] + 1:
        ans.append(s[i - 1])
        i -= 1
        j -= 1
    else:
        if dp[i - 1][j] == dp[i][j]:
            i -= 1
        else:
            j -= 1
print(*reversed(ans), sep='')

Submission status: Time Limit Exceeded

Solution code:
import sys
s= sys.stdin.readline().rstrip() 
t= sys.stdin.readline() .rstrip()
Ns=len(s)
Nt=len(t)
i=1
dp=[["" for i in range(Nt+1)]for j in range(Ns+1)]
while i<=Ns:
    j=1
    while j<=Nt:
        if 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][j-1]
            else:
                dp[i][j]=dp[i-1][j]
        j+=1
    i+=1
print(dp[Ns][Nt])

Submission status: Time Limit Exceeded

Solution code:
import sys
s= sys.stdin.readline().rstrip() 
t= sys.stdin.readline() .rstrip()
Ns=len(s)
Nt=len(t)
dp=[["" for i in range(Nt+1)]for j in range(Ns+1)]
for i in range(1,Ns+1):
    for j in range(1,Nt+1):
        if 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][j-1]
            else:
                dp[i][j]=dp[i-1][j]
print(dp[Ns][Nt])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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]:
            new_len, word = DP[i][j][0] + 1, DP[i][j][1] + S[i]
            DP[i+1][j+1] = max([new_len, word], DP[i+1][j], DP[i][j+1])

        else:
            DP[i+1][j+1] = max(DP[i][j], DP[i+1][j], DP[i][j+1])

ans = DP[-1][-1][1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    l = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
    for i, vi in enumerate(s):
        for j, vj in enumerate(t):
            if vi == vj:
                l[i + 1][j + 1] = l[i][j] + 1
                continue
            l[i + 1][j + 1] = max(l[i][j + 1], l[i + 1][j])
    n = l[-1][-1]
    i = len(s)
    j = len(t)
    r = ''
    while n > 0:
        if i - 1 > 0 and l[i][j] == l[i-1][j]:
            i = i - 1
        elif j - 1 > 0 and l[i][j] == l[i][j-1]:
            j = j - 1
        else:
            r += s[i-1]
            i = i - 1
            j = j - 1
            n -= 1
    print(r[::-1])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s, t = input(), input()
    dp = ['' for _ in range(len(t) + 1)]
    for i, si in enumerate(s, 1):
        u = ''
        for j, ti in enumerate(t, 1):
            d = u
            l = dp[j - 1]
            u = dp[j]
            if si == ti:
                dp[j] = d + si
            else:
                if len(l) > len(u):
                    dp[j] = l
    print(dp[-1])


main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = np.array(list(input()), np.unicode)
sl = len(s)
t = np.array(list(input()), np.unicode)
tl = len(t)
equal = (s[:, None] == t[None, :])

dp = np.array([np.zeros(tl + 1, np.int32)])
for i in range(sl):
    tmp = dp[-1].copy()
    np.maximum(tmp[1:], tmp[:-1] + equal[i], out=tmp[1:])
    np.maximum.accumulate(tmp, out=tmp)
    dp = np.append(dp, [tmp], axis=0)

answer = ''
while sl > 0 and tl > 0:
    if s[sl - 1] == t[tl - 1]:
        sl -= 1
        tl -= 1
        answer += s[sl]
        continue

    if dp[sl - 1][tl] > dp[sl][tl - 1]:
        sl -= 1
    else:
        tl -= 1

print(answer[::-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
l = ['' for _ in range(len(t) + 1)]
n = [0] * (len(t) + 1)
for vi in s:
    for j, vj in enumerate(t):
        if vi == vj:
            l[j + 1] = l[j + 1] + vi
            n[j + 1] += 1
            continue
        if n[j] > n[j + 1]:
            l[j + 1] = l[j]
            n[j + 1] = n[j]
print(l[-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
l = ['' for _ in range(len(t) + 1)]
for vi in s:
    for j, vj in enumerate(t):
        if vi == vj:
            l[j + 1] = l[j + 1] + vi
            continue
        t1 = l[j + 1]
        t2 = l[j]
        if len(t2) > len(t1):
            l[j + 1] = t2
print(l[-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    sl = len(s)
    t = input()
    tl = len(t)

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

    answer = ''
    while sl > 0 and tl > 0:
        if s[sl - 1] == t[tl - 1]:
            sl -= 1
            tl -= 1
            answer += s[sl]
            continue

        if dp[sl - 1][tl] > dp[sl][tl - 1]:
            sl -= 1
        else:
            tl -= 1

    print(answer[::-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
l = [['' for _ in range(len(t))] for _ in range(len(s))]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            if i == 0 or j == 0:
                l[i][j] = s[i]
            else:
                l[i][j] = l[i-1][j-1] + s[i]
        elif i != 0 and j == 0:
            l[i][j] = l[i-1][j]
        elif i == 0:
            l[i][j] = l[i][j-1]
        elif len(l[i][j-1]) > len(l[i-1][j]):
            l[i][j] = l[i][j-1]
        else:
            l[i][j] = l[i-1][j]
print(l[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    s, t = input(), input()
    v = [('', False) for _ in range(len(t) + 1)]
    w = [('', False) for _ in range(len(t) + 1)]
    for i in range(1, len(s) + 1):
        for j in range(1, len(t) + 1):
            u, uu = v[j]
            l, ll = w[j - 1]
            d, dd = v[j - 1]
            if s[i - 1] == t[j - 1]:
                if len(u) > len(l) and not uu:
                    l, ll = u, uu 
                if len(l) > len(d) and not ll:
                    d, dd = l, ll
                w[j] = (d + s[i - 1], True)
            else:
                if len(u) > len(l):
                    l, ll = u, uu
                dd = False
                if len(l) > len(d):
                    d, dd = l, ll
                w[j] = (d, dd)
        v, w = w, v
    print(v[-1][0])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s, t = input(), input()
    v = [('', False) for i in range(len(t) + 1)]
    for i in range(1, len(s) + 1):
        w = [('', False) for _ in range(len(t) + 1)]
        for j in range(1, len(t) + 1):
            u, uu = v[j]
            l, ll = w[j - 1]
            d, dd = v[j - 1]
            if s[i - 1] == t[j - 1]:
                if len(u) > len(l) and not uu:
                    l, ll = u, uu 
                if len(l) > len(d) and not ll:
                    d, dd = l, ll
                w[j] = (d + s[i - 1], True)
            else:
                if len(u) > len(l):
                    l, ll = u, uu
                dd = False
                if len(l) > len(d):
                    d, dd = l, ll
                w[j] = (d, dd)
        v = w
    print(v[-1][0])


main()

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
ma=0
a=[0,0]
dp=[[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
pred=[[-1 for i in range(len(t)+1)] for j in range(len(s)+1)]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        dp[i][j]=max(dp[i][j],dp[i-1][j])
        dp[i][j]=max(dp[i][j],dp[i][j-1])
        if s[i-1]==t[j-1]:
            dp[i][j]=max(dp[i][j],1+dp[i-1][j-1])
        if dp[i][j]==1+dp[i-1][j-1]:
            pred[i][j]=[i-1,j-1]
        if dp[i][j]==dp[i][j-1]:
            pred[i][j]=[i,j-1]
        if dp[i][j]==dp[i-1][j]:
            pred[i][j]=[i-1,j]
        if dp[i][j]>ma:
            ma=dp[i][j]
            a=[i,j]
b=a

ans=[b[:]]
while b!=-1:
    #print(b)
    b=pred[b[0]][b[1]]
    if b==-1:
        break
    if 0 in b:
        break
    if b!=-1:
        ans.append(b[:])


ss=""
for  i in ans:
    if s[i[0]-1]==t[i[1]-1]:
        ss+=s[i[0]-1]
ss=ss[-1::-1]
print(ss)

Submission status: Time Limit Exceeded

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

        ma=max(ma,dp[i][j])
ans=""
a=[-1,-1]
ma=-1
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if dp[i][j]>ma:
            ma=dp[i][j]
            a=[i,j][:]
b=a[:]
ans=[b[:]]
while b!=-1:
    #print(b)
    b=pred[b[0]][b[1]][:]
    if 0 in b:
        break
    if b!=-1:
        ans.append(b)


ss=""
for  i in ans:
    if s[i[0]-1]==t[i[1]-1]:
        ss+=s[i[0]-1]
ss=ss[-1::-1]
print(ss)