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:
#!/usr/bin/env python3
import sys
def S(): return list(sys.stdin.readline())[:-1]
def f():
    s = S()
    t = S()
    ls = len(s)
    lt = len(t)
    dp = [[0]*(ls+1) for _ in range(lt+1)]
    for i in range(lt):
        for j in range(ls):
            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])

    ans = ""
    while lt > 0 and ls > 0:
        if dp[lt][ls] == dp[lt-1][ls]:
            lt -= 1
        elif dp[lt][ls] == dp[lt][ls-1]:
            ls -= 1
        elif dp[lt][ls] == dp[lt-1][ls-1] + 1:
            ans += t[lt-1]
            lt -= 1
            ls -= 1
    print(ans[::-1])

if __name__ == '__main__':
    f()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def f():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)
    dp = [[0]*(ls+1) for _ in range(lt+1)]

    for i,T in enumerate(t):
        for j,S in enumerate(s):
            if T == S:
                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 = ""
    ti = lt
    sj = ls
    while ti > 0 and sj > 0:
        if dp[ti][sj] == dp[ti-1][sj]:
            ti -= 1
        elif dp[ti][sj] == dp[ti][sj-1]:
            sj -= 1
        elif dp[ti][sj] == dp[ti-1][sj-1] + 1:
            ans += t[ti-1]
            ti -= 1
            sj -= 1
    print(ans[::-1])

if __name__ == '__main__':
    f()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0]*(ls+1) for _ in range(lt+1)]

for i,T in enumerate(t):
    for j,S in enumerate(s):
        if T == S:
            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 = ""
ti = lt
sj = ls
while ti > 0 and sj > 0:
    if dp[ti][sj] == dp[ti-1][sj]:
        ti -= 1
    elif dp[ti][sj] == dp[ti][sj-1]:
        sj -= 1
    elif dp[ti][sj] == dp[ti-1][sj-1] + 1:
        ans += t[ti-1]
        ti -= 1
        sj -= 1
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0 for _ in range(ls+1)] for _ in range(lt+1)]

for i in range(lt):
    for j in range(ls):
        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])

ans = ""
ti = lt
sj = ls
while ti > 0 and sj > 0:
    if dp[ti][sj] == dp[ti-1][sj]:
        ti -= 1
    elif dp[ti][sj] == dp[ti][sj-1]:
        sj -= 1
    elif dp[ti][sj] == dp[ti-1][sj-1] + 1:
        ans += t[ti-1]
        ti -= 1
        sj -= 1
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    n = I()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n-2):
        dp[i+1] = min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
        dp[i+2] = min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
    dp[n-1] = min(dp[n-1],dp[n-2]+abs(h[n-1]-h[n-2]))
    print(dp[n-1])
#B
def B():
    n,k = LI()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,min(n-i,k+1)):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
    print(dp[n-1])

#C
def C():
    n = I()
    v = LIR(n)
    dp = [[0,0,0] for i in range(n+1)]
    for i in range(n):
        dp[i+1][0] = max(dp[i+1][0],dp[i][1]+v[i][0],dp[i][2]+v[i][0])
        dp[i+1][1] = max(dp[i+1][1],dp[i][2]+v[i][1],dp[i][0]+v[i][1])
        dp[i+1][2] = max(dp[i+1][2],dp[i][0]+v[i][2],dp[i][1]+v[i][2])
    print(max(dp[n]))

#D
def D():
    n,W = LI()
    g = LIR(n)
    dp = [[0 for i in range(W+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(W+1)[::-1]:
            w,v = g[i]
            if j >= w:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
            else:
                dp[i+1][j] = max(dp[i+1][j],dp[i][j])
    print(max(dp[n]))
#E
def E():
    n,W = LI()
    g = LIR(n)
    V = 100000
    dp = [[float("inf") for i in range(V+1)] for j in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(V+1)[::-1]:
            w,v = g[i]
            if j >= v:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
            else:
                dp[i+1][j] = min(dp[i+1][j],dp[i][j])

    for i in range(V+1)[::-1]:
        if dp[n][i] <= W:
            print(i)
            quit()

#F
def F():
    s = S()
    t = S()
    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] = max(dp[i][j]+1,dp[i+1][j],dp[i][j+1])
            else:
                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])

    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:
            i -= 1
            j -= 1
            ans = s[i]+ans
    print(ans)
#G
def G():
    n,m = LI()
    e = LIR(m)
    dp = [0 for j in range(m+1)]
    for i in range(m):
        x,y = e[i]
        dp[i+1][y] = max(dp[i][y],dp[i][x]+1)
    ans = 0
    for i in range(m+1):
        ans = max(dp[i])
    print(ans)
#H
def H():
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
def factorial(n):
    if (n==0) or (n==1):
        return 1
    ret = 1
    for i in range(2, n+1):
        ret *= i
    return ret
def combination(n, k):
    return factorial(n)//factorial(k)//factorial(n-k)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

s = S()
t = S()

#dp[s][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])

i = len(s)
j = len(t)
res = ""
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 = s[i] + res

print(res)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
def factorial(n):
    if (n==0) or (n==1):
        return 1
    ret = 1
    for i in range(2, n+1):
        ret *= i
    return ret
def combination(n, k):
    return factorial(n)//factorial(k)//factorial(n-k)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

s = S()
t = S()

#dp[s][t]
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:
            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[len(s)][len(t)])

Submission status: Time Limit Exceeded

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

lens=len(s)
lent=len(t)

dp=[[0]*(lent+1) for _ in range(lens+1)]

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

ans=''
i,j=lens,lent

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
F - LCS
https://atcoder.jp/contests/dp/tasks/dp_f

"""
import sys


def solve(s, t):
    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
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    ans = []
    y, x = n, m
    lcs = dp[y][x]
    while x > 0 or y > 0:
        if y-1 >= 0 and dp[y-1][x] == lcs:
            y -= 1
        elif x-1 >= 0 and dp[y][x-1] == lcs:
            x -= 1
        else:
            y -= 1
            x -= 1
            ans.append(s[y])
            lcs -= 1
    return ''.join(ans[::-1])


def main(args):
    s = input()
    t = input()
    ans = solve(s, t)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

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

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

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

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 = t[lt-1] + ans
        ls -= 1
        lt -= 1

print(ans)

Submission status: Time Limit Exceeded

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

# dp = np.zeros(shape=(len(s), len(t)), dtype=np.int64)
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] = max(dp[i+1][j+1], dp[i][j]+1)
        else:
            dp[i+1][j+1] = max(dp[i+1][j+1], max(dp[i][j+1], dp[i+1][j]))

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


i = len(s)
j = len(t)
# print(type(i))
# print(type(j))
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]
        i -= 1
        j -= 1

print(ans[::-1])

Submission status: Time Limit Exceeded

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

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

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

def find_left_most(i, j, v):
    a = i
    b = j

    while dp[a][b] == v:
        b -= 1
    b += 1

    while dp[a][b] == v:
        a -= 1
    a += 1

    return (a,b)
# print(dp)

s = []
i,j = len(S),len(T)
for v in range(max_len, 0, -1):
    i,j = find_left_most(i,j,v)
    s.append(S[i-1])
    i-=1
    j-=1

s.reverse()
print(''.join(s))

Submission status: Time Limit Exceeded

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

lens = len(s)
lent = len(t)

# dp = [[None] * lent for _ in range(lens)]
# def dfs(aindex=0, bindex=0):
#     if aindex >= lens:
#         return 0
#     if bindex >= lent:
#         return 0
#
#     if dp[aindex][bindex] is not None:
#         return dp[aindex][bindex]
#
#     if s[aindex] == t[bindex]:
#         r = dfs(aindex + 1, bindex + 1) + 1
#     else:
#         r = max(dfs(aindex + 1, bindex), dfs(aindex, bindex + 1))
#     dp[aindex][bindex] = r
#     return r
#
# print(dfs())

shift = [1 << x for x in range(3000 + 1)]

dp = [[0] * (lent + 1) for _ in range(lens + 1)]
# pattern = [[0] * (lent + 1) for _ in range(lens + 1)]
pattern = [[[0] * 3000 for _ in range(lent + 1)] for _ in range(lens + 1)]
# dp = [[(0, 0) for _ in range(lent + 1)] for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            r = dp[aindex + 1][bindex + 1] + 1
            # p = s[aindex] + pattern[aindex + 1][bindex + 1]
            # p = (1 << aindex) + pattern[aindex + 1][bindex + 1]
            p = pattern[aindex + 1][bindex + 1][:]
            p[aindex] += 1
        else:
            if dp[aindex + 1][bindex] > dp[aindex][bindex + 1]:
                r = dp[aindex + 1][bindex]
                p = pattern[aindex + 1][bindex]
            else:
                r = dp[aindex][bindex + 1]
                p = pattern[aindex][bindex + 1]
            # r = max(dp[aindex + 1][bindex], dp[aindex][bindex + 1])
        dp[aindex][bindex] = r
        pattern[aindex][bindex] = p
for aindex in range(lens):
    if pattern[0][0][aindex]:
        print(s[aindex], end="")

Submission status: Time Limit Exceeded

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

lens = len(s)
lent = len(t)

# dp = [[None] * lent for _ in range(lens)]
# def dfs(aindex=0, bindex=0):
#     if aindex >= lens:
#         return 0
#     if bindex >= lent:
#         return 0
#
#     if dp[aindex][bindex] is not None:
#         return dp[aindex][bindex]
#
#     if s[aindex] == t[bindex]:
#         r = dfs(aindex + 1, bindex + 1) + 1
#     else:
#         r = max(dfs(aindex + 1, bindex), dfs(aindex, bindex + 1))
#     dp[aindex][bindex] = r
#     return r
#
# print(dfs())

shift = [1 << x for x in range(3000 + 1)]

dp = [[0] * (lent + 1) for _ in range(lens + 1)]
pattern = [[0] * (lent + 1) for _ in range(lens + 1)]
# dp = [[(0, 0) for _ in range(lent + 1)] for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            r = dp[aindex + 1][bindex + 1] + 1
            # p = s[aindex] + pattern[aindex + 1][bindex + 1]
            # p = (1 << aindex) + pattern[aindex + 1][bindex + 1]
            p = shift[aindex] + pattern[aindex + 1][bindex + 1]
        else:
            if dp[aindex + 1][bindex] > dp[aindex][bindex + 1]:
                r = dp[aindex + 1][bindex]
                p = pattern[aindex + 1][bindex]
            else:
                r = dp[aindex][bindex + 1]
                p = pattern[aindex][bindex + 1]
            # r = max(dp[aindex + 1][bindex], dp[aindex][bindex + 1])
        dp[aindex][bindex] = r
        pattern[aindex][bindex] = p
for aindex in range(lens):
    if (1 << aindex) & pattern[0][0]:
        print(s[aindex], end="")
# print()
# print(dp[0])
# print(pattern[0])

Submission status: Time Limit Exceeded

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

lens = len(s)
lent = len(t)

# dp = [[None] * lent for _ in range(lens)]
# def dfs(aindex=0, bindex=0):
#     if aindex >= lens:
#         return 0
#     if bindex >= lent:
#         return 0
#
#     if dp[aindex][bindex] is not None:
#         return dp[aindex][bindex]
#
#     if s[aindex] == t[bindex]:
#         r = dfs(aindex + 1, bindex + 1) + 1
#     else:
#         r = max(dfs(aindex + 1, bindex), dfs(aindex, bindex + 1))
#     dp[aindex][bindex] = r
#     return r
#
# print(dfs())

dp = [[0] * (lent + 1) for _ in range(lens + 1)]
pattern = [[0] * (lent + 1) for _ in range(lens + 1)]
# dp = [[(0, 0) for _ in range(lent + 1)] for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            r = dp[aindex + 1][bindex + 1] + 1
            # p = s[aindex] + pattern[aindex + 1][bindex + 1]
            # p = (1 << aindex) + pattern[aindex + 1][bindex + 1]
            p = (2**aindex) + pattern[aindex + 1][bindex + 1]
        else:
            if dp[aindex + 1][bindex] > dp[aindex][bindex + 1]:
                r = dp[aindex + 1][bindex]
                p = pattern[aindex + 1][bindex]
            else:
                r = dp[aindex][bindex + 1]
                p = pattern[aindex][bindex + 1]
            # r = max(dp[aindex + 1][bindex], dp[aindex][bindex + 1])
        dp[aindex][bindex] = r
        pattern[aindex][bindex] = p
for aindex in range(lens):
    if (1 << aindex) & pattern[0][0]:
        print(s[aindex], end="")
# print()
# print(dp[0])
# print(pattern[0])

Submission status: Time Limit Exceeded

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

lens = len(s)
lent = len(t)

dp = [[None] * lent for _ in range(lens)]
# def dfs(aindex=0, bindex=0):
#     if aindex >= lens:
#         return 0
#     if bindex >= lent:
#         return 0
#
#     if dp[aindex][bindex] is not None:
#         return dp[aindex][bindex]
#
#     if s[aindex] == t[bindex]:
#         r = dfs(aindex + 1, bindex + 1) + 1
#     else:
#         r = max(dfs(aindex + 1, bindex), dfs(aindex, bindex + 1))
#     dp[aindex][bindex] = r
#     return r
#
# print(dfs())

dp = [[0] * (lent + 1) for _ in range(lens + 1)]
pattern = [[0] * (lent + 1) for _ in range(lens + 1)]
# dp = [[(0, 0) for _ in range(lent + 1)] for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            r = dp[aindex + 1][bindex + 1] + 1
            # p = s[aindex] + pattern[aindex + 1][bindex + 1]
            p = (1 << aindex) + pattern[aindex + 1][bindex + 1]
        else:
            if dp[aindex + 1][bindex] > dp[aindex][bindex + 1]:
                r = dp[aindex + 1][bindex]
                p = pattern[aindex + 1][bindex]
            else:
                r = dp[aindex][bindex + 1]
                p = pattern[aindex][bindex + 1]
            # r = max(dp[aindex + 1][bindex], dp[aindex][bindex + 1])
        dp[aindex][bindex] = r
        pattern[aindex][bindex] = p
for aindex in range(lens):
    if (1 << aindex) & pattern[0][0]:
        print(s[aindex], end="")
# print()
# print(dp[0])
# print(pattern[0])

Submission status: Time Limit Exceeded

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

lens = len(s)
lent = len(t)

dp = [[None] * lent for _ in range(lens)]
# def dfs(aindex=0, bindex=0):
#     if aindex >= lens:
#         return 0
#     if bindex >= lent:
#         return 0
#
#     if dp[aindex][bindex] is not None:
#         return dp[aindex][bindex]
#
#     if s[aindex] == t[bindex]:
#         r = dfs(aindex + 1, bindex + 1) + 1
#     else:
#         r = max(dfs(aindex + 1, bindex), dfs(aindex, bindex + 1))
#     dp[aindex][bindex] = r
#     return r
#
# print(dfs())

dp = [[(0, 0)] * (lent + 1) for _ in range(lens + 1)]
# dp = [[(0, 0) for _ in range(lent + 1)] for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            length, pattern = dp[aindex + 1][bindex + 1]
            r = (length + 1, pattern | (2 << aindex))
        else:
            if dp[aindex + 1][bindex][0] > dp[aindex][bindex + 1][0]:
                r = dp[aindex + 1][bindex]
            else:
                r = dp[aindex][bindex + 1]
        dp[aindex][bindex] = r
for aindex in range(lens):
    if (2 << aindex) & dp[0][0][1]:
        print(s[aindex], end="")
print()

Submission status: Time Limit Exceeded

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

lens = len(s)
lent = len(t)

dp = [[None] * lent for _ in range(lens)]
# def dfs(aindex=0, bindex=0):
#     if aindex >= lens:
#         return 0
#     if bindex >= lent:
#         return 0
#
#     if dp[aindex][bindex] is not None:
#         return dp[aindex][bindex]
#
#     if s[aindex] == t[bindex]:
#         r = dfs(aindex + 1, bindex + 1) + 1
#     else:
#         r = max(dfs(aindex + 1, bindex), dfs(aindex, bindex + 1))
#     dp[aindex][bindex] = r
#     return r
#
# print(dfs())

dp = [[(0, 0)] * (lent + 1) for _ in range(lens + 1)]
dp = [[(0, 0) for _ in range(lent + 1)] for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            length, pattern = dp[aindex + 1][bindex + 1]
            r = (length + 1, pattern | (2 << aindex))
        else:
            r = max(dp[aindex + 1][bindex], dp[aindex][bindex + 1])
        dp[aindex][bindex] = r
for aindex in range(lens):
    if (2 << aindex) & dp[0][0][1]:
        print(s[aindex], end="")
print()

Submission status: Time Limit Exceeded

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

lens = len(s)
lent = len(t)

dp = [[None] * lent for _ in range(lens)]
# def dfs(aindex=0, bindex=0):
#     if aindex >= lens:
#         return 0
#     if bindex >= lent:
#         return 0
#
#     if dp[aindex][bindex] is not None:
#         return dp[aindex][bindex]
#
#     if s[aindex] == t[bindex]:
#         r = dfs(aindex + 1, bindex + 1) + 1
#     else:
#         r = max(dfs(aindex + 1, bindex), dfs(aindex, bindex + 1))
#     dp[aindex][bindex] = r
#     return r
#
# print(dfs())

dp = [[(0, "")] * (lent + 1) for _ in range(lens + 1)]
dp = [[(0, "") for _ in range(lent + 1)] for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            length, pattern = dp[aindex + 1][bindex + 1]
            r = (length + 1, s[aindex] + pattern)
        else:
            r = max(dp[aindex + 1][bindex], dp[aindex][bindex + 1])
        dp[aindex][bindex] = r
print(dp[0][0][1])

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(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] +ans
        i -= 1
        j -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = raw_input()
t = raw_input()
ls = len(s)
lt = len(t)
 
dp = [[""]*lt for i in xrange(ls)]

curr = ""
for i in xrange(lt):
  if (s[0] == t[i]):
    curr = s[0]
  dp[0][i] = curr

curr = ""
for i in xrange(ls):
  if (t[0] == s[i]):
    curr = t[0]
  dp[i][0] = curr

for i in xrange(1, ls):
  for j in xrange(1, lt):
    dp[i][j] = dp[i-1][j] if len(dp[i-1][j]) >= len(dp[i][j-1]) else dp[i][j-1]
    temp = dp[i-1][j-1]
    if s[i] == t[j]:
      temp =  temp + s[i]
    dp[i][j] = dp[i][j] if len(dp[i][j]) > len(temp) else temp 
print dp[ls-1][lt-1]

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)

dp = [[""]*lt for i in range(ls)]

curr = ""
for i in range(lt):
  if (s[0] == t[i]):
    curr = s[0]
  dp[0][i] = curr

curr = ""
for i in range(ls):
  if (t[0] == s[i]):
    curr = t[0]
  dp[i][0] = curr

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

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
T=input()
memo = [[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]:
            memo[i][j] = memo[i-1][j-1] + 1
        else:
            memo[i][j] = max(memo[i-1][j], memo[i][j-1])
 
ans = ''
i = len(S)
j = len(T)
while i > 0 and j > 0:
    if memo[i][j] == memo[i-1][j]:
        i-=1
    elif memo[i][j] == memo[i][j-1]:
        j-=1
    else:
        i-=1
        j-=1
        ans = ans + S[i]

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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

s = input()[:-1]
t = input()[:-1]

N = len(s) + 1
M = len(t) + 1


# dp[i][j] := s[i] t[j]までのLCS
dp = [[""]*M for _ in range(N)]


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

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
l1=len(s)
l2=len(t)
ans=[]
dp=[[0]*(l2+1) for i in range(l1+1)]
s='1'+s
t='2'+t
#print(dp)
for i in range(1,l1+1):
    for j in range(1,l2+1):
        if(s[i]==t[j]):
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        
length=dp[l1][l2]
'''
print('length',length)
for i in dp:
    print(i)          '''

i=l1
j=l2
while(True):
    #print(dp[i][j])
    if(dp[i][j]!= max(dp[i-1][j],dp[i][j-1])):
        ans.append(s[i])
        i-=1
        j-=1
    else:
        if(dp[i-1][j]>=dp[i][j-1]):
            i-=1
        else:
            j-=1
    if(dp[i][j]==0):
        break
    
print(''.join(str(x) for x in ans[::-1]))

Submission status: Time Limit Exceeded

Solution code:
#n,W=map(int, input().split())
s=input()
t=input()
ns=len(s)
nt=len(t)
dp=[[(0,[]) for j in range(ns+1)] for i in range(nt+1)]
    
for i in range(1,nt+1):
    for j in range(1,ns+1):
        if t[i-1]==s[j-1]:
            dp[i][j]=(dp[i-1][j-1][0]+1,dp[i-1][j-1][1]+[i-1])
        else:
            a,b=dp[i-1][j],dp[i][j-1]
            c=max(a[0],b[0])
            if c==a[0]:
                dp[i][j]=a
            else:
                dp[i][j]=b
    
ans=[]
for i in dp[-1][-1][-1]:
    ans.append(t[i])
print(''.join(ans))

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
ns=len(s)
nt=len(t)
dp=[[(0,'') for j in range(ns+1)] for i in range(nt+1)] # dp[i][j] = max len and string using up to t[i],s[j]

for i in range(1,nt+1):
    for j in range(1,ns+1):
        if t[i-1]==s[j-1]:
            dp[i][j]=(dp[i-1][j-1][0]+1,dp[i-1][j-1][1]+t[i-1])
        else:
            a,b=dp[i-1][j],dp[i][j-1]
            c=max(a[0],b[0])
            if c==a[0]:
                dp[i][j]=a
            else:
                dp[i][j]=b

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
ns=len(s)
nt=len(t)
dp=[[(0,'') for j in range(ns+1)] for i in range(nt+1)] # dp[i][j] = max len and string using up to t[i],s[j]

for i in range(1,nt+1):
    for j in range(1,ns+1):
        if t[i-1]==s[j-1]:
            dp[i][j]=(dp[i-1][j-1][0]+1,dp[i-1][j-1][1]+t[i-1])
        else:
            a,b=dp[i-1][j],dp[i][j-1]
            c=max(a[0],b[0])
            if c==a[0]:
                dp[i][j]=a
            else:
                dp[i][j]=b

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def lcs(xs, ys):
    dp = [([''] * (len(ys) + 1)) for _ in range(len(xs) + 1)]
    for i, x in enumerate(xs):
        for j, y in enumerate(ys):
            dp[i + 1][j + 1] = dp[i][j + 1]
            if len(dp[i + 1][j + 1]) < len(dp[i + 1][j]):
                dp[i + 1][j + 1] = dp[i + 1][j]
            if len(dp[i + 1][j + 1]) < (len(dp[i][j]) + int(x == y)):
                dp[i + 1][j + 1] = dp[i][j] + x
    return dp[-1][-1]


def solve(s: str, t: str):
    return lcs(s, t)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    result = solve(s, t)
    print(result)

if __name__ == '__main__':
    main()