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

ansl = []
cnt = dp[-1][-1]
def tami(i,j):
  global cnt
  if cnt == 0:
    return
  if s[i-1] == t[j-1]:
    cnt -= 1
    ansl.append(i-1)
  if dp[i-1][j-1]==cnt:
    tami(i-1,j-1)
  if dp[i][j-1]==cnt:
    tami(i,j-1)

tami(len(s),len(t))

ans = ""
for i in ansl:
  ans += s[i]
print(ans[::-1])

Submission status: Time Limit Exceeded

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

ls,lt = len(s),len(t)
dp = [[(0,"")]*(lt+1) for _ in [0]*(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][0]+1,dp[i-1][j][1]+s[i-1]]
        elif dp[i-1][j][0] >= dp[i][j-1][0]:
            dp[i][j] = dp[i-1][j][:]
        else:
            dp[i][j] = dp[i][j-1][:]
print(dp[-1][-1][1])

Submission status: Time Limit Exceeded

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

ls,lt = len(s),len(t)
if ls > lt:
    #短い方をsに固定
    s,t = t,s
    ls,lt = lt,ls
dp=[("",0,0)]
common_str_set = set([""])
max_len = 0
i_ans = 0
for i,c in enumerate(s):
    for common_str,j,l_dp in dp[:]:
        if max_len >= l_dp + min((ls - i,lt-j)):
            continue
        for k,ct in enumerate(t[j:],j):
            if c == ct and (common_str+c) not in common_str_set:
                dp.append((common_str+c,k+1,l_dp+1))
                common_str_set.add(common_str+c)
                if l_dp+1 > max_len:
                    max_len = l_dp+1
                    i_ans = len(dp)-1
                break
print(dp[i_ans][0])

Submission status: Time Limit Exceeded

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

ls,lt = len(s),len(t)
if ls > lt:
    #短い方をsに固定
    s,t = t,s
    ls,lt = lt,ls
dp=[("",0,0)]
common_str_set = set([""])
max_len = 0
i_ans = 0
for i,c in enumerate(s):
    for common_str,j,l_dp in dp[:]:
        for k,ct in enumerate(t[j:],j):
            if c == ct and (common_str+c) not in common_str_set:
                dp.append((common_str+c,k+1,l_dp+1))
                common_str_set.add(common_str+c)
                if l_dp+1 > max_len:
                    max_len = l_dp+1
                    i_ans = len(dp)-1
print(dp[i_ans][0])

Submission status: Time Limit Exceeded

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

ls,lt = len(s),len(t)
if ls > lt:
    #短い方をsに固定
    s,t = t,s
    ls,lt = lt,ls
dp=[("",0,0)]
common_str_set = set([""])
max_len = 0
i_ans = 0
for i,c in enumerate(s):
    for common_str,j,l_dp in dp.copy():
        for k,ct in enumerate(t[j:],j):
            if c == ct and (common_str+c) not in common_str_set:
                dp.append((common_str+c,k+1,l_dp+1))
                common_str_set.add(common_str+c)
                if l_dp+1 > max_len:
                    max_len = l_dp+1
                    i_ans = len(dp)-1
print(dp[i_ans][0])

Submission status: Time Limit Exceeded

Solution code:
#タイムアウト
from itertools import *

s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[[0,""]] * (lt + 1) for _ in range(ls + 1)]
for si,sk in enumerate(s):
    for ti,tk in enumerate(t):
        if sk==tk:
            dp[si+1][ti+1] = [dp[si][ti][0]+1,dp[si][ti][1]+sk]
        else:
            if dp[si][ti+1][0] > dp[si+1][ti][0]:
                dp[si+1][ti+1] = [dp[si][ti+1][0],dp[si][ti+1][1]]
            else:
                dp[si+1][ti+1] = [dp[si+1][ti][0],dp[si+1][ti][1]]
print(dp[-1][-1][-1])

Submission status: Time Limit Exceeded

Solution code:
from itertools import *

def make_dp():
    for i, j in product(range(1, ls + 1), 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])
    return dp[-1][-1]

def get_lcs(i,j,u):
    N=dp[i][j]
    U=dp[i-1][j]
    if N==U:
        return get_lcs(i-1,j,u)
    L = dp[i][j - 1]
    if N==L:
        return get_lcs(i, j-1, u)
    if N==1:
        return s[i-1]+u
    return get_lcs(i-1,j-1,s[i-1]+u)


s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0]*(lt+1) for _ in range(ls+1)]
make_dp()
if dp[-1][-1]==0:
    print()
else:
    print(get_lcs(ls,lt,""))

Submission status: Time Limit Exceeded

Solution code:
# タイムアウト
import numpy as np
from itertools import *

s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0]*(lt+1) for _ in range(ls+1)]
for i, j in product(range(1, ls + 1), 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])
u = ""
for _ in range(dp[-1][-1]):
    while dp[i][j] == dp[i - 1][j]:
        i -= 1
    while dp[i][j] == dp[i][j - 1]:
        j -= 1
    u = s[i - 1] + u
    i -= 1
print(u)

Submission status: Time Limit Exceeded

Solution code:
# タイムアウト
import numpy as np
from itertools import *

s = input()
t = input()
ls = len(s)
lt = len(t)
dp = np.zeros((ls + 1, lt + 1), dtype="uint32")
for i, j in product(range(1, ls + 1), 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])
u = ""
for _ in range(dp[-1][-1]):
    while dp[i][j] == dp[i - 1][j]:
        i -= 1
    while dp[i][j] == dp[i][j - 1]:
        j -= 1
    u = s[i - 1] + u
    i -= 1
print(u)

Submission status: Time Limit Exceeded

Solution code:
from itertools import *

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

Submission status: Time Limit Exceeded

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

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

for i in range(len(t) + 1):
    dp[i][0] = ''

for i in range(len(s) + 1):
    dp[0][i] = ''

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] + t[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[-1][-1])

Submission status: Time Limit Exceeded

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

  n, m = len(s), len(t)
  dp = [[0 for _ in range(m)] for _ in range(n)]
  
  for i in range(n):
    if s[i] == t[0]:
      for k in range(i, n):
        dp[k][0] = 1
      break

  for j in range(m):
    if t[j] == s[0]:
      for k in range(j, m):
        dp[0][k] = 1
      break

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

  lcs = dp[n - 1][m - 1]
  i = n - 1
  j = m - 1
  res = ''
  while len(res) < lcs:
    if s[i] == t[j]:
      res = s[i] + res
      i -= 1
      j -= 1
    elif i == 0:
      j -= 1
    elif j == 0:
      i -= 1
    elif dp[i - 1][j] > dp[i][j - 1]:
      i -= 1
    else:
      j -= 1
  return res

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

Submission status: Time Limit Exceeded

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

  n, m = len(s), len(t)
  dp = [[0 for _ in range(m)] for _ in range(n)]
  
  for i in range(n):
    if s[i] == t[0]:
      for k in range(i, n):
        dp[k][0] = 1
      break

  for j in range(m):
    if t[j] == s[0]:
      for k in range(j, m):
        dp[0][k] = 1
      break

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

  lcs = dp[n - 1][m - 1]
  i = n - 1
  j = m - 1
  res = ''
  while len(res) < lcs:
    if s[i] == t[j]:
      res = s[i] + res
      i -= 1
      j -= 1
    elif i == 0:
      j -= 1
    elif j == 0:
      i -= 1
    elif dp[i - 1][j] > dp[i][j - 1]:
      i -= 1
    else:
      j -= 1
  print(res)

if __name__ == "__main__":
  solve()

Submission status: Time Limit Exceeded

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

  n, m = len(s), len(t)
  dp = [[0 for _ in range(m)] for _ in range(n)]

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

  lcs = dp[n - 1][m - 1]
  i = n - 1
  j = m - 1
  res = ''
  while len(res) < lcs:
    if s[i] == t[j]:
      res = s[i] + res
      i -= 1
      j -= 1
    elif i == 0:
      j -= 1
    elif j == 0:
      i -= 1
    elif dp[i - 1][j] > dp[i][j - 1]:
      i -= 1
    else:
      j -= 1
  print(res)

if __name__ == "__main__":
  solve()

Submission status: Time Limit Exceeded

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

n, m = len(s), len(t)
dp = [[0 for _ in range(m)] for _ in range(n)]

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

lcs = dp[n - 1][m - 1]
i = n - 1
j = m - 1
res = ''
while len(res) < lcs:
  if s[i] == t[j]:
    res = s[i] + res
    i -= 1
    j -= 1
  elif i == 0:
    j -= 1
  elif j == 0:
    i -= 1
  elif dp[i - 1][j] > dp[i][j - 1]:
    i -= 1
  else:
    j -= 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = [ord(i) - 97 for i in s]
t = input()
t = [ord(i) -97 for i in t]

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

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][j-1], dp[i-1][j])

max_len = dp[-1][-1]

ans = []

i = ls
j = lt

for l in range(max_len):
    while dp[i-1][j] == max_len - l:
        i -= 1
    while dp[i][j-1] == max_len - l:
        j -= 1
    ans.append(s[i-1])
    #ans += s[i-1]

alphabet = [chr(97+i) for i in range(27)]
a = ""
for i in ans:
    a += alphabet[i]
print(a[::-1])
#print(ans[::-1])

Submission status: Time Limit Exceeded

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

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

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][j-1], dp[i-1][j])

max_len = dp[-1][-1]
#print(max_len)

ans = ""

i = ls
j = lt

for l in range(max_len):
    while dp[i-1][j] == max_len - l:
        i -= 1
    while dp[i][j-1] == max_len - l:
        j -= 1
    ans += s[i-1]


print(ans[::-1])

Submission status: Time Limit Exceeded

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

#print(dp)
count = dp[-1][-1]
ans = ["#"]*count
i,j = len(a),len(b)
while count != 0:
    if dp[i][j] - dp[i-1][j-1] == 1:
        i -= 1
        j -= 1
        ans[count-1] = a[i]
        count -= 1
    else:
        i = i-1
print("".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys

s = sys.stdin.readline()
t = sys.stdin.readline()

s_len = len(s) - 1
t_len = len(t) - 1
dp = [[[0, ''] for x in range(t_len)] for y in range(s_len)]

for i in range(t_len):
    if s[0] == t[i]:
        dp[0][i][1] = s[0]
        dp[0][i][0] = 1
    else:
        dp[0][i][1] = dp[0][i-1][1] if i != 0 else ''
        dp[0][i][0] = dp[0][i-1][0] if i != 0 else 0


for i in range(s_len):
    if s[i] == t[0]:
        dp[i][0][1] = t[0]
        dp[i][0][0] = 1
    else:
        dp[i][0][1] = dp[i-1][0][1] if i != 0 else ''
        dp[i][0][0] = dp[i-1][0][0] if i != 0 else 0

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

print(dp[s_len-1][t_len-1][1])

Submission status: Time Limit Exceeded

Solution code:
import sys

s = sys.stdin.readline().strip()
t = sys.stdin.readline().strip()

s_len = len(s)
t_len = len(t)
dp = [[[0, ''] for x in range(t_len)] for y in range(s_len)]

for i in range(t_len):
    if s[0] == t[i]:
        dp[0][i][1] = s[0]
        dp[0][i][0] = 1
    else:
        dp[0][i][1] = dp[0][i-1][1] if i != 0 else ''
        dp[0][i][0] = dp[0][i-1][0] if i != 0 else 0


for i in range(s_len):
    if s[i] == t[0]:
        dp[i][0][1] = t[0]
        dp[i][0][0] = 1
    else:
        dp[i][0][1] = dp[i-1][0][1] if i != 0 else ''
        dp[i][0][0] = dp[i-1][0][0] if i != 0 else 0

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

print(dp[s_len-1][t_len-1][1])

Submission status: Time Limit Exceeded

Solution code:
import sys

s = sys.stdin.readline().strip()
t = sys.stdin.readline().strip()

s_len = len(s)
t_len = len(t)
dp = [['' for x in range(t_len)] for y in range(s_len)]

for i in range(t_len):
    if s[0] == t[i]:
        dp[0][i] = s[0]
    else:
        dp[0][i] = dp[0][i-1] if i != 0 else ''


for i in range(s_len):
    if s[i] == t[0]:
        dp[i][0] = t[0]
    else:
        dp[i][0] = dp[i-1][0] if i != 0 else ''

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

Submission status: Time Limit Exceeded

Solution code:
import sys
# input処理を高速化する
input = sys.stdin.readline
# 入力
S = input()
T = input()

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
# input処理を高速化する
input = sys.stdin.readline
# 入力
S = input()
T = input()

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

# input処理を高速化する
input = sys.stdin.readline

# 入力
S = input()
T = input()

def lcs(s, t):
    dp = np.zeros((len(S)+1, len(T)+1), dtype=int)

    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] = np.maximum(dp[i+1][j], dp[i][j+1])
    
    ans = ''
    i = len(S)
    j = len(T)
    while (i>0  and j>0):
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans += s[i-1] 
            i -= 1
            j -= 1
    
    print(ans[::-1])

lcs(S, T)

Submission status: Time Limit Exceeded

Solution code:
import sys

# input処理を高速化する
input = sys.stdin.readline

# 入力
S = input()
T = input()

def chmax(a, b):
    if a >= b:
        return a
    else:
        return b


def lcs(s, t):
    dp = [[0 for i in range(len(T)+1)] for j in range(len(S)+1)]
    for i in range(len(S)):
        for j in range(len(T)):
            if S[i] == T[j]:
                dp[i+1][j+1] = chmax(dp[i+1][j+1], dp[i][j] + 1)
            dp[i+1][j+1] = chmax(dp[i+1][j+1], dp[i+1][j])
            dp[i+1][j+1] = chmax(dp[i+1][j+1], dp[i][j+1])

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

        
lcs(S, T)

Submission status: Time Limit Exceeded

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

MAX_LENGTH  = 3001
memoization = [[-1 for i in range(MAX_LENGTH)] for a in range(MAX_LENGTH)] 

string1 = input()
string2 = input()

def LCS(indexString1, indexString2):
   if indexString1 == len(string1) or indexString2 == len(string2):
      return ''
   
   if memoization[indexString1][indexString2] != -1:
      return memoization[indexString1][indexString2] 
   
   longestCommonSubsequence = None

   if string1[indexString1] == string2[indexString2]:
      longestCommonSubsequence = string1[indexString1] + LCS(indexString1+1, indexString2+1)
   
   else:
      longestCommonSubsequence = LCS(indexString1+1, indexString2)
      temp = LCS(indexString1, indexString2+1) 

      if len(temp) > len(longestCommonSubsequence):
         longestCommonSubsequence = temp
   
   memoization[indexString1][indexString2] = longestCommonSubsequence
   return longestCommonSubsequence

print( LCS(0,0) )

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
a=[[""]*(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]:
            a[i+1][j+1]=a[i][j]+s[i]
        else:
            a[i+1][j+1]=(a[i][j+1] if len(a[i][j+1])>len(a[i+1][j]) else a[i+1][j])
print(a[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = " "+input()
    N = len(s)-1

    t = " "+input()
    M = len(t)-1
    if N < M:
        N, M = M, N
        s, t = t, s
    # dp[i][j] := sのi文字目, tのj文字目までを使ったLCSの長さ
    # last_letter[i][j] := s_i, t_jまでを使ったLCSの最後の文字
    dp = [[-1]*(M+1) for i in range(N+1)]
    last_letter = [[-1]*(M+1) for i in range(N+1)]
    dp[0] = [0]*(N+1)
    last_letter[0] = ['' for n in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0
        last_letter[i][0] = ''
    for i in range(1, N+1):
        for j in range(1, M+1):
            
            if s[i] == t[j]:
                dp[i][j] = dp[i-1][j-1]+1
                last_letter[i][j] = last_letter[i-1][j-1] + s[i]
            elif s[i] != t[j]:
                if dp[i-1][j] > dp[i][j-1]:
                    dp[i][j] = dp[i-1][j]
                    last_letter[i][j] = last_letter[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1]
                    last_letter[i][j] = last_letter[i][j-1]
    print(last_letter[N][M])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

s = [ord(a)-97 for a in list(sys.stdin.readline().rstrip())]
t = [ord(b)-97 for b in list(sys.stdin.readline().rstrip())]
len_s = len(s)
len_t = len(t)

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

strings = []
while len_s > 0 and len_t > 0:
    if s[len_s-1] == t[len_t-1]:
        len_s -= 1
        len_t -= 1
        strings.insert(0,chr(s[len_s]+97))
    elif dp[len_s][len_t-1] > dp[len_s-1][len_t]:
        len_t -= 1
    else:
        len_s -= 1

print("".join(strings))

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    s = [ord(a)-97 for a in list(sys.stdin.readline().rstrip())]
    t = [ord(b)-97 for b in list(sys.stdin.readline().rstrip())]
    l1 = len(s)
    l2 = len(t)

    dp = [[0]*(l2+1) for _ in range(l1+1)]

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

    string = []
    for i,j in zip([m for m in range(l1,0,-1)],[n for n in range(l2,0,-1)]):
        if dp[i][j] > dp[i-1][j-1]:
            string.insert(0,chr(s[i-1]+97))
    print("".join(string))


main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def lcs_count(A,B):
    # initial value setting
    dp = [[0]*(l2+1) for _ in range(l1+1)]
    # create table
    for i in range(1,l1+1):
        for j in range(1,l2+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    return dp

def lcs_string(dp):
    string = []
    for i,j in zip([m for m in range(l1,0,-1)],[n for n in range(l2,0,-1)]):
        if dp[i][j] > dp[i-1][j-1]:
            string.insert(0,chr(s[i-1]+97))
    print("".join(string))

s = [ord(a)-97 for a in list(sys.stdin.readline().rstrip())]
t = [ord(b)-97 for b in list(sys.stdin.readline().rstrip())]
l1 = len(s)
l2 = len(t)

DP = lcs_count(s,t)
lcs_string(DP)

Submission status: Time Limit Exceeded

Solution code:

s = input()
t = input()

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

tab = [ [0]*sl for _ in range(tl)]

for i in range(1,sl):

    si = s[i-1]

    for j in range(1,tl):
        ti = t[j-1]

        if si == ti:
            tab[j][i] = tab[j-1][i-1] + 1
        else:
            tab[j][i] = max(tab[j-1][i], tab[j][i-1])


#for li in tab:
#    print(li)

ans = ''

sl -= 1
tl -= 1

while sl>0 and tl>0:

    if s[sl-1] == t[tl-1]:
        ans = s[sl-1] + ans
        tl -= 1
        sl -= 1

    elif tab[tl][sl] == tab[tl-1][sl]:
        tl -= 1
    
    elif tab[tl][sl] == tab[tl][sl-1]:
        sl -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def lcs_count(A,B):
    dp = [list(0 for _ in range(l2+1)) for _ in range(l1+1)]
    # create table
    for i in range(1,l1+1):
        for j in range(1,l2+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    return dp

def lcs_string(dp):
    string = []
    for i,j in zip([m for m in range(l1,0,-1)],[n for n in range(l2,0,-1)]):
        if dp[i][j] > dp[i-1][j-1]:
            string.insert(0,chr(s[i-1]+97))
    print("".join(string))

s = [ord(a)-97 for a in list(sys.stdin.readline().rstrip())]
t = [ord(b)-97 for b in list(sys.stdin.readline().rstrip())]
l1 = len(s)
l2 = len(t)

DP = lcs_count(s,t)
lcs_string(DP)

Submission status: Time Limit Exceeded

Solution code:
import sys

def lcs_count(A,B):
    # initial value setting
    dp = [list(0 for _ in range(l2+1)) for _ in range(l1+1)]
    # create table
    for i in range(1,l1+1):
        for j in range(1,l2+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    return dp

def lcs_string(dp):
    string = []
    S = [m for m in range(l1,0,-1)]
    T = [n for n in range(l2,0,-1)]
    for i,j in zip(S,T):
        if dp[i][j] > dp[i-1][j-1]:
            string.insert(0,s[i-1])
    print("".join(string))

s = sys.stdin.readline().rstrip()
t = sys.stdin.readline().rstrip()
l1 = len(s)
l2 = len(t)

DP = lcs_count(s,t)
lcs_string(DP)

Submission status: Time Limit Exceeded

Solution code:
import sys

def lcs_count(A,B):
    # initial value setting
    dp = [list(0 for _ in range(l2+1)) for _ in range(l1+1)]
    # create table
    for i in range(1,l1+1):
        for j in range(1,l2+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    return dp

def lcs_string(dp):
    string = []
    for i,j in zip([m for m in range(l1,0,-1)],[n for n in range(l2,0,-1)]):
        if dp[i][j] > dp[i-1][j-1]:
            string.insert(0,s[i-1])
    print("".join(string))

s = sys.stdin.readline().rstrip()
t = sys.stdin.readline().rstrip()
l1 = len(s)
l2 = len(t)

DP = lcs_count(s,t)
lcs_string(DP)

Submission status: Time Limit Exceeded

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

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

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

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

ans = ''
i = n
j = m
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()
memo_ls = [[] for i in range(len(S)+1)]
res = ""
for i in range(len(T) + 1):
    memo_ls[0].append(0)
path = dict()
for i in range(len(S)):
    memo_ls[i+1].append(0)
    for j in range(len(T)):
        if S[i] == T[j]:
            cost = max(memo_ls[i][j] + 1, memo_ls[i][j+1], memo_ls[i+1][j])
            memo_ls[i+1].append(cost)
        else:
            memo_ls[i+1].append(max(memo_ls[i][j+1], memo_ls[i+1][j]))

x_ind = len(T)
y_ind = len(S)
while x_ind * y_ind > 0:
    if memo_ls[y_ind][x_ind] == memo_ls[y_ind-1][x_ind]:
        y_ind -= 1
    elif memo_ls[y_ind][x_ind] == memo_ls[y_ind][x_ind-1]:
        x_ind -= 1
    else:
        res += T[x_ind-1]
        x_ind -= 1
        y_ind -= 1
print(res[::-1])

Submission status: Time Limit Exceeded

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_f

def f_lcs(s,t):
    dp=[[0 for x in xrange(len(t)+1)] for x in xrange(len(s)+1)]
    for i in xrange(len(s)+1):
        for j in xrange(len(t)+1):
            if i==0 or j==0:
                dp[i][j]=0
            elif s[i-1]==t[j-1]:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    lenlcs=dp[-1][-1]
    lcs=[""]*(lenlcs+1)
    lcs[lenlcs]=""
    i,j=len(s),len(t)
    while i>0 and j>0:
        if s[i-1]==t[j-1]:
            lcs[lenlcs-1]=s[i-1] 
            i-=1
            j-=1
            lenlcs-=1
        elif dp[i-1][j]>dp[i][j-1]: 
            i-=1
        else: 
            j-=1
    print "".join(lcs)
s=raw_input()
t=raw_input()
f_lcs(s,t)