Problem:


Score : 100 points

Problem Statement

You are given strings s and t.
Find one longest string that is a subsequence of both s and t.

Notes

A subsequence of a string x is the string obtained by removing zero or more characters from x and concatenating the remaining characters without changing the order.

Constraints

s and t are strings consisting of lowercase English letters.

1 \leq |s|, |t| \leq 3000

Input

Input is given from Standard Input in the following format:

s
t

Output

Print one longest string that is a subsequence of both s and t.
If there are multiple such strings, any of them will be accepted.

Sample Input 1

axyb
abyxb

Sample Output 1

axb

The answer is axb or ayb; either will be accepted.

Sample Input 2

aa
xayaz

Sample Output 2

aa

Sample Input 3

a
z

Sample Output 3

The answer is  (an empty string).

Sample Input 4

abracadabra
avadakedavra

Sample Output 4

aaadara



Sample input:
axyb
abyxb


Sample output:
axb

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
n = len(s)
m = len(t)
letter = [[""for i in range(n+1)]for j in range(m+1)]
x = 0
y = 0
for i,a in enumerate(t):
    for j,b in enumerate(s):
        if len(letter[i+1][j])<len(letter[i][j]):
            letter[i + 1][j] = letter[i][j]
        if len(letter[i][j+1])<len(letter[i][j]):
            letter[i][j+1] = letter[i][j]
        if a == b:
            if len(letter[i+1][j+1])<len(letter[i][j])+1:
                letter[i+1][j+1] = letter[i][j]+a
                x = i+1
                y = j+1
            else:
                letter[i+1][j+1] = letter[i][j]

print(letter[x][y])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0for i in range(n+1)]for j in range(m+1)]
letter = [[""for i in range(n+1)]for j in range(m+1)]
x = 0
y = 0
for i,a in enumerate(t):
    for j,b in enumerate(s):
        if dp[i+1][j]<dp[i][j]:
            letter[i + 1][j] = letter[i][j]
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if dp[i][j+1]<dp[i][j]:
            letter[i][j+1] = letter[i][j]
        dp[i][j+1] = max(dp[i][j+1],dp[i][j])
        if a == b:
            if dp[i+1][j+1]<dp[i][j]+1:
                letter[i+1][j+1] = letter[i][j]+a
                x = i+1
                y = j+1
            else:
                letter[i+1][j+1] = letter[i][j]
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1)

print(letter[x][y])

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
t = str(input())
ls = len(s)
lt = len(t)
x = [["",0] for _ in range(((ls+1)*(lt+1)))]
for k in range(ls+lt-1):
  for i in range(max(0,k-lt+1),min(k,ls-1)+1):
    j = k-i
    if s[i] == t[j]:
      a = x[i*(lt+1)+j][1]+1
      b = x[i*(lt+1)+j+1][1]
      c = x[(i+1)*(lt+1)+j][1]
      m = max([a,b,c])
      if  m == a:
        x[(i+1)*(lt+1)+j+1][0] = x[i*(lt+1)+j][0]+s[i]
        x[(i+1)*(lt+1)+j+1][1] = a
      elif m == b:
        x[(i+1)*(lt+1)+j+1] = x[i*(lt+1)+j+1]
      else:
        x[(i+1)*(lt+1)+j+1] = x[(i+1)*(lt+1)+j]
    else:
      b = x[i*(lt+1)+j+1][1]
      c = x[(i+1)*(lt+1)+j][1]
      if b >= c:
        x[(i+1)*(lt+1)+j+1] = x[i*(lt+1)+j+1]
      else:
        x[(i+1)*(lt+1)+j+1] = x[(i+1)*(lt+1)+j]
print(x[ls*(lt+1)+lt][0])

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
t = str(input())
ls = len(s)
lt = len(t)
x = [""]*((ls+1)*(lt+1))
for k in range(ls+lt-1):
  for i in range(max(0,k-lt+1),min(k,ls-1)+1):
    j = k-i
    if s[i] == t[j]:
      a = len(x[i*(lt+1)+j])+1
      b = len(x[i*(lt+1)+j+1])
      c = len(x[(i+1)*(lt+1)+j])
      m = max([a,b,c])
      if  m == a:
        x[(i+1)*(lt+1)+j+1] = x[i*(lt+1)+j]+s[i]
      elif m == b:
        x[(i+1)*(lt+1)+j+1] = x[i*(lt+1)+j+1]
      else:
        x[(i+1)*(lt+1)+j+1] = x[(i+1)*(lt+1)+j]
    else:
      b = len(x[i*(lt+1)+j+1])
      c = len(x[(i+1)*(lt+1)+j])
      if b >= c:
        x[(i+1)*(lt+1)+j+1] = x[i*(lt+1)+j+1]
      else:
        x[(i+1)*(lt+1)+j+1] = x[(i+1)*(lt+1)+j]
print(x[ls*(lt+1)+lt])

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
t = str(input())
ls = len(s)
lt = len(t)
x = [""]*((ls+1)*(lt+1))
for k in range(ls+lt-1):
  for i in range(max(0,k-lt+1),min(k,ls-1)+1):
    j = k-i
    if s[i] == t[j]:
      a = len(x[i*(lt+1)+j])
      a += 1
      b = len(x[i*(lt+1)+j+1])
      c = len(x[(i+1)*(lt+1)+j])
      if max([a,b,c]) == a:
        x[(i+1)*(lt+1)+j+1] = x[i*(lt+1)+j]+s[i]
      elif max([a,b,c]) == b:
        x[(i+1)*(lt+1)+j+1] = x[i*(lt+1)+j+1]
      else:
        x[(i+1)*(lt+1)+j+1] = x[(i+1)*(lt+1)+j]
    else:
      b = len(x[i*(lt+1)+j+1])
      c = len(x[(i+1)*(lt+1)+j])
      if b >= c:
        x[(i+1)*(lt+1)+j+1] = x[i*(lt+1)+j+1]
      else:
        x[(i+1)*(lt+1)+j+1] = x[(i+1)*(lt+1)+j]
print(x[ls*(lt+1)+lt])

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
t = str(input())
ls = len(s)
lt = len(t)
x = [["" for _ in range(lt+1)] for _ in range(ls+1)]
for k in range(ls+lt-1):
  for i in range(max(0,k-lt+1),min(k,ls-1)+1):
    j = k-i
    if s[i] == t[j]:
      a = len(x[i][j])
      a += 1
      b = len(x[i][j+1])
      c = len(x[i+1][j])
      if max([a,b,c]) == a:
        x[i+1][j+1] = x[i][j]+s[i]
      elif max([a,b,c]) == b:
        x[i+1][j+1] = x[i][j+1]
      else:
        x[i+1][j+1] = x[i+1][j]
    else:
      b = len(x[i][j+1])
      c = len(x[i+1][j])
      if b >= c:
        x[i+1][j+1] = x[i][j+1]
      else:
        x[i+1][j+1] = x[i+1][j]
print(x[ls][lt])

Submission status: Time Limit Exceeded

Solution code:
#Template 1.0
import sys, re
# from collections import deque, defaultdict, Counter
# from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
# from itertools import accumulate, permutations, combinations, product, groupby
# from operator import itemgetter, mul
# from copy import deepcopy
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect, bisect_left
# from heapq import heappush, heappop, heapify
# from functools import reduce
def input(): return sys.stdin.readline().strip()
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
def list2d(a, b, c): return [[c] * b for i in range(a)]
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7



s = STR()
t = STR()
Ls = len(s)
Lt = len(t)
dp = list2d(Ls+1, Lt+1, 0)

ans = ""
for i in range(1, Ls+1):
    for j in range(1, Lt+1):
        if(s[i-1]==t[j-1]):
            dp[i][j] = 1 + dp[i-1][j-1]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
row = Ls
col = Lt

while(row>0 and col>0):
    # print(dp[row][col], row, col)
    if(dp[row][col]!=max(dp[row-1][col], dp[row][col-1])):
        ans+=str(t[col-1])
        row-=1
        col-=1
    else:
        if(dp[row][col]==dp[row-1][col]):
            # ans += str(s[row - 2])
            row-=1
        else:
            # ans += str(t[col - 2])
            col-=1
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
#Template 1.0
import sys, re
# from collections import deque, defaultdict, Counter
# from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
# from itertools import accumulate, permutations, combinations, product, groupby
# from operator import itemgetter, mul
# from copy import deepcopy
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect, bisect_left
# from heapq import heappush, heappop, heapify
# from functools import reduce
def input(): return sys.stdin.readline().strip()
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
def list2d(a, b, c): return [[c] * b for i in range(a)]
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

# start your code here:

def solve(i, j):
    if(i==Ls or j==Lt):
        return ""
    elif(s[i]==t[j]):
        if(dp[i][j]==-1):
            foo = str(s[i]) + solve(i+1, j+1)
            dp[i][j] = foo
            return foo
        else:
            return dp[i][j]
    else:
        if(dp[i][j]==-1):
            temp1 = solve(i+1, j)
            temp2 = solve(i, j+1)

            if(len(temp1)>len(temp2)):
                dp[i][j] = temp1
                return temp1
            dp[i][j] = temp2
            return temp2
        else:
            return dp[i][j]

s = STR()
t = STR()
Ls = len(s)
Lt = len(t)
dp = list2d(3001, 3001, -1)
print(solve(0, 0))

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]

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

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

Submission status: Time Limit Exceeded

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

s=len(S)
t=len(T)
#DPテーブル作成
dp=[['']*(t+1) for _ 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] =  max([ dp[i+1][j] , dp[i][j+1] ],key=len)
# print(*dp,sep="\n")

res = ''
while s != 0 and t != 0:
    if dp[s][t] == dp[s-1][t]:
        s -= 1
    elif dp[s][t] == dp[s][t-1]:
        t -= 1
    else:
        s -= 1
        t -= 1
        res = S[s] + res

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

Submission status: Time Limit Exceeded

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

s=len(S)
t=len(T)
#DPテーブル作成
dp=[['']*(t+1) for _ 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] =  max([ dp[i+1][j] , dp[i][j+1] ],key=len)
print(dp[s][t])

Submission status: Time Limit Exceeded

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

s=len(S)
t=len(T)
#DPテーブル作成
dp=[['']*(t+1) for _ 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] =  max([ dp[i+1][j] , dp[i][j+1] ],key=len)
# print(*dp,sep="\n")

print(dp[s][t])

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    s, t = input(), input()    

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

    i, j = len(t), len(s)
    ans = []

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input=sys.stdin.buffer.readline
    s=b' '+input()[:-1]
    t=b' '+input()[:-1]
    n,m=len(s),len(t)
    dp=[[0]*m for _ in range(n)]
    b=dp[0]
    for i in range(1,n):
        dpi=dp[i]
        for j in range(1,m):
            if s[i]==t[j]:
                dpi[j]=b[j-1]+1
            else:
                dpi[j]=max(b[j],dpi[j-1])
        b=dpi
    ans=[]
    i,j=n-1,m-1
    while dp[i][j]:
        if dp[i][j]==dp[i-1][j]:
            i-=1
        elif dp[i][j]==dp[i][j-1]:
            j-=1
        else:
            ans.append(s[i])
            i-=1
            j-=1
    print(''.join(map(chr,ans))[::-1])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input=sys.stdin.buffer.readline
    s=b' '+input()[:-1]
    t=b' '+input()[:-1]
    n,m=len(s),len(t)
    dp=[[0]*m for _ in range(n)]
    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]+1
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    ans=[]
    i,j=n-1,m-1
    while dp[i][j]:
        if dp[i][j]==dp[i-1][j]:
            i-=1
        elif dp[i][j]==dp[i][j-1]:
            j-=1
        else:
            ans.append(s[i])
            i-=1
            j-=1
    print(''.join(map(chr,ans))[::-1])
main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


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

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

    dp = []
    for _ in range(0, lt):
        L = [0]*ls
        dp.append(L)
    
    # initialize
    val = 0
    for itr_s in range(0, ls):
        if s[itr_s] == t[0]:
            val = 1
        dp[0][itr_s] = val
    val = 0
    for itr_t in range(0, lt):
        if t[itr_t] == s[0]:
            val = 1
        dp[itr_t][0] = val

    for itr_t in range(1, lt):
        for itr_s in range(1, ls):
            if s[itr_s] == t[itr_t]:
                dp[itr_t][itr_s] = dp[itr_t - 1][itr_s - 1] + 1
            else:
                dp[itr_t][itr_s] = max(dp[itr_t - 1][itr_s], dp[itr_t][itr_s - 1])

    res = ""
    while itr_s > 0 or itr_t > 0:
        itr_s, itr_t = ls - 1, lt - 1
        if dp[itr_t][itr_s] == dp[itr_t][itr_s - 1]:
            itr_s -= 1
        elif dp[itr_t][itr_s] == dp[itr_t - 1][itr_s]:
            itr_t -= 1
        else:
            res = s[itr_s] + res
            itr_s -= 1
            itr_t -= 1
        
    if dp[itr_t][itr_s] == 1:
        res = s[itr_s] + res

    print(res)



        
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    solve(s, t)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s,t=input(),input()
n,m=len(s),len(t)
dp=[[0]*(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])
ans=""
while m>0 and n>0:
  if s[n-1]==t[m-1]:ans+=s[n-1];n-=1;m-=1
  elif dp[n][m]==dp[n-1][m]:n-=1
  else:m-=1
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys


def solve(s, t):
    v = [0] * (len(s) + 1)
    dp = [v]
    for ti in t:
        u, v = v, v.copy()
        dp.append(v)
        ll, ul = 0, 0
        for j, sj in enumerate(s):
            uj = u[j + 1]
            if sj == ti:
                v[j + 1] = 1 + ul
                ll = 1 + ul
            else:
                if ll > uj:
                    v[j + 1] = ll
                else:
                    ll = uj
            ul = uj
    i = len(t)
    j = len(s)
    k = dp[i][j]
    selected = []
    while k > 0:
        if dp[i - 1][j] == k:
            i -= 1
        elif dp[i][j - 1] == k:
            j -= 1
        else:
            selected.append(t[i - 1])
            k -= 1
            i -= 1
            j -= 1
    return "".join(selected[::-1])


def do_job():
    "Do the work"
    s = input()
    t = input()
    result = solve(s, t)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys


def solve(s, t):
    v = [0] * (len(s) + 1)
    dp = [v]
    for ti in t:
        u, v = v, v.copy()
        dp.append(v)
        ll, ul = 0, 0
        for j, sj in enumerate(s):
            uj = u[j + 1]
            if sj == ti:
                v[j + 1] = 1 + ul
                ll = 1 + ul
            else:
                if ll > uj:
                    v[j + 1] = ll
                else:
                    ll = uj
            ul = uj
    i = len(t)
    j = len(s)
    k = dp[i][j]
    selected = []
    while k > 0:
        if t[i - 1] == s[j - 1]:
            selected.append(t[i - 1])
            k -= 1
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(selected[::-1])


def do_job():
    "Do the work"
    s = input()
    t = input()
    result = solve(s, t)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys


def solve(s, t):
    v = [0] * (len(s) + 1)
    dp = [v]
    for i, ti in enumerate(t):
        u, v = v, v.copy()
        dp.append(v)
        for j, sj in enumerate(s):
            if sj == ti:
                v[j + 1] = 1 + u[j]
            else:
                v[j + 1] = u[j + 1]
                tmp = v[j]
                if v[j + 1] < tmp:
                    v[j + 1] = tmp
    i = len(t)
    j = len(s)
    k = dp[i][j]
    selected = []
    while k > 0:
        if t[i - 1] == s[j - 1]:
            selected.append(t[i - 1])
            k -= 1
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(selected[::-1])


def do_job():
    "Do the work"
    s = input()
    t = input()
    result = solve(s, t)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys


def solve(s, t):
    v = [0 for _ in range(len(s) + 1)]
    dp = [v]
    for i, ti in enumerate(t):
        u, v = v, v.copy()
        dp.append(v)
        for j, sj in enumerate(s):
            if sj == ti:
                v[j + 1] = 1 + u[j]
            else:
                v[j + 1] = max(u[j + 1], v[j])
    i = len(t)
    j = len(s)
    k = dp[i][j]
    selected = []
    while k > 0:
        if t[i - 1] == s[j - 1]:
            selected.append(t[i - 1])
            k -= 1
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(selected[::-1])


def do_job():
    "Do the work"
    s = input()
    t = input()
    result = solve(s, t)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys


def solve(s, t):
    dp = [[0 for _ in range(len(s) + 1)] for _ in range(len(t) + 1)]
    for i, ti in enumerate(t):
        for j, sj in enumerate(s):
            if sj == ti:
                dp[i + 1][j + 1] = 1 + dp[i][j]
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
    i = len(t)
    j = len(s)
    k = dp[i][j]
    selected = []
    while k > 0:
        if t[i - 1] == s[j - 1]:
            selected.append(t[i - 1])
            k -= 1
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(selected))


def do_job():
    "Do the work"
    s = input()
    t = input()
    result = solve(s, t)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys


def solve(s, t):
    dp = [[0 for _ in range(len(s) + 1)] for _ in range(len(t) + 1)]
    for i in range(1, len(t) + 1):
        for j in range(1, len(s) + 1):
            if s[j - 1] == t[i - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    i = len(t)
    j = len(s)
    selected = []
    while i > 0 and j > 0:
        if t[i - 1] == s[j - 1]:
            selected.append(t[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(selected))


def do_job():
    "Do the work"
    s = input()
    t = input()
    result = solve(s, t)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    s = input().rstrip()
    t = input().rstrip()

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

    dp = []
    for _ in range(n + 1):
        dp.append([''] * (m + 1))

    for i in range(1, n + 1):
        s_ = s[i - 1]
        for j in range(1, m + 1):
            t_ = t[j - 1]
            if s_ != t_:
                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]
            else:
                dp[i][j] = list(dp[i - 1][j - 1])
                dp[i][j].append(s_)
                dp[i][j] = "".join(dp[i][j])

    print(dp[-1][-1])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    s = input().rstrip()
    t = input().rstrip()

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

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

    for i in range(1, n + 1):
        s_ = s[i - 1]
        for j in range(1, m + 1):
            t_ = t[j - 1]
            if s_ != t_:
                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]
            else:
                dp[i][j] = list(dp[i - 1][j - 1])
                dp[i][j].append(s_)
                dp[i][j] = "".join(dp[i][j])

    print(dp[-1][-1])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    s = input().rstrip()
    t = input().rstrip()

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

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

    for i in range(1, n + 1):
        s_ = s[i - 1]
        for j in range(1, m + 1):
            t_ = t[j - 1]
            if s_ != t_:
                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]
            else:
                dp[i][j] = dp[i - 1][j - 1][:]
                dp[i][j].append(s_)

    print("".join(dp[-1][-1]))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

s = input().rstrip()
t = input().rstrip()

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

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

from copy import deepcopy

for i in range(1, n + 1):
    s_ = s[i - 1]
    for j in range(1, m + 1):
        t_ = t[j - 1]
        if s_ != t_:
            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]
        else:
            dp[i][j] = deepcopy(dp[i - 1][j - 1])
            dp[i][j].append(s_)

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

Submission status: Time Limit Exceeded

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

s = input().rstrip()
t = input().rstrip()

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

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

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

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

Submission status: Time Limit Exceeded

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

ans = ""
i = len(s)
j = len(t)
while 0 < i and 0 < j:
    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]
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
s = input()
t = input()

#dp[i][j] = sのi番,tのj番までの最大
dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
memo = [[set() 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 dp[i][j] < dp[i-1][j]:
            dp[i][j] = dp[i-1][j]
            memo[i][j] = memo[i-1][j]
        if dp[i][j] < dp[i][j-1]:
            dp[i][j] = dp[i][j-1]
            memo[i][j] = memo[i][j-1]
        if s[i-1] == t[j-1]:
            if dp[i][j] < dp[i-1][j-1] + 1:
                dp[i][j] = dp[i-1][j-1] + 1
                memo[i][j] = memo[i-1][j-1] | {i-1}
#print(dp[len(s)][len(t)])
ans = ''
for i in memo[len(s)][len(t)]:
    ans += s[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
s = input()
t = input()

#dp[i][j] = sのi番,tのj番までの最大
dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
memo = [[[] 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 dp[i][j] < dp[i-1][j]:
            dp[i][j] = dp[i-1][j]
            memo[i][j] = memo[i-1][j]
        if dp[i][j] < dp[i][j-1]:
            dp[i][j] = dp[i][j-1]
            memo[i][j] = memo[i][j-1]
        if s[i-1] == t[j-1]:
            if dp[i][j] < dp[i-1][j-1] + 1:
                dp[i][j] = dp[i-1][j-1] + 1
                memo[i][j] = memo[i-1][j-1] + [i-1]
#print(dp[len(s)][len(t)])
ans = ''
for i in memo[len(s)][len(t)]:
    ans += s[i]
print(ans)

Submission status: Time Limit Exceeded

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

#dp[i][j] = sのi番,tのj番までの最大
dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
memo = [[[] 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 dp[i][j] < dp[i-1][j]:
            dp[i][j] = dp[i-1][j]
            memo[i][j] = memo[i-1][j]
        if dp[i][j] < dp[i][j-1]:
            dp[i][j] = dp[i][j-1]
            memo[i][j] = memo[i][j-1]
        if s[i-1] == t[j-1]:
            if dp[i][j] < dp[i-1][j-1] + 1:
                dp[i][j] = dp[i-1][j-1] + 1
                memo[i][j] = memo[i-1][j-1] + [i-1]
#print(dp[len(s)][len(t)])
ans = ''
for i in memo[len(s)][len(t)]:
    ans += s[i]
print(ans)

Submission status: Time Limit Exceeded

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

#dp[i][j] = sのi番,tのj番までの最大
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 len(dp[i][j]) < len(dp[i-1][j]):
            dp[i][j] = dp[i-1][j]
        if len(dp[i][j]) < len(dp[i][j-1]):
            dp[i][j] = dp[i][j-1]
        if s[i-1] == t[j-1]:
            if len(dp[i-1][j-1]) < len(dp[i-1][j-1]) + 1:
                dp[i][j] = dp[i-1][j-1] + s[i-1]
print(dp[len(s)][len(t)])

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)
    dp = [[0] * (M+1) for _ in range(N+1)]
    
    for i in range(1, N+1):
        for j in range(1, M+1):
            p = (S[i-1] == T[j-1])
            dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + p)
            
    ans = []
    x, y = N, M
    while x and y:
        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
            ans.append(S[x])
        
    print(''.join(ans[::-1]))


if __name__ == "__main__":
    main()