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:
def main():
  s = input()
  t = input()
  dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
  for i in range(1, len(s) + 1):
    dpi = dp[i]
    dpi1 = dp[i - 1]
    si1 = s[i - 1]
    for j in range(1, len(t) + 1):
      k = dpi1[j]
      l = dpi[j - 1] 
      if l > k:
        k = l
      l = dpi1[j - 1] + 1
      if si1 == t[j - 1] and l > k:
        k = l
      dpi[j] = k
  u = []
  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:
      u.append(s[i - 1])
      i -= 1
      j -= 1
  print(''.join(reversed(u)))
main()

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):
    k = dp[i - 1][j]
    if dp[i][j - 1] > k:
      k = dp[i][j - 1]
    if (s[i - 1] == t[j - 1]) and (dp[i - 1][j - 1] + 1 > k):
      k = dp[i - 1][j - 1] + 1
    dp[i][j] = k
result = ''
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:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
s = input()
t = input()
dp = [[-1] * (len(t) + 1) for _ in range(len(s) + 1)]
dp[0][0] = 0
def rec(i, j):
  if dp[i][j] != -1:
    return dp[i][j]
  k = -1
  if i - 1 >= 0:
    k = rec(i - 1, j)
  if j - 1 >= 0:
    k = max(k, rec(i, j - 1))
  if i - 1 >= 0 and j - 1 >= 0 and s[i - 1] == t[j - 1]:
    k = max(k, rec(i - 1, j - 1) + 1)
  dp[i][j] = k
  return dp[i][j]
rec(len(s), len(t))
i = len(s)
j = len(t)
result = ''
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:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from builtins import range
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [[0] * (tlen + 1) for i in range(slen + 1)]
  for i in range(slen):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    si = s[i]
    for j in range(tlen):
      j1 = j + 1
      dpij = dpi[j]
      if si == t[j]:
        dpi1[j1] = dpij + 1
      else:
        if dpij > dpi[j1]:
          dpi[j1] = dpij
        if dpij > dpi1[j]:
          dpi1[j] = dpij
  result = ''
  i = slen
  j = tlen
  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:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [[0] * (tlen + 1) for i in range(slen + 1)]
  for i in range(slen):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    si = s[i]
    for j in range(tlen):
      j1 = j + 1
      if si == t[j]:
        dpi1[j1] = dpi[j] + 1
      else:
        if dpi1[j] > dpi[j1]:
          dpi1[j1] = dpi1[j]
        else:
          dpi1[j1] = dpi[j1]
  result = ''
  i = slen
  j = tlen
  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:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
s = raw_input()
t = raw_input()
dp = dict()
for i in range(-1,len(s)):
    dp[i,-1]=0
for j in range(-1,len(t)):
    dp[-1,j]=0
# dp[-1,0]=0
for i in range(len(s)):
    for j in range(len(t)):
        ni = max(-1, i-1)
        nj = max(-1,j-1)
        if s[i]==t[j]:
            dp[i,j] = max(1 + dp[ni,nj], dp[ni,j], dp[i, nj])
        else:
            dp[i,j] = max(dp[ni,j], dp[i, nj])

# print(dp[len(s)-1, len(t)-1])
ct = dp[len(s)-1, len(t)-1]
x = len(s)-1
y = len(t)-1
ans = ""
while(ct):
    # print(x,y)
    if s[x]==t[y]:
        # print(s[x],t[y])
        ans = ans + s[x]
        ct-=1
        x = x-1
        y = y-1
        
        # print(ans)
    elif dp[x,y]==dp[x-1,y]:
        x = x-1
    elif dp[x,y]==dp[x,y-1]:
        y = y-1
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
s = tuple(input())
t = tuple(input())
n = len(s)
m = len(t)

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

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

res = ''
while n != 0 and m != 0:
    if dp[n][m] == dp[n-1][m]:
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    else:
        n -= 1
        m -= 1
        res = s[n] + res
print(res)

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
  for i in range(slen):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    si = s[i]
    for j in range(tlen):
      j1 = j + 1
      if si == t[j]:
        dpi1[j1] = dpi[j] + 1
      else:
        if dpi1[j] > dpi[j1]:
          dpi1[j1] = dpi1[j]
        else:
          dpi1[j1] = dpi[j1]
  result = ''
  i = slen
  j = tlen
  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:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  _max = max
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
  for i in range(slen):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    si = s[i]
    for j in range(tlen):
      j1 = j + 1
      if si == t[j]:
        dpi1[j1] = dpi[j] + 1
      else:
        dpi1[j1] = _max(            dpi1[j], dpi[j1])
  result = ''
  i = slen
  j = tlen
  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:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  _max = max
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
  for i in range(slen):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    si = s[i]
    for j in range(tlen):
      j1 = j + 1
      if si == t[j]:
        dpi1[j1] = _max(dpi[j] + 1, dpi1[j], dpi[j1])
      else:
        dpi1[j1] = _max(            dpi1[j], dpi[j1])
  result = ''
  i = slen
  j = tlen
  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:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  _max = max
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
  for i in range(slen):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    si = s[i]
    for j in range(tlen):
      j1 = j + 1
      if si == t[j]:
        dpi1[j1] = _max(dpi1[j1], dpi[j] + 1, dpi1[j], dpi[j1])
      else:
        dpi1[j1] = _max(dpi1[j1],             dpi1[j], dpi[j1])
  result = ''
  i = slen
  j = tlen
  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:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  _max = max
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
  for i in range(slen):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    si = s[i]
    for j in range(tlen):
      if si == t[j]:
        dpi1[j + 1] = _max(dpi1[j + 1], dpi[j] + 1, dpi1[j], dpi[j + 1])
      else:
        dpi1[j + 1] = _max(dpi1[j + 1],             dpi1[j], dpi[j + 1])
  result = ''
  i = slen
  j = tlen
  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:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  _max = max
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
  for i in range(slen):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    for j in range(tlen):
      if s[i] == t[j]:
        dpi1[j + 1] = _max(dpi1[j + 1], dpi[j] + 1, dpi1[j], dpi[j + 1])
      else:
        dpi1[j + 1] = _max(dpi1[j + 1],             dpi1[j], dpi[j + 1])
  result = ''
  i = slen
  j = tlen
  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:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
s = [ord(c) - 97 for c in input()]
t = [ord(c) - 97 for c in input()]
sl = len(s)
tl = len(t)
rr = [[0] * (tl) for _ in range(sl)]
t0 = t[0]

# init
for i in range(sl):
    if s[i] == t0:
        for k in range(i,sl):
            rr[k][0] = 1
        break

rr0 = rr[0]
s0 = s[0]
for j in range(tl):
    if s0 == t[j]:
        for k in range(j,tl):
            rr0[k] = 1
        break

# solve
ta = [(i,t[i]) for i in range(1, tl)]
for i in range(1, sl):
    rri = rr[i]
    rri1 = rr[i-1]
    si = s[i]
    for j, tj in ta:
        if si == tj:
            rri[j] = rri1[j-1] + 1
        else:
            rri[j] = rri1[j]
            if rri[j] < rri[j-1]:
                rri[j] = rri[j-1]

# restore
i = sl-1
j = tl-1
r = []
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        r.append(s[i] + 97)
        i -= 1
        j -= 1
        continue
    if rr[i][j] == 0:
        break
    if i > 0 and rr[i-1][j] == rr[i][j]:
        i -= 1
    else:
        j -= 1

ans = ''.join(map(chr,r[::-1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = [ord(c) - 97 for c in input()]
t = [ord(c) - 97 for c in input()]
sl = len(s)
tl = len(t)
rr = [[0] * (tl) for _ in range(sl)]
t0 = t[0]

# init
for i in range(sl):
    if s[i] == t0:
        for k in range(i,sl):
            rr[k][0] = 1
        break

rr0 = rr[0]
s0 = s[0]
for j in range(tl):
    if s0 == t[j]:
        for k in range(j,tl):
            rr0[k] = 1
        break

# solve
ta = [(i,t[i]) for i in range(1, tl)]
for i in range(1, sl):
    rri = rr[i]
    rri1 = rr[i-1]
    si = s[i]
    for j, tj in ta:
        if si == tj:
            rri[j] = rri1[j-1] + 1
        else:
            rri[j] = rri1[j]
            if rri[j] < rri[j-1]:
                rri[j] = rri[j-1]

# restore
i = sl-1
j = tl-1
r = []
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        r.append(s[i] + 97)
        i -= 1
        j -= 1
        continue
    if rr[i][j] == 0:
        break
    if i > 0 and rr[i-1][j] == rr[i][j]:
        i -= 1
    else:
        j -= 1

print(''.join(map(chr,r[::-1])))

"""
https://atcoder.jp/contests/dp/submissions/3972219
より。

愚直な実装で、エッジケース考え始めると大変そうだが…？
numpyと比べてオーバーヘッドが少なくs,tの小さいテストケースでは早い。
"""

Submission status: Time Limit Exceeded

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

# DPテーブルを初期化
dp = [[0 for j in range(len(t)+1)] for i in range(len(s)+1)]


# ループを回す
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

# 答えを復元
ans = ''
i = 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 = list(input())
T = list(input())

s_len = len(S)
t_len = len(T)
MAX = max(s_len, t_len)
dp = [[''] * (MAX + 1) for _ in range(MAX + 1)]
len_dp = [[0] * (MAX + 1) for _ in range(MAX + 1)]


for i in range(s_len):
    for j in range(t_len):
        if S[i] == T[j]:
            candidates = [dp[i][j], dp[i + 1][j], dp[i][j + 1]]
            candidates_len = [len_dp[i][j], len_dp[i + 1][j], len_dp[i][j + 1]]
            max_len = max(candidates_len)
            max_len_index = candidates_len.index(max_len)
            if max_len_index == 0:
                dp[i + 1][j + 1] = candidates[max_len_index] + S[i]
                len_dp[i + 1][j + 1] = candidates_len[max_len_index] + 1
            else:
                dp[i + 1][j + 1] = candidates[max_len_index]
                len_dp[i + 1][j + 1] = candidates_len[max_len_index]
        else:
            if len_dp[i + 1][j] > len_dp[i][j + 1]:
                dp[i + 1][j + 1] = dp[i + 1][j]
                len_dp[i + 1][j + 1] = len_dp[i + 1][j]
            else:
                dp[i + 1][j + 1] = dp[i][j + 1]
                len_dp[i + 1][j + 1] = len_dp[i][j + 1]
print(dp[s_len][t_len])

Submission status: Time Limit Exceeded

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

s_len = len(S)
t_len = len(T)
MAX = max(s_len, t_len)
dp = [[''] * (MAX + 1) for _ in range(MAX + 1)]


for i in range(s_len):
    for j in range(t_len):
        if S[i] == T[j]:
            candidates = [dp[i][j], dp[i + 1][j], dp[i][j + 1]]
            candidates_len = list(map(len, candidates))
            max_len = max(candidates_len)
            max_len_index = candidates_len.index(max_len)
            if max_len_index == 0:
                dp[i + 1][j + 1] = candidates[max_len_index] + S[i]
            else:
                dp[i + 1][j + 1] = candidates[max_len_index]
        else:
            if len(dp[i + 1][j]) > len(dp[i][j + 1]):
                dp[i + 1][j + 1] = dp[i + 1][j]
            else:
                dp[i + 1][j + 1] = dp[i][j + 1]
print(dp[s_len][t_len])

Submission status: Time Limit Exceeded

Solution code:
s=input();t=input()
ls=len(s);lt=len(t)
dp=[[0]*(lt+1) for _ in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    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 ls and lt:
  if dp[ls][lt]==dp[ls-1][lt]:
    ls-=1
  elif dp[ls][lt]==dp[ls][lt-1]:
    lt-=1
  else:
    ls-=1;lt-=1
    ans+=s[ls]
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
from array import array
def main():
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [array('L', [0 for j in range(tlen + 1)]) for i in range(slen + 1)]
  for i in range(slen):
    dpi1 = dp[i + 1]
    for j in range(tlen):
      if s[i] == t[j]:
        dpi1[j + 1] = max(dpi1[j + 1], dp[i][j] + 1, dpi1[j], dp[i][j + 1])
      else:
        dpi1[j + 1] = max(dpi1[j + 1], dpi1[j], dp[i][j + 1])
  result = ''
  i = slen
  j = tlen
  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:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
  for i in range(slen):
    dpi1 = dp[i + 1]
    for j in range(tlen):
      if s[i] == t[j]:
        dpi1[j + 1] = max(dpi1[j + 1], dp[i][j] + 1, dpi1[j], dp[i][j + 1])
      else:
        dpi1[j + 1] = max(dpi1[j + 1], dpi1[j], dp[i][j + 1])
  result = ''
  i = slen
  j = tlen
  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:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
  for i in range(slen):
    for j in range(tlen):
      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])
  result = ''
  i = slen
  j = tlen
  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:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()