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

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    S = readline().strip()
    T = readline().strip()
    N, M = len(S), len(T)

    dp = [[0] * (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] + 1
            elif dp[i + 1][j] > dp[i][j + 1]:
                dp[i + 1][j + 1] = dp[i + 1][j]
            else:
                dp[i + 1][j + 1] = dp[i][j + 1]

    ans = []
    i, j = N, M
    while i and j:
        if S[i - 1] == T[j - 1]:
            ans.append(S[i - 1])
            i -= 1
            j -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            i -= 1

    print(''.join(reversed(ans)))
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
s=input()
t=input()
@lru_cache(None)
def dp(i,j):
  if i==0 or j==0:
    return ""
  if s[i-1]==t[j-1]:
    return ''.join([dp(i-1,j-1)+s[i-1]])
  else:
    return dp(i,j-1) if len(dp(i,j-1))>=len(dp(i-1,j)) else dp(i-1,j)
print(dp(len(s),len(t)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())

s=input()
t=input()
@lru_cache(None)
def dp(i,j):
  if i==0 or j==0:
    return ""
  if s[i-1]==t[j-1]:
    return dp(i-1,j-1)+s[i-1]
  else:
    return dp(i,j-1) if len(dp(i,j-1))>=len(dp(i-1,j)) else dp(i-1,j)
print(dp(len(s),len(t)))

Submission status: Time Limit Exceeded

Solution code:
import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

def LCS(s, t):
	n, m = len(s), len(t)
	dp = [[0 for i in range(m+1)] for j in range(n+1)]
	for i in range(n+1):
		for j in range(m+1):
			if i == 0 or j == 0:
				dp[i][j] = 0
			elif s[i-1] == t[j-1]:
				dp[i][j] = 1 + dp[i-1][j-1]
			else:
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
	index = dp[n][m]
	ans = [" "]*index
	i, j = n, m
	while index:
		if s[i-1] == t[j-1]:
			ans[index-1] =  s[i-1]
			index -= 1
			i -= 1; j -= 1
		elif dp[i-1][j] > dp[i][j-1]:
			i -= 1
		else:
			j -= 1
	return(("").join(ans))

def solve():
	s1 = inp().strip(); s2 = inp().strip()
	print(LCS(s1, s2))




if __name__ == "__main__":
	solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def LCS(s, t):
	n, m = len(s), len(t)
	dp = [[0 for i in range(m+1)] for j in range(n+1)]
	for i in range(n+1):
		for j in range(m+1):
			if i == 0 or j == 0:
				dp[i][j] = 0
			elif s[i-1] == t[j-1]:
				dp[i][j] = 1 + dp[i-1][j-1]
			else:
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
	# print("    ", end="")
	# for i in t:print(i, end = " ")
	# s += " "
	# # print("\n")
	# for k in range(n+1):
	# 	print(s[k-1], *dp[k])
	index = dp[n][m]
	ans = [" "]*index
	i, j = n, m
	while index:
		if s[i-1] == t[j-1]:
			ans[index-1] =  s[i-1]
			index -= 1
			i -= 1; j -= 1
		elif dp[i-1][j] > dp[i][j-1]:
			i -= 1
		else:
			j -= 1
	return(("").join(ans))

def solve():
	s1 = input().strip(); s2 = input().strip()
	print(LCS(s1, s2))









if __name__ == "__main__":
	solve()

Submission status: Time Limit Exceeded

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
s=s0()
t=s0()

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

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

# print(dp)

#reverse
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:
s=input()
t=input()
x=len(s)
y=len(t)
dp=[[0 for i in range(y)] for i in range(x)]
for i in range(x):
	if(t[-1] in s[i:]):
		dp[i][y-1]=t[-1]
	else:
		dp[i][y-1]=""
for j in range(y):
	if(s[-1] in t[j:]):
		dp[x-1][j]=s[-1]
	else:
		dp[x-1][j]=""
if(s[-1]==t[-1]):
	dp[x-1][y-1]=t[-1]
else:
	dp[x-1][y-1]=""
for i in range(x-2,-1,-1):
	for j in range(y-2,-1,-1):
		if(s[i]==t[j]):
			dp[i][j]=s[i]+dp[i+1][j+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[0][0])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
def lcs(s1, s2):
    dp=[[0 for i in range(len(s2)+1)] for j 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]):
                if(i==0 or j==0):
                    dp[i][j]=1;
                else:
                    dp[i][j]=dp[i-1][j-1]+1;
            else:
                dp[i][j]=max(dp[i][j-1],dp[i-1][j])
      
    
    
    i = len(s1)
    j = len(s2)
    ans = ""
    while i>0 and j >0:
        if s1[i-1]==s2[j-1]:
            ans+=s1[i-1]
            i-=1
            j-=1
        else:
            if dp[i-1][j]>dp[i][j-1]:
                i-=1
            else:
                j-=1
                
    cs=dp[-1][-1];
    return ans


print(lcs(s,t)[::-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
def lcs(s1, s2):
    dp=[""]*(len(s2)+1)
    
    for i in range(len(s1)):
        new_dp=[""]*(len(s2)+1)
        for j in range(len(s2)):
            if(s1[i]==s2[j]):
                if(i==0 or j==0):
                    new_dp[j]=s1[i];
                else:
                    new_dp[j]=dp[j-1]+s1[i];
            else:
                new_dp[j]=max(new_dp[j-1],dp[j],key = len)
        dp=new_dp;

    cs=dp[-2];
    return len(cs), cs


print(lcs(s,t)[1])

Submission status: Time Limit Exceeded

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
def lcs(s1, s2):
    matrix = [["" for x in range(len(s2))] for x in range(len(s1))]
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i] == s2[j]:
                if i == 0 or j == 0:
                    matrix[i][j] = s1[i]
                else:
                    matrix[i][j] = matrix[i-1][j-1] + s1[i]
            else:
                matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1], key=len)

    cs = matrix[-1][-1]

    return len(cs), cs


print(lcs(s,t)[1])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    S = list(input())
    T = list(input())

    LCS = [[0 for _ in range(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):
            x = 1 if S[i - 1] == T[j - 1] else 0
            LCS[i][j] = max(LCS[i - 1][j - 1] + x, LCS[i - 1][j], LCS[i][j - 1])

    res = ""
    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if LCS[i][j] == LCS[i - 1][j]:
            i -= 1
        elif LCS[i][j] == LCS[i][j - 1]:
            j -= 1
        else:
            res += S[i - 1]
            i -= 1
            j -= 1

    print(res[::-1])


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

def main():
  s = input().rstrip()
  t = input().rstrip()
  ls = len(s)
  lt = len(t)
  dp = [[0]*(lt+1) for _ in range(ls+1)]
  for i in range(ls):
    for j in range(lt):
      if s[i] == t[j]:
        dp[i+1][j+1] = dp[i][j] + 1
      else:
        dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
  ans = ""
  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)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

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

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=''
a=n
b=m
while a>0 and b>0:
  if dp[a][b]==dp[a-1][b]:
    a-=1
  elif dp[a][b]==dp[a][b-1]:
    b-=1
  else:
    a-=1
    b-=1
    ans=s[a]+ans
print(ans)

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(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][0], dp[i - 1][j - 1][1] + s[i - 1]]

        else:

            a, s1 = dp[i - 1][j]
            b, s2 = dp[i][j - 1]

            if a > b:
                dp[i][j] = [a, s1]

            else:
                dp[i][j] = [b, s2]

print(dp[n][m][1])

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:

import sys

def lcs(s, t):
    n = len(s)
    m = len(t)
    dp = [[[0, ""] for i in range(n + 1)] for  j in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):

            if s[j - 1] == t[i - 1]:
                dp[i][j] = [1 + dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]+s[j - 1]]
                # strn += s[i - 1]

            else:

                a, s1 = dp[i - 1][j]
                b, s2 = dp[i][j - 1]

                if a > b:
                    dp[i][j] = [a, s1]

                else:
                    dp[i][j] = [b, s2]

    return dp[m][n][1]


s =  sys.stdin.readline().strip()
t =  sys.stdin.readline().strip()
sys.stdout.write(str(lcs(s, t)))

Submission status: Time Limit Exceeded

Solution code:
def LCS(s1, s2):
    l1, l2 = len(s1), len(s2)
    dp = [['' for _ in range(l2 + 1)] for _ in range(l1 + 1)]
    for i in range(1, l1 + 1):
        for j in range(1, l2 + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + s1[i - 1]
            else:
                dp[i][j] = dp[i][j - 1] if len(dp[i][j - 1]) > len(dp[i - 1][j]) else dp[i - 1][j]
    return dp[l1][l2]
 
 
if __name__ == '__main__':
    s1 = input()
    s2 = input()
    print(LCS(s1, s2))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def LCS():
  X = np.array(list(input()),dtype = str)
  Y = np.array(list(input()),dtype = str)
  
  dp = np.zeros([len(Y) + 1,len(X) + 1],dtype = int)
  for y in range(len(Y)):
    for x in range(len(X)):
      if Y[y] == X[x]:
        #Xのi文字目とYのj文字目が一致した時のみ値が更新される
        #文字列が一致する直線、i - 1,j - 1目までの最大一致数に、1を足す
        dp[y + 1][x + 1] = dp[y][x] + 1
        
      else:
        dp[y + 1][x + 1] = max(dp[y][x + 1],dp[y + 1][x])
        
    
  x = len(X)
  y = len(Y)
  ans = ""
  
  while x > 0 and y > 0:
    if dp[y][x] == dp[y - 1][x]:
      y -= 1
    elif dp[y][x] == dp[y][x - 1]:
      x -= 1
    else:
      ans = Y[y - 1] + ans
      y,x = y - 1,x - 1
  
  print(ans)
  
LCS()

Submission status: Time Limit Exceeded

Solution code:
def LCS(s1, s2):
    l1, l2 = len(s1), len(s2)
    dp = [['' for _ in range(l2 + 1)] for _ in range(l1 + 1)]
    for i in range(1, l1 + 1):
        for j in range(1, l2 + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + s1[i - 1]
            else:
                dp[i][j] = dp[i][j - 1] if len(dp[i][j - 1]) > len(dp[i - 1][j]) else dp[i - 1][j]
    return dp[l1][l2]


if __name__ == '__main__':
    s1 = input()
    s2 = input()
    print(LCS(s1, s2))

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)]
s = "0"+s
t = "0"+t

q = []

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

i = len(t)-1
j = len(s)-1

while i != 0 and j != 0:
    if dp[i][j] != dp[i-1][j] and  dp[i][j] != dp[i][j-1]:
        q.append(t[i])
        i -= 1
        j -= 1
    elif dp[i][j] != dp[i-1][j] and  dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j] and  dp[i][j] != dp[i][j-1]:
        i -= 1
    else:
        i -= 1

print(''.join(q[::-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def LCS():
  X = input()
  Y = input()
  
  dp = np.zeros([len(Y) + 1,len(X) + 1],dtype = int)
  for y in range(len(Y)):
    for x in range(len(X)):
      if Y[y] == X[x]:
        #Xのi文字目とYのj文字目が一致した時のみ値が更新される
        #文字列が一致する直線、i - 1,j - 1目までの最大一致数に、1を足す
        dp[y + 1][x + 1] = dp[y][x] + 1
        
      else:
        dp[y + 1][x + 1] = max(dp[y][x + 1],dp[y + 1][x])
        
    
  x = len(X)
  y = len(Y)
  ans = ""
  
  while x > 0 and y > 0:
    if dp[y][x] == dp[y - 1][x]:
      y -= 1
    elif dp[y][x] == dp[y][x - 1]:
      x -= 1
    else:
      ans = Y[y - 1] + ans
      y,x = y - 1,x - 1
  
  print(ans)
  
LCS()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def LCS():
  X = input()
  Y = input()
  dp = [["" for i in range(len(X) + 1) ]for i in range(len(Y) + 1)]
  for y in range(len(Y)):
    for x in range(len(X)):
      if Y[y] == X[x]:
        #Xのi文字目とYのj文字目が一致した時のみ値が更新される
        #文字列が一致する直線、i - 1,j - 1目までの最大一致数に、1を足す
        dp[y + 1][x + 1] = dp[y][x] + X[x]
      else:
        a = dp[y][x]
        b = dp[y + 1][x]
        c = dp[y][x + 1]
        m = max(len(b),len(c))
        if len(a) > len(b) or len(a) > len(c):
          continue
        if m == len(c):
          dp[y + 1][x + 1] = c
        elif m == len(b):
          dp[y + 1][x + 1] = b
    
  print(dp[-1][-1])
  
LCS()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    s = input()
    t = input()
    s_size = len(s)
    t_size = len(t)
    dp = ["" for i in range(s_size+1)]
    for i in range(1, t_size+1):
        tmp = ""
        for j in range(1, s_size+1):
            tmp1 = dp[j]
            if t[i-1] == s[j-1]:
                dp[j] = tmp + t[i-1]
            else:
                dp[j] = dp[j-1] if len(dp[j-1]) > len(tmp1) else tmp1
            tmp = tmp1
    print(dp[-1])
solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    s = input()
    t = input()
    s_size = len(s)
    t_size = len(t)
    dp = [["" for i in range(s_size+1)] for j in range(t_size+1)]
    for i in range(1, t_size+1):
        for j in range(1, s_size+1):
            if t[i-1] == s[j-1]:
                dp[i][j] = dp[i-1][j-1] + t[i-1]
            else:
                dp[i][j] = dp[i][j-1] if len(dp[i][j-1]) > len(dp[i-1][j]) else dp[i-1][j]
    print(dp[t_size][s_size])
solve()

Submission status: Time Limit Exceeded

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

def LCS(X,Y):
    XL = len(X)
    YL = len(Y)
    dp = [[0 for j in range(YL+1)] for i in range(XL+1)]
    for i in range(XL):
        for j in range(YL):
            if X[i] == Y[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])
    # 以下復元
    idx = dp[XL][YL]-1
    S = [0 for i in range(idx+1)]
    i,j = XL,YL
    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
            S[idx] = X[i]
            idx -= 1
    return S

print(''.join(LCS(s,t)))

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
S=len(s)
T=len(t)
ans=[[""for e in range(S+1)] for f in range(T+1)]
ct=[[0 for e in range(S+1)] for f in range(T+1)]
for a in range(1,T+1):
 for b in range(1,S+1):
  if t[a-1]==s[b-1]:
   ans[a][b]=ans[a-1][b-1]+t[a-1]
   ct[a][b]=ct[a-1][b-1]+1
  else:
   if ct[a-1][b]> ct[a][b-1]:
    ans[a][b]=ans[a-1][b]
    ct[a][b]=ct[a-1][b]
   else:
    ans[a][b]=ans[a][b-1]
    ct[a][b]=ct[a][b-1]   
print(ans[T][S])

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
S=len(s)
T=len(t)
ans=[[""for e in range(S+1)] for f in range(T+1)]
for a in range(1,T+1):
 for b in range(1,S+1):
  if t[a-1]==s[b-1]:
   ans[a][b]=ans[a-1][b-1]+t[a-1]
  else:
   if len(ans[a-1][b])>len(ans[a][b-1]):
    ans[a][b]=ans[a-1][b]
   else:
    ans[a][b]=ans[a][b-1]
print(ans[T][S])

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])
      
i, j = len(s), len(t)
f = ""

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 :
    f += s[i-1]
    i -= 1
    j -= 1
  
print(f[::-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s=input()
t=input()
a=len(s)
b=len(t)
dp=np.full((a+1,b+1),0,dtype=int)
for i in range(a):
  for j in range(b):
    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 a!=0 and b!=0:
  if dp[a][b]==dp[a-1][b]:
    a-=1
  elif dp[a][b]==dp[a][b-1]:
    b-=1
  else:
    a-=1
    b-=1
    res=s[a]+res
print(res)

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
a=len(s)
b=len(t)
dp=[[0]*(b+1) for i in range(a+1)]
for i in range(a):
  for j in range(b):
    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 a!=0 and b!=0:
  if dp[a][b]==dp[a-1][b]:
    a-=1
  elif dp[a][b]==dp[a][b-1]:
    b-=1
  else:
    a-=1
    b-=1
    res=s[a]+res
print(res)

Submission status: Time Limit Exceeded

Solution code:
def lcs(s, t):
    n = len(s)
    m = len(t)
    # dp[i][j] := 0-indexでsのi-1文字目までとtのj-1文字目までとのlcsの長さ
    # dp[0][0]は空文字を見ていると考えるからdp[0][0] = 0
    # dp[n][m] := sのn-1文字目まで（0-indexなのでsの末尾）とtのm-1文字目まで(0-indexなのでtの末尾)
    dp = [[0]*(m+1) for _ in range(n+1)]

    for i in range(n):
        for j in range(m):
            # 0-indexでsのi文字目とtのj文字目が等しいなら斜めに移動する
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            # 異なるなら左または上のmaxをとる
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    res = ""
    while n != 0 and m != 0:  # どちらかが0になったら終わり，dp[0][*]及びdp[*][0]は必ず0なので
        # 上から遷移している場合，nをデクリメントしてよい
        if dp[n][m] == dp[n-1][m]:
            n -= 1
        # 左から遷移している場合，mをデクリメントしてよい
        elif dp[n][m] == dp[n][m-1]:
            m -= 1
        # 左でも上でもなく，左上からの遷移の場合，共通文字
        else:
            n -= 1
            m -= 1
            # 後ろから復元しているので以下のようにする
            res = s[n] + res
    return res


S = input()
T = input()
print(lcs(S, T))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
T=input()
dp=[["" for j in range(len(T))] for i in range(len(S))]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i][j]=dp[max(i-1,0)][max(j-1,0)]+S[i]
        else:
            L=[dp[max(i-1,0)][max(j-1,0)],dp[max(i-1,0)][j],dp[i][max(j-1,0)]]
            L_len=[len(L[0]),len(L[1]),len(L[2])]
            dp[i][j]=L[L_len.index(max(L_len))]
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
S=input()
T=input()
dp=[["" for j in range(len(T))] for i in range(len(S))]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i][j]=dp[max(i-1,0)][max(j-1,0)]+S[i]
        else:
            L=[dp[max(i-1,0)][max(j-1,0)],dp[max(i-1,0)][j],dp[i][max(j-1,0)]]
            dp[i][j]=L[np.argmax([len(L[0]),len(L[1]),len(L[2])])]
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]:
            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[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
#最長共通部分列
# https://qiita.com/_rdtr/items/c49aa20f8d48fbea8bd2

#比較する文字列
s1 = input()
s2 = input()

table = [[0 for _ in range(len(s1))] for _ in range(len(s2))]

#0行目を埋める
f = 0
for i in range(len(s2)):
    if f or s2[i] == s1[0]:
        table[i][0] = 1
        f = 1

#0列目を埋める
f = 0
for i in range(len(s1)):
    if f or s2[0] == s1[i]:
        table[0][i] = 1
        f = 1


for i in range(1, len(s2)):
    for j in range(1, len(s1)):
        #上マスと左マスは考慮済みなので、左上から遷移する
        if s2[i] == s1[j]:
            table[i][j] += table[i-1][j-1]+1
        else:
            if i == 0 or j == 0:
                continue
            else:
                table[i][j] = max(table[i-1][j], table[i][j-1])

# for col in table:
#     print(col)

#最長文字列を求める
lcs_str = ""
i, j = len(s2)-1, len(s1)-1

while i >= 0 and j >= 0:
    # print("i", i, "j", j)
    if s2[i] == s1[j]:
        # print("c")
        lcs_str += s2[i] #or s2[j-1]
        i -= 1
        j -= 1
    else:
        if j == 0:
            i -= 1
        elif i == 0:
            j -= 1
        else:
            if table[i-1][j] > table[i][j-1]:
                i -= 1
            else:
                j -= 1
print(lcs_str[::-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    S = input().rstrip()
    T = input().rstrip()

    # dp[i][j] = sのi番目とtのj番目まででえられる最長部分列の長さ
    dp = [[(0, "")] * (len(T) + 1) for _ in range(len(S) + 1)]

    for i, s in enumerate(S, 1):
        for j, t in enumerate(T, 1):
            # 一致するとき
            if s == t:
                # 一致する文字の一つ左側までの最大部分列に一致した文字を加える
                if dp[i][j][0] < dp[i-1][j-1][0] + 1:
                    dp[i][j] = (dp[i-1][j-1][0] + 1, dp[i-1][j-1][1] + s)
            # 一致しない場合も、一つ手前の文字までの最大文字列を引き継ぐ
            if dp[i][j][0] < dp[i-1][j][0]:
                dp[i][j] = dp[i-1][j]
            if dp[i][j][0] < dp[i][j-1][0]:
                dp[i][j] = dp[i][j-1]
    print(dp[len(S)][len(T)][1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s1=input()
s2=input()
a=[[0]*(len(s2)+1) for i in range(len(s1)+1)]
res=''
for i in range(1,len(s1)+1):
  for j in range(1,len(s2)+1):
    if s1[i-1] == s2[j-1]:
      a[i][j] = a[i-1][j-1] + 1
    elif a[i-1][j] >= a[i][j-1]:
      a[i][j] = a[i-1][j]
    else:
      a[i][j] = a[i][j-1]
i=len(s1)
j=len(s2)
while i>0 and j>0:
  if a[i][j] == a[i-1][j]:
    i -= 1
  elif a[i][j] == a[i][j-1]:
    j -= 1
  else:
    res = s1[i-1] + res
    i -= 1
    j -= 1   
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
s1 = input()
s2 = input()
n, m = len(s1), len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
prev = dp[0]
for i in range(1,n+1):
    dpi = dp[i]
    for j in range(1, m+1):
        if s1[i-1] == s2[j-1]:
            dpi[j] = 1 + prev[j-1]
        else:
            dpi[j] = max(prev[j], dpi[j-1])
    prev = dpi
res = []
i, j = n, m
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        res.append(s1[i-1])
        i -= 1
        j -= 1
print(''.join(map(chr,res))[::-1])

Submission status: Time Limit Exceeded

Solution code:
s1 = input()
s2 = input()
n, m = len(s1), len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
prev = dp[0]
for i in range(1,n+1):
    dpi = dp[i]
    for j in range(1, m+1):
        if s1[i-1] == s2[j-1]:
            dpi[j] = 1 + prev[j-1]
        else:
            dpi[j] = max(prev[j], dpi[j-1])
    prev = dpi
res = ''
i, j = n, m
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        res = s1[i-1] + res
        i -= 1
        j -= 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
s1 = input()
s2 = input()
n = len(s1)
m = len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1, m+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])
res = ''
i, j = n, m
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        res = s1[i-1] + res
        i -= 1
        j -= 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
s1 = list(input())
s2 = list(input())
n = len(s1)
m = len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1, m+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])
res = ''
i, j = n, m
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        res = s1[i-1] + res
        i -= 1
        j -= 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
s1 = list(input())
s2 = list(input())
n = len(s1)
m = len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1, m+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])
res = []
i, j = n, m
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        res.append(s1[i-1])
        i -= 1
        j -= 1
print(''.join(res[::-1]))

Submission status: Time Limit Exceeded

Solution code:
s1 = list(input())
s2 = list(input())
n = len(s1)
m = len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1, m+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])
res = []
i, j = n, m
while i > 0 and j > 0:
    if s1[i-1] == s2[j-1]:
        res.append(s1[i-1])
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1
print(''.join(res[::-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


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

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

    for i, si in enumerate(s):
        for j, tj in enumerate(t):
            if si == tj:
                dp[i + 1][j + 1] = dp[i][j] + si
            else:
                x, y = dp[i][j + 1], dp[i + 1][j]
                dp[i + 1][j + 1] = x if len(x) > len(y) else y

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def max_words(a,b):
    if len(a)>len(b):
        return a
    else:
        return b


dp = [[""]*(len(t)+1) for _ in range(len(s)+1)] #dp[i+1][j+1] : sのi文字目までとtのj文字目までのLCS

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

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