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 = tuple(input())
t = tuple(input())
n = len(s)
m = len(t)

dp = [['']*m for i in range(n)]
if s[0] == t[0]:
    dp[0][0] = s[0]

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

for i in range(1,n):
    for j in range(1,m):
        if s[i] == t[j]:
            dp[i][j] = dp[i-1][j-1] + s[i]
        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 = list(input())
t = list(input())
n = len(s)
m = len(t)

dp = [['']*m for i in range(n)]
if s[0] == t[0]:
    dp[0][0] = s[0]

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

for i in range(1,n):
    for j in range(1,m):
        if s[i] == t[j]:
            dp[i][j] = dp[i-1][j-1] + s[i]
        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:
# coding: utf-8
# Tasks: EDPC(Educational DP Contest) F - LCS

import sys
input = sys.stdin.readline

def f(s, t):
    sl, tl = len(s), 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][0] + 1, dp[i][j][1] + s[i]]
            else:
                dp[i + 1][j + 1] = dp[i + 1][j] \
                    if dp[i + 1][j][0] >= dp[i][j + 1][0] \
                    else dp[i][j + 1]
    return(dp[sl][tl][1])

s, t = [input().rstrip() for _ in range(2)] # 1 <= |s|, |t| <= 3000
print(f(s, t))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 17 09:02:00 2019
DPF3
@author: maezawa
"""

s = input()
t = input()

ns = len(s)
nt = len(t)

dp = [[0 for _ in range(nt+1)] for _ in range(ns+1)]

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

ans = ''
si = ns
ti = nt
while si > 0 and ti > 0:
    if dp[si][ti] == dp[si-1][ti]: 
        si -= 1
    elif dp[si][ti] == dp[si][ti-1]:
        ti -= 1
    else:
        ans = s[si-1] + ans
        si -= 1
        ti -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 17 09:02:00 2019
DPF
@author: maezawa
"""

s = input()
t = input()

ns = len(s)
nt = len(t)

dp = [['' for _ in range(nt+1)] for _ in range(ns+1)]

for si in range(ns):
    for ti in range(nt):
        if s[si] == t[ti]:
            arr = [dp[si][ti]+s[si], dp[si+1][ti], dp[si][ti+1]]
        else:
            arr = [dp[si+1][ti], dp[si][ti+1]]
        dp[si+1][ti+1] = max(arr, key=lambda x: len(x))
        
print(dp[ns][nt])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 17 09:02:00 2019
DPF
@author: maezawa
"""

s = input()
t = input()

ns = len(s)
nt = len(t)

dp = [['' for _ in range(nt+1)] for _ in range(ns+1)]

for si in range(ns):
    for ti in range(nt):
        if s[si] == t[ti]:
            arr = [dp[si][ti]+s[si], dp[si+1][ti], dp[si][ti+1]]
        else:
            arr = [dp[si+1][ti], dp[si][ti+1]]
        arr.sort(key=lambda x: len(x), reverse=True)
        dp[si+1][ti+1] = arr[0]
        
print(dp[ns][nt])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Tasks: EDPC(Educational DP Contest) F - LCS
import sys
input = sys.stdin.readline

def f(s, t):
    sl, tl = len(s), 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 + 1][j], dp[i][j + 1])
    cs = ""
    i, j = sl, tl
    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:
            cs = s[i - 1] + cs
            i -= 1
            j -= 1
    return(cs)

s, t = [input().rstrip() for _ in range(2)] # 1 <= |s|, |t| <= 3000
print(f(s, t))

Submission status: Time Limit Exceeded

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

sl = len(s)
tl = len(t)
rr = [[0]*tl for _ in range(sl)]
t0 = t[0]
for i in range(sl):
  if s[i] == t0:
    for k in range(i, sl):
      rr[k][0] = 1
    break
    
rr0 = rr[0]
s0 = s[0]
for j in range(tl):
  if s0 == t[j]:
    for k in range(j, tl):
      rr0[k] = 1
    break

ttl = [(i, t[i]) for i in range(1,tl)]
for i in range(1, sl):
  rri = rr[i]
  rrij = rr[i-1]
  si = s[i]
  for j, tj in ttl:
    if si == tj:
      rri[j] = rrij[j-1]+1
    else:
      rri[j] = rrij[j]
      if rri[j] < rri[j-1]:
        rri[j] = rri[j-1]
i = sl-1
j = tl-1
r = []
while i >= 0 and j >= 0:
  if s[i] == t[j]:
    r.append(s[i]+97)
    i -= 1
    j -= 1
    continue
  if rr[i][j] == 0:
    break
  if i > 0 and rr[i-1][j] == rr[i][j]:
    i -= 1
  else:
    j -= 1
print(''.join(map(chr,r[::-1])))

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
# dp[i][j] = LCS(s[:i+1],t[:j+1])
dp = [ [( 0 , -1 )]*(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):
        comp = [ dp[i][j-1][0],dp[i-1][j-1][0]+int(s[i-1]==t[j-1]),dp[i-1][j][0]]
        argmax = comp.index(max(comp))
        dp[i][j] = ( comp[argmax] , argmax )

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

print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
# dp[i][j] = LCS(s[:i+1],t[:j+1])
dp = [ [""]*(len(t)+1)  for _ in range(len(s)+1) ]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        incStr = s[i-1] if s[i-1]==t[j-1] else ""
        comp = [ dp[i][j-1],dp[i-1][j-1]+incStr,dp[i-1][j]]
        dp[i][j] = comp[comp.index(max(comp,key=lambda x: len(x)))]


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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/6
Update on 2019/3/6
Solved on 2019/3/
@author: shinjisu
"""


# Educational Dynamic Programming
# import math
import numpy as np


def getInt(): return int(input())


# def getIntList(): return [int(x) for x in input().split()]
def getIntList(): return np.array(input().split(), dtype=np.longlong)


# def zeros(n): return [0]*n
def zeros(n): return np.zeros(n, dtype=np.longlong)


# def getIntLines(n): return [int(input()) for i in range(n)]
def getIntLines(n):
    data = zeros(n)
    for i in range(n):
        data[i] = getInt()
    return data


def getIntMat(n, m):  # n行に渡って、1行にm個の整数
    mat = zeros((n, m))
    for i in range(n):
        mat[i] = getIntList()
    return mat


# def zeros2(n, m): return [zeros(m)]*n # obsoleted zeros((n, m))で代替


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**18


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def lcsLen(S, T, n, m):
    if n == -1 or m == -1:
        return 0
    elif S[n] == T[m]:
        return lcsLen(S, T, n-1, m-1)+1
    else:
        return max(lcsLen(S, T, n-1, m), lcsLen(S, T, n, m-1))


def lcs(S, T, n, m):
    if n == -1 or m == -1:
        return 0, ''
    elif S[n] == T[m]:
        lcstr = lcs(S, T, n-1, m-1)
        return lcstr[0]+1, lcstr[1]+S[n]
    else:
        lcstr1 = lcs(S, T, n-1, m)
        lcstr2 = lcs(S, T, n, m-1)
        if lcstr1[0] > lcstr2[0]:
            lcstr = lcstr1
        else:
            lcstr = lcstr2
        return lcstr


def prob_F_recur():  # LCS - Longest Common Subsequence
    S = input()
    T = input()
    dmp((S, T), 'S, T')
    lenS, lenT = len(S), len(T)
    dmp((lenS, lenT), '(lenS, lenT)')
    lcstr = lcs(S, T, lenS-1, lenT-1)
    dmp(lcstr, 'lcs')
    return lcstr[1]


def prob_F_TLE():  # LCS - Longest Common Subsequence  12/18 TLE
    S = input()
    T = input()
    dmp((S, T), 'S, T')
    lenS, lenT = len(S), len(T)
    dmp((lenS, lenT), '(lenS, lenT)')
    dp = [[[0, ''] for j in range(lenT+1)] for i in range(lenS+1)]
    dmp(dp)
    for i in range(lenS+1):
        for j in range(lenT+1):
            if i == 0 or j == 0:
                pass
            elif S[i-1] == T[j-1]:
                lcstr = dp[i-1][j-1]
                dp[i][j] = lcstr[0]+1, lcstr[1]+S[i-1]
            else:
                lcstr1 = dp[i-1][j]
                lcstr2 = dp[i][j-1]
                if lcstr1[0] > lcstr2[0]:
                    dp[i][j] = lcstr1
                else:
                    dp[i][j] = lcstr2
    dmp(dp)
    lcstr = dp[lenS][lenT]
    dmp(lcstr)
    return lcstr[1]


def lcs_rec2(S, T, n, m, dp):
    if n == 0 or m == 0:
        return ''
    elif S[n-1] == T[m-1]:
        return lcs(S, T, n-1, m-1, dp)+S[n-1]
    elif dp[n-1][m] > dp[n][m-1]:
        return lcs(S, T, n-1, m, dp)
    else:
        return lcs(S, T, n, m-1, dp)


def lcs(S, T, n, m, dp):
    lcstr = ''
    while True:
        if n == 0 or m == 0:
            return lcstr
        elif S[n-1] == T[m-1]:
            dmp(S[n-1])
            lcstr = S[n-1] + lcstr
            n -= 1
            m -= 1
        elif dp[n-1][m] > dp[n][m-1]:
            n -= 1
        else:
            m -= 1


def prob_F():  # LCS - Longest Common Subsequence
    S = input()
    T = input()
    dmp((S, T), 'S, T')
    lenS, lenT = len(S), len(T)
    dmp((lenS, lenT), '(lenS, lenT)')
#    dp = [[0 for j in range(lenT+1)] for i in range(lenS+1)]
    dp = zeros((lenS+1, lenT+1))
    dmp(dp)
    for i in range(lenS+1):
        for j in range(lenT+1):
            if i == 0 or j == 0:
                pass
            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])
    dmp(dp)
    return dmp(lcs(S, T, lenS, lenT, dp))


debug = False  # True False
ans = prob_F()
print(ans)
#for row in ans:
#    print(row)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/6
Update on 2019/3/6
Solved on 2019/3/
@author: shinjisu
"""


# Educational Dynamic Programming
# import math
import numpy as np


def getInt(): return int(input())


# def getIntList(): return [int(x) for x in input().split()]
def getIntList(): return np.array(input().split(), dtype=np.longlong)


# def zeros(n): return [0]*n
def zeros(n): return np.zeros(n, dtype=np.longlong)


# def getIntLines(n): return [int(input()) for i in range(n)]
def getIntLines(n):
    data = zeros(n)
    for i in range(n):
        data[i] = getInt()
    return data


def getIntMat(n, m):  # n行に渡って、1行にm個の整数
    mat = zeros((n, m))
    for i in range(n):
        mat[i] = getIntList()
    return mat


# def zeros2(n, m): return [zeros(m)]*n # obsoleted zeros((n, m))で代替


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**18


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def lcsLen(S, T, n, m):
    if n == -1 or m == -1:
        return 0
    elif S[n] == T[m]:
        return lcsLen(S, T, n-1, m-1)+1
    else:
        return max(lcsLen(S, T, n-1, m), lcsLen(S, T, n, m-1))


def lcs(S, T, n, m):
    if n == -1 or m == -1:
        return 0, ''
    elif S[n] == T[m]:
        lcstr = lcs(S, T, n-1, m-1)
        return lcstr[0]+1, lcstr[1]+S[n]
    else:
        lcstr1 = lcs(S, T, n-1, m)
        lcstr2 = lcs(S, T, n, m-1)
        if lcstr1[0] > lcstr2[0]:
            lcstr = lcstr1
        else:
            lcstr = lcstr2
        return lcstr


def prob_F_recur():  # LCS - Longest Common Subsequence
    S = input()
    T = input()
    dmp((S, T), 'S, T')
    lenS, lenT = len(S), len(T)
    dmp((lenS, lenT), '(lenS, lenT)')
    lcstr = lcs(S, T, lenS-1, lenT-1)
    dmp(lcstr, 'lcs')
    return lcstr[1]


def prob_F_TLE():  # LCS - Longest Common Subsequence  12/18 TLE
    S = input()
    T = input()
    dmp((S, T), 'S, T')
    lenS, lenT = len(S), len(T)
    dmp((lenS, lenT), '(lenS, lenT)')
    dp = [[[0, ''] for j in range(lenT+1)] for i in range(lenS+1)]
    dmp(dp)
    for i in range(lenS+1):
        for j in range(lenT+1):
            if i == 0 or j == 0:
                pass
            elif S[i-1] == T[j-1]:
                lcstr = dp[i-1][j-1]
                dp[i][j] = lcstr[0]+1, lcstr[1]+S[i-1]
            else:
                lcstr1 = dp[i-1][j]
                lcstr2 = dp[i][j-1]
                if lcstr1[0] > lcstr2[0]:
                    dp[i][j] = lcstr1
                else:
                    dp[i][j] = lcstr2
    dmp(dp)
    lcstr = dp[lenS][lenT]
    dmp(lcstr)
    return lcstr[1]


def lcs(S, T, n, m, dp):
    if n == 0 or m == 0:
        return ''
    elif S[n-1] == T[m-1]:
        return lcs(S, T, n-1, m-1, dp)+S[n-1]
    elif dp[n-1][m] > dp[n][m-1]:
        return lcs(S, T, n-1, m, dp)
    else:
        return lcs(S, T, n, m-1, dp)


def prob_F():  # LCS - Longest Common Subsequence
    S = input()
    T = input()
    dmp((S, T), 'S, T')
    lenS, lenT = len(S), len(T)
    dmp((lenS, lenT), '(lenS, lenT)')
#    dp = [[0 for j in range(lenT+1)] for i in range(lenS+1)]
    dp = zeros((lenS+1, lenT+1))
    dmp(dp)
    for i in range(lenS+1):
        for j in range(lenT+1):
            if i == 0 or j == 0:
                pass
            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])
    dmp(dp)
    return dmp(lcs(S, T, lenS, lenT, dp))


debug = False  # True False
ans = prob_F()
print(ans)
#for row in ans:
#    print(row)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/6
Update on 2019/3/6
Solved on 2019/3/
@author: shinjisu
"""


# Educational Dynamic Programming
# import math
import numpy as np


def getInt(): return int(input())


# def getIntList(): return [int(x) for x in input().split()]
def getIntList(): return np.array(input().split(), dtype=np.longlong)


# def zeros(n): return [0]*n
def zeros(n): return np.zeros(n, dtype=np.longlong)


# def getIntLines(n): return [int(input()) for i in range(n)]
def getIntLines(n):
    data = zeros(n)
    for i in range(n):
        data[i] = getInt()
    return data


def getIntMat(n, m):  # n行に渡って、1行にm個の整数
    mat = zeros((n, m))
    for i in range(n):
        mat[i] = getIntList()
    return mat


# def zeros2(n, m): return [zeros(m)]*n # obsoleted zeros((n, m))で代替


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**18


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def lcsLen(S, T, n, m):
    if n == -1 or m == -1:
        return 0
    elif S[n] == T[m]:
        return lcsLen(S, T, n-1, m-1)+1
    else:
        return max(lcsLen(S, T, n-1, m), lcsLen(S, T, n, m-1))


def lcs(S, T, n, m):
    if n == -1 or m == -1:
        return 0, ''
    elif S[n] == T[m]:
        lcstr = lcs(S, T, n-1, m-1)
        return lcstr[0]+1, lcstr[1]+S[n]
    else:
        lcstr1 = lcs(S, T, n-1, m)
        lcstr2 = lcs(S, T, n, m-1)
        if lcstr1[0] > lcstr2[0]:
            lcstr = lcstr1
        else:
            lcstr = lcstr2
        return lcstr


def prob_F_recur():  # LCS - Longest Common Subsequence
    S = input()
    T = input()
    dmp((S, T), 'S, T')
    lenS, lenT = len(S), len(T)
    dmp((lenS, lenT), '(lenS, lenT)')
    lcstr = lcs(S, T, lenS-1, lenT-1)
    dmp(lcstr, 'lcs')
    return lcstr[1]


def prob_F():  # LCS - Longest Common Subsequence
    S = input()
    T = input()
    dmp((S, T), 'S, T')
    lenS, lenT = len(S), len(T)
    dmp((lenS, lenT), '(lenS, lenT)')
    dp = [[[0, ''] for j in range(lenT+1)] for i in range(lenS+1)]
    dmp(dp)
    for i in range(lenS+1):
        for j in range(lenT+1):
            if i == 0 or j == 0:
                pass
            elif S[i-1] == T[j-1]:
                lcstr = dp[i-1][j-1]
                dp[i][j] = lcstr[0]+1, lcstr[1]+S[i-1]
            else:
                lcstr1 = dp[i-1][j]
                lcstr2 = dp[i][j-1]
                if lcstr1[0] > lcstr2[0]:
                    dp[i][j] = lcstr1
                else:
                    dp[i][j] = lcstr2
    dmp(dp)
    lcstr = dp[lenS][lenT]
    dmp(lcstr)
    return lcstr[1]


debug = False  # True False
ans = prob_F()
print(ans)
#for row in ans:
#    print(row)

Submission status: Time Limit Exceeded

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

# dp[i][j] : 文字列Sのi文字目までと文字列Tのj文字目まで(Sの最後index, Tの最後index, 値)

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

dp[0][0] = (0,"")

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

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

ans = ""

ind_x = len(T)
ind_y = len(S)

while ind_x * ind_y :
    if S[ind_y-1] == T[ind_x-1] :
        ans = S[ind_y-1] + ans
        ind_x -= 1
        ind_y -= 1
    elif dp[ind_y][ind_x] == dp[ind_y-1][ind_x] :
        ind_y -= 1
    else :
        ind_x -= 1
    

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(s, t):
    # 1-origin
    s_size, t_size = len(s), len(t)
    dp = [[0] * (t_size + 1) for _ in range(s_size + 1)]

    for i in range(1, s_size + 1):
        for j in range(1, t_size + 1):
            prev_i, prev_j = i - 1, j - 1
            dp[i][j] = max(dp[prev_i][j], dp[i][prev_j])
            if s[prev_i] != t[prev_j]:
                # 不一致
                continue
            if dp[prev_i][prev_j] + 1 <= dp[i][j]:
                # maxを超えないとき
                continue
            dp[i][j] = dp[prev_i][prev_j] + 1

    # 文字復元
    buff = []
    s_key, t_key = s_size, t_size
    while s_key > 0 and t_key > 0:
        prev_s, prev_t = s_key - 1, t_key - 1
        if s[prev_s] == t[prev_t]:
            buff.append(s[prev_s])
            s_key -= 1
            t_key -= 1
            continue
        if dp[s_key][t_key] == 0:
            break
        if s_key > 0 and dp[s_key][t_key] == dp[prev_s][t_key]:
            s_key -= 1
        else:
            t_key -= 1

    return "".join(buff[::-1])


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

    ans = solve(s, t)
    print(ans)


main()

Submission status: Time Limit Exceeded

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

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

i = len_s
j = len_t
res = ""
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        res += s[i-1]
        i -= 1
        j -= 1

print(res[::-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

input = sys.stdin.readline
s = list(input())[:-1]
t = list(input())[:-1]

INF = 10 ** 18
dp = [[0] * int(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] = max(dp[i][j] + 1, 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])

res = ""
i = len(t)
j = len(s)

while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        res = t[i-1] + res
        i -= 1
        j -= 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
###modular exponentiation: a^n % M
#pow(a, n, M) 
### gcd: gcd(a, b)
#import fractions
#fractions.gcd(a, b)
### LCM (M, N)
#lcm = M*N/fractions.gcd(M, N)
INF = 1000000000+5

def get_lcs(s, t):
    '''
    >> get_lcs('acbdi', 'cdxbdx')
    'cbdi'
           i
      0 c d x b d x
    0 0
    a 0
    c 0
  j b      max(1+L[i-1][j-1], L[i-1][j], L[i][j-1])
    d
    x
    '''
    def diff(i, j):
        if s[i-1] == t[j-1]:
            return 1
        else:
            return 0
    M = len(s)
    N = len(t)
    DP = []
    parent = []
    for i in range(M+1):
        DP.append([0]*(N+1))
        parent.append([0]*(N+1))
    parent[0][0] = (-1, -1)
    for i in range(1, M+1):
        for j in range(1, N+1):
            DP[i][j] = max(DP[i][j-1], DP[i-1][j], DP[i-1][j-1] + diff(i, j))
            if DP[i][j] == DP[i-1][j-1]+1:
                parent[i][j] = (i-1, j-1)
            elif DP[i][j] == DP[i-1][j]:
                parent[i][j] = (i-1, j)
            else:
                parent[i][j] = (i, j-1)
#    for row in DP:
#        print(row)
    i, j = M, N
    result = ''
    while i > 0 and j > 0:
        if parent[i][j] == (-1, -1):
            break
        if parent[i][j] == (i-1, j-1):
            result = s[i-1] + result
            i, j = (i-1, j-1)
        else:
            i, j = parent[i][j]
    return result




s = input()
t = input()
result = get_lcs(s, t)
print("{}".format(result))

Submission status: Time Limit Exceeded

Solution code:
class Solution(object):
    def lcs(self, a, b):
        dp = [[[0,[]] for _ in range(len(b)+1)] for _ in range(len(a)+1)]
        # print(dp[0][0][0], dp[0][0][1])

        for i in range(len(a)):
            curr_a = a[i]
            for j in range(len(b)):
                curr_b = b[j]
                if curr_a == curr_b:
                    dp[i+1][j+1][0] = dp[i][j][0]+1
                    dp[i+1][j+1][1] =  dp[i][j][1] + [curr_a]
                else:
                    dp[i+1][j+1][0] = max(dp[i][j+1][0], dp[i+1][j][0])
                    if dp[i][j+1][0] > dp[i+1][j][0]:
                        dp[i+1][j+1][1] += dp[i][j+1][1]
                    else:
                        dp[i+1][j+1][1] += dp[i+1][j][1]

        return "".join(dp[-1][-1][1])










if __name__ == '__main__':
    a = str(input())
    b = str(input())
    sol = Solution()
    res = sol.lcs(a, b)
    print(res)

Submission status: Time Limit Exceeded

Solution code:
S=input()
T=input()
s=len(S)
t=len(T)
dp=[['' for i in range(t+1)] for j in range(s+1)]
for i in range(s):
    for j in range(t):
        if S[i]!=T[j]:
            dp[i+1][j+1]=dp[i+1][j]
            if len(dp[i][j+1])>len(dp[i+1][j]):
                dp[i+1][j+1]=dp[i][j+1]
            continue
        dp[i+1][j+1]=dp[i][j]+S[i]
print(dp[s][t])

Submission status: Time Limit Exceeded

Solution code:
S=input()
T=input()
s=len(S)
t=len(T)
dp=[['' for i in range(t+1)] for j in range(s+1)]
for i in range(s):
    for j in range(t):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+S[i]
            continue
        dp[i+1][j+1]=dp[i+1][j]
        if len(dp[i][j+1])>len(dp[i+1][j]):
            dp[i+1][j+1]=dp[i][j+1]
print(dp[s][t])

Submission status: Time Limit Exceeded

Solution code:
S=input()
T=input()
s=len(S)
t=len(T)
dp=[['' for i in range(t+1)] for j in range(s+1)]
for i in range(s):
    for j in range(t):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+S[i]
        else:
            dp[i+1][j+1]=dp[i+1][j]
            if len(dp[i][j+1])>len(dp[i+1][j]):
                dp[i+1][j+1]=dp[i][j+1]
print(dp[s][t])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

aa = len(a)

bb = len(b)

dp = [[0]*(bb+1) for i in range(aa+1)]

for i in range(aa):
	for j in range(bb):
		if a[i] == b[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 aa > 0 and bb > 0:
	if a[aa-1] == b[bb-1]:
		aa -= 1
		bb -= 1
		ans += a[aa]
	elif dp[aa][bb-1] > dp[aa-1][bb]:
		bb -= 1
	else:
		aa -= 1
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
def LCS(S,T):
    #初期化
    dp=[['' for i in range(len(T)+1)] for j in range(len(S)+1)]

    #DP
    for i in range(len(S)):
        for j in range(len(T)):

            if len(dp[i][j+1]) <= len(dp[i+1][j]):
                dp[i+1][j+1]=dp[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]
      
            if S[i]==T[j]:
                if len(dp[i+1][j+1]) <= len(dp[i][j])+1:
                    dp[i+1][j+1]=dp[i][j] + S[i]
                else:
                    dp[i+1][j+1]=dp[i+1][j+1]
    return dp[len(S)][len(T)]

S = input()
T = input()

lenS = len(S)
lenT = len(T)

print(LCS(S,T))

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
n = len(S)
m = len(T)

DP = [[''] * (m+1) for i 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:
            DP[i+1][j+1] = DP[i+1][j] if len(DP[i+1][j]) > len(DP[i][j+1]) else DP[i][j+1]
        
print(DP[n][m])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
s_len = len(s)
t_len = len(t)

# dp[i][j] = sのi文字目、tのj文字目までの最大長の部分文字列
dp = [['' for j in range(t_len + 1)] for i in range(s_len + 1)]
for si in range(1, s_len + 1):
    for ti in range(1, t_len + 1):
        dp_len = len(dp[si][ti])
        if s[si - 1] == t[ti - 1]:
            if dp_len < len(dp[si - 1][ti - 1] + s[si - 1]):
                dp[si][ti] = dp[si - 1][ti - 1] + s[si - 1]
                dp_len = len(dp[si][ti])
        if dp_len < len(dp[si - 1][ti]):
            dp[si][ti] = dp[si - 1][ti]
            dp_len = len(dp[si][ti])
        if dp_len < len(dp[si][ti - 1]):
            dp[si][ti] = dp[si][ti - 1]
print(dp[s_len][t_len])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
s_len = len(s)
t_len = len(t)

# dp[i][j] = sのi文字目、tのj文字目までの最大長の部分文字列
dp = [['' for j in range(t_len + 1)] for i in range(s_len + 1)]
for si in range(1, s_len + 1):
    for ti in range(1, t_len + 1):
        if s[si - 1] == t[ti - 1]:
            if len(dp[si][ti]) < len(dp[si - 1][ti - 1] + s[si - 1]):
                dp[si][ti] = dp[si - 1][ti - 1] + s[si - 1]
        if len(dp[si][ti]) < len(dp[si - 1][ti]):
            dp[si][ti] = dp[si - 1][ti]
        if len(dp[si][ti]) < len(dp[si][ti - 1]):
            dp[si][ti] = dp[si][ti - 1]
print(dp[s_len][t_len])

Submission status: Time Limit Exceeded

Solution code:

S = input()
T = input()
N = len(S)
M = len(T)

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

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

i = N
j = M
cnt = dp[N][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:
        i -= 1 ; j -= 1
        res.append(S[i])
# while cnt :
#     while cnt == dp[i][j]:
#         i -= 1
#     i += 1
#     while cnt == dp[i][j]:
#         j -= 1
#     j += 1
#     res.append(S[i-1])
#     cnt -= 1
#     i -= 1; j -= 1
print("".join(reversed(res)))

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
N = len(S)
M = len(T)

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

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

i = N
j = M
cnt = dp[N][M]
while cnt :
    while cnt == dp[i][j]:
        i -= 1
    i += 1
    while cnt == dp[i][j]:
        j -= 1
    j += 1
    res.append(S[i-1])
    cnt -= 1
    i -= 1; j -= 1
print("".join(reversed(res)))

Submission status: Time Limit Exceeded

Solution code:
s1 = raw_input()
n = len(s1)
s2 = raw_input()
m = len(s2)

import sys
sys.setrecursionlimit(10**5)
 
memo = {}
sol = {}
 
def lcs(n, m): ##1 index
    state = (n, m)
 
    if state not in memo:
        if n <= 0 or m <= 0:
            memo[state] = 0
            sol[state] = list()
            return 0
            
        if s1[n-1] == s2[m-1]:
            memo[state] = 1+lcs(n-1, m-1)
            sol[state] = [s1[n-1]]+sol[(n-1, m-1)]
                                          
        else:
            memo[state] = max(lcs(n-1, m), lcs(n, m-1))
            if memo[state] == memo[(n-1, m)]:
                sol[state] = sol[(n-1, m)]
            else:
                sol[state] = sol[(n, m-1)]
 
    return memo[state]
  
k = lcs(n, m)

ss = sol[(n,m)]
ss.reverse()
print ''.join(ss)