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:
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] = list(sol[(n-1, m)])
            else:
                sol[state] = list(sol[(n, m-1)])
 
    return memo[state]
  
k = lcs(n, m)

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

Submission status: Time Limit Exceeded

Solution code:

def backtrack(a, memo) : 
    r = len(memo) - 1
    c = len(memo[0]) - 1

    result = ''
    while r > 0 : 
        if memo[r][c] == memo[r - 1][c] : 
            r -= 1
        else : 
            c -= 1
            r -= 1
            result += a[r]

    return result[::-1]


def LCS(a, b) : 
    memo = [[0 for _ in xrange(len(b) + 1)] for _ in xrange(len(a) + 1)]

    for i in xrange(len(a)) :
        for j in xrange(len(b)) : 
            if a[i] == b[j] : 
                memo[i + 1][j + 1] = memo[i][j] + 1
            else : 
                memo[i + 1][j + 1] = max(memo[i][j + 1], memo[i + 1][j])

    return backtrack(a, memo)



a = raw_input().strip()
b = raw_input().strip()

print LCS(a, b)

Submission status: Time Limit Exceeded

Solution code:
x = input()
n1 = len(x)
y = input()
n2 = len(y)
dp = [[0 for i in range(n2+1)] for i in range(n1+1)]
for i in range(1,n1+1):
	for j in range(1,n2+1):
		if(x[i-1] == y[j-1]):
			dp[i][j] = 1 + dp[i-1][j-1]
		else:
			dp[i][j] = max(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
i = n1
j = n2
c = min(n1,n2)
o = ['' for i in range(min(n1,n2))]
while (i>=0 and j>=0):
 	if(dp[i][j] == 1 + dp[i-1][j-1]):
 		i = i-1
 		j = j-1
 		o[c-1] = x[i]
 		c -= 1
 	if(dp[i][j] == dp[i][j-1]):
 		j = j-1
 	if(dp[i][j] == dp[i-1][j]):
 		i = i-1
 	if(dp[i][j] == dp[i-1][j-1]):
 		i = i-1
 		j = j-1
print(''.join(o))

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ls, lt = len(s), len(t)
dp = [[0 for _ in range(lt+1)] for _ in range(ls+1)]
for i in range(1, ls+1):
    for j in range(1, lt+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
i, j = ls, lt
ans = []
while(i > 0 and j > 0):
    if dp[i][j] == dp[i-1][j-1] + 1:
        ans.append(s[i-1])
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1
ans.reverse()
print(str(''.join(ans)))

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ls, lt = len(s), len(t)
dp = [[0 for _ in range(lt+1)] for _ in range(ls+1)]
for i in range(1, ls+1):
    for j in range(1, lt+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = max(dp[i-1][j-1]+1, dp[i-1][j], dp[i][j-1])
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
i, j = ls, lt
ans = []
while(i > 0 and j > 0):
    if dp[i][j] == dp[i-1][j-1] + 1:
        ans.append(s[i-1])
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1
ans.reverse()
print(str(''.join(ans)))

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


s = ''
dp = []
def main():
    global s
    global dp
    s = input()
    t = input()

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

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

    #  print(t)
    #  v = 0
    #  result = ''
    #  print('dp[-1]', dp[-1])
    #  for idx, i in enumerate(dp[-1]):
    #      print(idx, i)
    #      if i == v + 1:
    #          result += t[idx-1]
    #          v += 1

    #  print(result)

    #  lcs_str = ''
    #  i, j = n - 1, m - 1
    #  while i >= 0 and j >= 0:
    #      if s[i] == t[j]:
    #          lcs_str += s[i]
    #          i -= 1
    #          j -= 1
    #      elif dp[i+1][j+1] == 0:
    #          break
    #      else:
    #          if dp[i][j+1] > dp[i+1][j]:
    #              i -= 1
    #          else:
    #              j -= 1

    #  print(lcs_str[::-1])
    print_lcs(n, m)


def print_lcs(i, j):
    global s, dp
    if not i or not j:
        return ''

    ret = dp[i][j]
    if ret == dp[i-1][j]:
        print_lcs(i - 1, j)
    elif ret == dp[i][j-1]:
        print_lcs(i, j-1)
    else:
        print_lcs(i - 1, j - 1)
        print(s[i-1], end='', flush=True)


main()

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


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

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

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

    #  print(t)
    #  v = 0
    #  result = ''
    #  print('dp[-1]', dp[-1])
    #  for idx, i in enumerate(dp[-1]):
    #      print(idx, i)
    #      if i == v + 1:
    #          result += t[idx-1]
    #          v += 1

    #  print(result)

    lcs_str = ''
    i, j = n - 1, m - 1
    while i >= 0 and j >= 0:
        if s[i] == t[j]:
            lcs_str += s[i]
            i -= 1
            j -= 1
        elif dp[i+1][j+1] == 0:
            break
        else:
            if dp[i][j+1] > dp[i+1][j]:
                i -= 1
            else:
                j -= 1

    print(lcs_str[::-1])




main()

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


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

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

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

    #  print(t)
    #  v = 0
    #  result = ''
    #  print('dp[-1]', dp[-1])
    #  for idx, i in enumerate(dp[-1]):
    #      print(idx, i)
    #      if i == v + 1:
    #          result += t[idx-1]
    #          v += 1

    #  print(result)

    lcs_str = ''
    i, j = n - 1, m - 1
    while i >= 0 and j >= 0:
        if s[i] == t[j]:
            lcs_str += s[i]
            i -= 1
            j -= 1
        else:
            if dp[i][j+1] > dp[i+1][j]:
                i -= 1
            else:
                j -= 1

    print(lcs_str[::-1])




main()

Submission status: Time Limit Exceeded

Solution code:


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

l = dp[len(s)][len(t)]
resp = []
inds = len(s)
indt = len(t)
while len(resp) < l:
    if s[inds - 1] == t[indt - 1] and dp[inds][indt] == 1 + dp[inds - 1][indt - 1]:
        resp.append(s[inds - 1])
        inds -= 1
        indt -= 1
        continue
    if dp[inds][indt] == dp[inds - 1][indt - 1]:
        inds -= 1
        indt -= 1
        continue
    if dp[inds][indt] == dp[inds - 1][indt]:
        inds -= 1
        continue
    if dp[inds][indt] == dp[inds][indt - 1]:
        indt -= 1
        continue
resp.reverse()
print(''.join(resp))

Submission status: Time Limit Exceeded

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

dp = [[0 for t in range(len(T)+1)] for s in range(len(S)+1)]
str = []

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])

str_len = 0
fc_s = len(S)
fc_t = len(T)
while dp[fc_s][fc_t] != 0:
    if (dp[fc_s][fc_t] == dp[fc_s - 1][fc_t]):
        fc_s -= 1
    if (dp[fc_s][fc_t] == dp[fc_s][fc_t - 1]):
        fc_t -= 1
    if (dp[fc_s][fc_t] != dp[fc_s - 1][fc_t]) & (dp[fc_s][fc_t] != dp[fc_s][fc_t - 1]):
        str.append(S[fc_s - 1])
        fc_s -= 1
        fc_t -= 1

str = str[::-1]

print(''.join(str))

Submission status: Time Limit Exceeded

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

# minimize
mnmz={ch for ch in s} & {ch for ch in t}
if len(mnmz)==0:
    print("")
    exit()
s=[ z for z in s if z in mnmz ]
t=[ z for z in t if z in mnmz ]
if len(s)>len(t): s, t = t, s

# init
dp=[[0]*len(s) for _ in range(len(t))]

#dp frame

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

#recover string
res=[]
j=len(s)-1
i=len(t)-1
while i>0 and j>0:
    if s[j]==t[i] and dp[i][j]==dp[i-1][j-1]+1:
        res.append(s[j])
        i=i-1
        j=j-1
        continue
    if dp[i][j]==dp[i][j-1]:
        j=j-1
    else: i=i-1
# last letter (first acually)
if i==0:
    res.append(t[0])
elif j==0:
    res.append(s[0])


print("".join(chr(i+97) for i in reversed(res)))

Submission status: Time Limit Exceeded

Solution code:
s=[ord(ch) for ch in input()]
t=[ord(ch) for ch in input()]

# minimize
mnmz={ch for ch in s} & {ch for ch in t}
if len(mnmz)==0:
    print("")
    exit()
s=[ z for z in s if z in mnmz ]
t=[ z for z in t if z in mnmz ]
if len(s)>len(t): s, t = t, s

# init
dp=[[0]*len(s) for _ in range(len(t))]

#dp frame

for i in range(len(s)): 
    if s[i]==t[0]:
        for j in range(i, len(s)):
            dp[0][j]=1
        break
for i in range(len(t)): 
    if s[0]==t[i]:
        for j in range(i, len(t)):
            dp[j][0]=1
        break
#dp
for i in range(1,len(t)):
    for j in range(1, len(s)):
        temp = max(dp[i][j-1], dp[i-1][j])
        if s[j]==t[i]:
            if temp<dp[i-1][j-1]+1:
                temp=dp[i-1][j-1]+1
        dp[i][j]=temp
    if dp[i][-1]==len(s): break

#recover string
res=[]
j=len(s)-1
i=len(t)-1
while i>0 and j>0:
    if s[j]==t[i] and dp[i][j]==dp[i-1][j-1]+1:
        res.append(s[j])
        i=i-1
        j=j-1
        continue
    if dp[i][j]==dp[i][j-1]:
        j=j-1
    else: i=i-1
# last letter (first acually)
if i==0:
    res.append(t[0])
elif j==0:
    res.append(s[0])


print("".join(chr(i) for i in reversed(res)))

Submission status: Time Limit Exceeded

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

# minimize
mnmz={ch for ch in s} & {ch for ch in t}
if len(mnmz)==0:
    print("")
    exit()
s="".join([ z for z in s if z in mnmz])
t="".join([ z for z in t if z in mnmz])
if len(s)>len(t): s, t = t, s

# init
dp=[[0]*len(s) for _ in range(len(t))]

#dp frame

for i in range(len(s)): 
    if s[i]==t[0]:
        for j in range(i, len(s)):
            dp[0][j]=1
        break
for i in range(len(t)): 
    if s[0]==t[i]:
        for j in range(i, len(t)):
            dp[j][0]=1
        break
#dp
for i in range(1,len(t)):
    for j in range(1, len(s)):
        temp = max(dp[i][j-1], dp[i-1][j])
        if s[j]==t[i]:
            if temp<dp[i-1][j-1]+1:
                temp=dp[i-1][j-1]+1
        dp[i][j]=temp
    if dp[i][-1]==len(s): break

#recover string
res=[]
j=len(s)-1
i=len(t)-1
while i>0 and j>0:
    if s[j]==t[i] and dp[i][j]==dp[i-1][j-1]+1:
        res.append(s[j])
        i=i-1
        j=j-1
        continue
    if dp[i][j]==dp[i][j-1]:
        j=j-1
    else: i=i-1
# last letter (first acually)
if i==0:
    res.append(t[0])
elif j==0:
    res.append(s[0])


print("".join(reversed(res)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

dp=[[0 for i in range(3100)] for j in range(3100)]

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][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]

i=n
j=m
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()

H = len(s)
W = len(t)
dp = [[0 for x in range(W+1)] for y in range(H+1)]

for y in range(H) :
    for x in range(W) :
        if s[y] == t[x] :
            dp[y+1][x+1] = dp[y][x]+1
        else :
            dp[y+1][x+1] = max(dp[y+1][x], dp[y][x+1])

ans = ""

while (H > 0) and (W > 0) :
    if dp[H][W] == dp[H-1][W] :
        H -= 1
    elif dp[H][W] == dp[H][W-1] :
        W -= 1
    else :
        H -= 1
        W -= 1
        ans = s[H] + ans

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

lmax = lambda x, y: x if len(x) > len(y) else y

@lru_cache(maxsize=10000)
def lcs(x,y):
    if x == "" or y == "":
        return ""
    elif x[-1] == y[-1]:
        return lcs(x[:-1],y[:-1]) + x[-1]
    else:
        return lmax(lcs(x[:-1],y), lcs(x,y[:-1]))

print(lcs(input(),input()))

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

lmax = lambda x, y: x if len(x) > len(y) else y
dp = dict()

@lru_cache(maxsize=10000)
def lcs(x,y):
    if x == "" or y == "":
        return ""
    elif x[-1] == y[-1]:
        return lcs(x[:-1],y[:-1]) + x[-1]
    else:
        return lmax(lcs(x[:-1],y), lcs(x,y[:-1]))

print(lcs(input(),input()))

Submission status: Time Limit Exceeded

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

lenmax = lambda x, y: x if len(x) > len(y) else y
dp = {("","") : ""}

def lcs(x,y):
    if (x,y) in dp:
        return dp[(x,y)]

    if x == "" or y == "":
        a = ""
    elif x[-1] == y[-1]:
        a = lcs(x[:-1],y[:-1]) + x[-1]
    else:
        a = lenmax(lcs(x[:-1],y), lcs(x,y[:-1]))
    dp[(x,y)] = a
    return a

print(lcs(input(),input()))

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ls = len( s)
lt = len( t)
CNT = [ [0]*(ls+1) for _ in range(lt+1)]
for i in range(1,lt+1):
    for j in range(1,ls+1):
        if s[j-1] == t[i-1]:
            CNT[i][j] = CNT[i-1][j-1]+1
        else:
            if CNT[i][j-1] >= CNT[i-1][j]:
                CNT[i][j] = CNT[i][j-1]
            else:
                CNT[i][j] = CNT[i-1][j]
i = lt
j = ls
ans = ""
while i > 0 and j > 0:
    if t[i-1] == s[j-1]:
        ans += t[i-1]
        i -= 1
        j -= 1
    else:
        if CNT[i-1][j] > CNT[i][j-1]:
            i -= 1
        else:
            j -= 1
print( ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ls = len( s)
lt = len( t)
ANS = [ [""]*(ls+1) for _ in range(lt+1) ]
CNT = [ [0]*(ls+1) for _ in range(lt+1)]
for i in range(1,lt+1):
    for j in range(1,ls+1):
        if s[j-1] == t[i-1]:
            ANS[i][j] = ANS[i-1][j-1]+s[j-1]
            CNT[i][j] = CNT[i-1][j-1]+1
        else:
            if CNT[i][j-1] >= CNT[i-1][j]:
                ANS[i][j] = ANS[i][j-1]
                CNT[i][j] = CNT[i][j-1]
            else:
                ANS[i][j] = ANS[i-1][j]
                CNT[i][j] = CNT[i-1][j]
print( ANS[lt][ls])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ls = len( s)
lt = len( t)
ANS = [ [("", 0)]*(ls+1) for _ in range(lt+1) ]
for i in range(1,lt+1):
    for j in range(1,ls+1):
        if s[j-1] == t[i-1]:
            word, cnt = ANS[i-1][j-1]
            ANS[i][j] = ( word + s[j-1], cnt + 1)
        else:
            wordo, cnto = ANS[i-1][j]
            wordl, cntl = ANS[i][j-1]
            if cnto >= cntl:
                ANS[i][j] = (wordo, cnto)
            else:
                ANS[i][j] = (wordl, cntl)
print( ANS[lt][ls][0])

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM : https://atcoder.jp/contests/dp/submissions/4011183

S,T = input(), input()
S,T = list(map(lambda x: ord(x)-97, S)), list(map(lambda x: ord(x)-97, T))

# print(S,T)

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

for i,s in enumerate(S):
    for j,t in enumerate(T):
        dp[i+1][j+1] = max(
                dp[i][j+1], 
                dp[i+1][j],
                dp[i][j] + (s==t)
                )
res = []

x,y = len(S), len(T)

while x > 0 and y > 0:
    if dp[x][y] == dp[x-1][y]:
        x -= 1
    elif dp[x][y] == dp[x][y-1]:
        y -= 1
    else:
        x -= 1
        y -= 1
        res.append(chr(S[x]+97))
print(''.join(reversed(res)))

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM : https://atcoder.jp/contests/dp/submissions/4011183

S,T = input(), input()

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

for i,s in enumerate(S):
    for j,t in enumerate(T):
        dp[i+1][j+1] = max(
                dp[i][j+1], 
                dp[i+1][j],
                dp[i][j] + int(s==t)
                )
res = []

x,y = len(S), len(T)

while x > 0 and y > 0:
    if dp[x][y] == dp[x-1][y]:
        x -= 1
    elif dp[x][y] == dp[x][y-1]:
        y -= 1
    else:
        x -= 1
        y -= 1
        res.append(S[x])
print(''.join(reversed(res)))

Submission status: Time Limit Exceeded

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


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


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

Submission status: Time Limit Exceeded

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


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


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

Submission status: Time Limit Exceeded

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

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

s="@"+s
t="_"+t


dp=[ [ 0 for j in range(len_t+1) ] for i in range(len_s+1)   ]
S=[ [ "" for j in range(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):
		if s[i]==t[j]:
			dp[i][j]=dp[i-1][j-1]+1
			S[i][j]=S[i-1][j-1]+s[i]
		else:			
			dp[i][j]=max( dp[i-1][j] , dp[i][j-1] )
			if dp[i-1][j]>=dp[i][j-1]:
				S[i][j]=S[i-1][j]
			else:
				S[i][j]=S[i][j-1]


print S[-1][-1]

Submission status: Time Limit Exceeded

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

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

# dp[len(s)][len(t)]
# dp表をつくる
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

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

rev = ""
#復元する
i = len_s
j = len_t
while (i>=1 and j>=1):
  if dp[i][j] == dp[i][j-1]:
    j -=1
  elif dp[i][j] == dp[i-1][j]:
    i -=1
  else:
    rev = t[j-1] + rev
    i -=1
    j -=1

print(rev)

Submission status: Time Limit Exceeded

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

  LS = len(s)
  LT = len(t)
      
  DP = [[[0, 0] for i in range(LT + 1)] for j in range(LS + 1)]
  
  for i in range(LS):
    for j in range(LT):
      a = DP[i+1][j][0]
      b = DP[i][j+1][0]
      if s[i] == t[j]:
        c = DP[i][j][0] + 1
        if max(a, b, c) == c:
          DP[i+1][j+1] = [c, 3]
        elif max(a, b) == b:
          DP[i+1][j+1] = [b, 2]
        else:
          DP[i+1][j+1] = [a, 1]
      else:
        if max(a, b) == b:
          DP[i+1][j+1] = [b, 2]
        else:
          DP[i+1][j+1] = [a, 1]
        
  Ans = ""
  j = LS
  k = LT
  for i in range(DP[j][k][0], 0, -1):
    while True:
      if DP[j][k][1] == 3:
        Ans += t[k-1]
        j -= 1
        k -= 1
        break
      elif DP[j][k][1] == 2:
        j -= 1
      else:
        k -= 1
  print(Ans[::-1])
main()

Submission status: Time Limit Exceeded

Solution code:
a = [0] + list(input())
b = [0] + list(input())
dp = [[''] * (len(b)) for i in range(len(a))]
for i in range(1, len(a)):
    for k in range(1, len(b)):
        if a[i] == b[k]:
            dp[i][k] = dp[i - 1][k - 1] + a[i]
        else:
            if len(dp[i][k - 1]) > len(dp[i - 1][k]): dp[i][k] = dp[i][k - 1]
            else: dp[i][k] = dp[i - 1][k]
print(dp[len(a) - 1][len(b) - 1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jan 19 12:14:33 2019
DP_F
@author: maezawa
"""

s = input()
t = input()

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import itertools as itr

s = input()
t = input()

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

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

for i, j in itr.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:
        dp[i][j] = max(dp[i][j],dp[i-1][j], dp[i][j-1], key=len)
    #print((i,j), dp[i][j])

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-# -*- coding: utf-8 -*-
"""
Created on Sat Jan 19 12:14:33 2019
DP_F
@author: maezawa
"""
import itertools as itr

s = input()
t = input()

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

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

for i, j in itr.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((i,j), dp[i][j])

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

Submission status: Time Limit Exceeded

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_f
#2019-01-14
S = input()
T = input()

#初期化
dp = [[0 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)):
        dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j], dp[i][j] + (S[i] == T[j]))

st = []

x = len(S)
y = len(T)
while x > 0 and y > 0:
    if dp[x][y] == dp[x-1][y]: x -= 1
    elif dp[x][y] == dp[x][y-1]: y -= 1
    else: 
        x -= 1
        y -= 1
        st += S[x]
print("".join(reversed(st)))

Submission status: Time Limit Exceeded

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_f
#2019-01-14
s = input()
t = input()

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

print(LCS(s,t))

Submission status: Time Limit Exceeded

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_f
#2019-01-14
s = input()
t = input()

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)):
      dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j], key=len)
      if S[i]==T[j]:
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+S[i], key=len)
  return dp[len(S)][len(T)]

print(LCS(s,t))

Submission status: Time Limit Exceeded

Solution code:
import itertools
S = input()
T = input()
Ns = len(S)
Nt = len(T)
dp = [['' for _ in range(Nt)] for _ in range(Ns)]
if S[0] == T[0]:
    dp[0][0] = S[0]
for i in range(Ns):
    for j in range(Nt):
        if i and j:
            if S[i] == T[j]:
                dp[i][j] = dp[i - 1][j - 1] + S[i]
            else:
                if len(dp[i][j - 1]) >= len(dp[i - 1][j]):
                    dp[i][j] = dp[i][j - 1]
                else:
                    dp[i][j] = dp[i - 1][j]
        elif i and dp[i - 1][j]:
            dp[i][j] = dp[i - 1][j]
        elif j and dp[i][j - 1]:
            dp[i][j] = dp[i][j - 1]
        elif S[i] == T[j]:
            dp[i][j] = S[i]
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
X = input()
Y = input()
import sys
sys.setrecursionlimit(1000000)
def lcs(s1, s2):
    memo = {}
    parents = {}
    def helper(i, j):
        if (i, j) in memo:
            return memo[(i, j)]
        if i < 0 or j < 0:
            return 0
        if s1[i] == s2[j]:
            f = 1 + helper(i-1, j-1)
        else:
            c1 = helper(i-1, j)
            c2 = helper(i, j-1)
            f = max(c1, c2)
        memo[(i, j)] = f
        return f
    l = helper(len(s1) - 1, len(s2) - 1)
    lcs = []
    s = max(memo.keys(), key=lambda x: memo[x])
    while s in memo:
        i, j = s
        if s1[i] == s2[j]:
            lcs.append(s1[i])
            s = (i-1, j-1)
        else:
            left = (i-1, j) in memo
            up = (i, j-1) in memo
            if left and up:
                if memo[i-1, j] > memo[i, j-1]:
                    s = (i-1, j)
                else:
                    s = (i, j-1)
            elif left:
                s = (i-1, j)
            elif up:
                s = (i, j-1)
            else:
                break
    return ''.join(lcs[::-1])
print(lcs(X, Y))

Submission status: Time Limit Exceeded

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

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

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

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

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