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: Wrong Answer

Solution code:
from itertools import product
from collections import deque
import sys
sys.setrecursionlimit(100000)


def read():
    s = input()
    t = input()
    return s, t


def lcs(s, t):
    S = len(s)
    T = len(t)
    dp = [[0 for j in range(T+1)] for i in range(S+1)]
    for i, j in product(range(S), range(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] = max(dp[i+1][j], dp[i][j])
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])
    maxpos = (0, 0)
    maxv = dp[0][0]
    for i, j in product(range(S), range(T)):
        if maxv < dp[i+1][j+1]:
            maxpos = (i, j)
            maxv = dp[i+1][j+1]
    return maxpos, dp


def retrieve(s, t, i, j, dp):
    x = list()
    while i >= 0 and j >= 0:
        if s[i] == t[j]:
            x.append(s[i])
            i -= 1
            j -= 1
        elif j < 0:
            i -= 1
        elif i < 0:
            j -= 1
        else:
            if dp[i][j+1] < dp[i+1][j]:
                j -= 1
            else:
                i -= 1
    return ''.join(reversed(x))


def solve(s, t):
    maxpos, dp = lcs(s, t)
    i, j = maxpos
    ans = retrieve(s, t, i, j, dp)
    return ans


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Wrong Answer

Solution code:
from itertools import product
from collections import deque
import sys
sys.setrecursionlimit(100000)


def read():
    s = input()
    t = input()
    return s, t


def lcs(s, t):
    S = len(s)
    T = len(t)
    dp = [[0 for j in range(T+1)] for i in range(S+1)]
    maxpos = (-1, -1)
    for i, j in product(range(S), range(T)):
        if s[i] == t[j]:
            if dp[i+1][j+1] < dp[i][j] + 1:
                dp[i+1][j+1] = dp[i][j] + 1
                if dp[maxpos[0]+1][maxpos[1]+1] < dp[i+1][j+1]:
                    maxpos = (i, j)
        else:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j])
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])
    return maxpos, dp


def retrieve(s, t, i, j, dp):
    x = list()
    while i >= 0 and j >= 0:
        if s[i] == t[j]:
            x.append(s[i])
            i -= 1
            j -= 1
        elif j < 0:
            i -= 1
        elif i < 0:
            j -= 1
        else:
            if dp[i][j+1] < dp[i+1][j]:
                j -= 1
            else:
                i -= 1
    return ''.join(reversed(x))


def solve(s, t):
    maxpos, dp = lcs(s, t)
    i, j = maxpos
    ans = retrieve(s, t, i, j, dp)
    return ans


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Wrong Answer

Solution code:
from itertools import product
from collections import deque
import sys
sys.setrecursionlimit(100000)


def read():
    s = input()
    t = input()
    return s, t


def lcs(s, t):
    S = len(s)
    T = len(t)
    dp = [[0 for j in range(T+1)] for i in range(S+1)]
    maxpos = (0, 0)
    for i, j in product(range(S), range(T)):
        if s[i] == t[j]:
            if dp[i+1][j+1] < dp[i][j] + 1:
                dp[i+1][j+1] = dp[i][j] + 1
                if dp[maxpos[0]+1][maxpos[1]+1] < dp[i+1][j+1]:
                    maxpos = (i, j)
        else:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j])
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])
    return maxpos, dp


def retrieve(s, t, i, j, dp):
    x = list()
    while i >= 0 and j >= 0:
        if s[i] == t[j]:
            x.append(s[i])
            i -= 1
            j -= 1
        elif j < 0:
            i -= 1
        elif i < 0:
            j -= 1
        else:
            if dp[i][j+1] < dp[i+1][j]:
                j -= 1
            else:
                i -= 1
    return ''.join(reversed(x))


def solve(s, t):
    maxpos, dp = lcs(s, t)
    i, j = maxpos
    ans = retrieve(s, t, i, j, dp)
    return ans


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Wrong Answer

Solution code:
from itertools import product
from collections import deque
import sys
sys.setrecursionlimit(100000)


def read():
    s = input()
    t = input()
    return s, t


def lcs(s, t):
    S = len(s)
    T = len(t)
    dp = [[0 for j in range(T+1)] for i in range(S+1)]
    maxpos = (0, 0)
    for i, j in product(range(S), range(T)):
        if s[i] == t[j]:
            if dp[i+1][j+1] < dp[i][j] + 1:
                dp[i+1][j+1] = dp[i][j] + 1
                if dp[maxpos[0]+1][maxpos[1]+1] < dp[i+1][j+1]:
                    maxpos = (i, j)
        else:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])
    return maxpos, dp


def retrieve(s, t, i, j, dp):
    x = list()
    while i >= 0 and j >= 0:
        if s[i] == t[j]:
            x.append(s[i])
            i -= 1
            j -= 1
        elif j < 0:
            i -= 1
        elif i < 0:
            j -= 1
        else:
            if dp[i][j+1] < dp[i+1][j]:
                j -= 1
            else:
                i -= 1
    return ''.join(reversed(x))


def solve(s, t):
    maxpos, dp = lcs(s, t)
    i, j = maxpos
    ans = retrieve(s, t, i, j, dp)
    return ans


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Wrong Answer

Solution code:
from itertools import product
from collections import deque
import sys
sys.setrecursionlimit(100000)


def read():
    s = input()
    t = input()
    return s, t


def lcs(s, t):
    S = len(s)
    T = len(t)
    dp = [[0 for j in range(T+1)] for i in range(S+1)]
    maxpos = (0, 0)
    for i, j in product(range(S), range(T)):
        if s[i] == t[j]:
            if dp[i+1][j+1] < dp[i][j] + 1:
                dp[i+1][j+1] = dp[i][j] + 1
                if dp[maxpos[0]+1][maxpos[1]+1] < dp[i+1][j+1]:
                    maxpos = (i, j)
        else:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])
    return maxpos, dp


def dfs(s, t, i, j, dp):
    q = deque()
    cost = dp[i+1][j+1]
    q.append((i, j, cost))
    sidx = list()
    while len(q) > 0:
        i, j, cost = q.pop()
        if i < 0 or j < 0 or cost < 0:
            continue
        if cost != dp[i+1][j+1]:
            continue
        if s[i] == t[j]:
            q.clear()
            q.append((i-1, j-1, cost-1))
            sidx.append(i)
        else:
            q.append((i-1, j, cost))
            q.append((i, j-1, cost))
    return reversed(sidx)


def solve(s, t):
    maxpos, dp = lcs(s, t)
    i, j = maxpos
    x = dfs(s, t, i, j, dp)
    ans = ''.join([s[i] for i in x])
    return ans


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Wrong Answer

Solution code:
from itertools import product
from collections import deque
import sys
sys.setrecursionlimit(100000)


def read():
    s = input()
    t = input()
    return s, t


def lcs(s, t):
    S = len(s)
    T = len(t)
    dp = [[0 for j in range(T+1)] for i in range(S+1)]
    maxpos = (0, 0)
    for i, j in product(range(S), range(T)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
            if dp[maxpos[0]+1][maxpos[1]+1] < dp[i+1][j+1]:
                maxpos = (i, j)
        else:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])
    return maxpos, dp


def dfs(s, t, i, j, dp):
    q = deque()
    cost = dp[i+1][j+1]
    q.append((i, j, cost))
    sidx = list()
    while len(q) > 0:
        i, j, cost = q.pop()
        if i < 0 or j < 0 or cost < 0:
            continue
        if cost != dp[i+1][j+1]:
            continue
        if s[i] == t[j]:
            q.clear()
            q.append((i-1, j-1, cost-1))
            sidx.append(i)
        else:
            q.append((i-1, j, cost))
            q.append((i, j-1, cost))
    return reversed(sidx)


def solve(s, t):
    maxpos, dp = lcs(s, t)
    i, j = maxpos
    x = dfs(s, t, i, j, dp)
    ans = ''.join([s[i] for i in x])
    return ans


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
dp=[[0]*(len(s)+1) for i 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]=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])
ans=[]
a=dp[len(t)][len(s)]
i=len(t)
j=len(s)
while i>0 and j>0:
  while j>0:
    if s[j-1]==t[i-1]:
      ans.append(s[j-1])
      i=i-1
      j=j-1
    else:
      if dp[i][j]==dp[i][j-1]:
        j=j-1
      else:
        i=i-1
ans=ans[::-1]
for i in range(len(ans)):
  print(ans[i],end="")
print()

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
dp=[[0]*(len(s)+1) for i 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]=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])
ans=[]
a=dp[len(t)][len(s)]
i=len(t)
j=len(s)
while i>0 and j>0:
  while j>0:
    if dp[i][j]==dp[i-1][j-1]+1 and dp[i][j]!=dp[i-1][j] and dp[i][j]!=dp[i][j-1]:
      ans.append(s[j-1])
      i=i-1
      j=j-1
      a=j
    else:
      j=j-1
  i=i-1
  j=a
ans=ans[::-1]
for i in range(len(ans)):
  print(ans[i],end="")
print()

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
dp=[[0]*(len(s)+1) for i 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]=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])
ans=[]
a=dp[len(t)][len(s)]
i=len(t)
j=len(s)
while i>0 and j>0:
  while j>0:
    if dp[i][j]==dp[i-1][j-1]+1:
      ans.append(s[j-1])
      i=i-1
      j=j-1
    else:
      j=j-1
ans=ans[::-1]
for i in range(len(ans)):
  print(ans[i],end="")
print()

Submission status: Wrong Answer

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
# import sys
# sys.setrecursionlimit(10**9)

def resolve():
    s = str(input())
    t = str(input())


    # 文字列S, Tのlongest common subsequenceの長さを返す
    # なお、longest common continuous subsequenceではないので注意！
    def lcs(S, T):
        # 初期化
        dp = [[0] * (len(T) + 1) for j in range(len(S) + 1)]

        # dp[i][j]はS[:i]とT[:j]のlcsの長さを表す
        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])
                # 望まれたニューカマーが来たら足す
                if S[i] == T[j]:
                    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
        l=[]
        for i in range(1,len(T)+1):
            if dp[len(S)][i]>dp[len(S)][i-1]:
                l.append(T[i-1])
        return ''.join(l)

    print(lcs(s, t))


resolve()

Submission status: Wrong Answer

Solution code:
a = input()
b = input()
n, m = len(a), len(b)

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

for i in range(n):
    for j in range(m):
        if a[i] == b[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(*dp, sep="\n")

c, d = n, m
ans = ""
while c > 0 and d > 0:
    if dp[c - 1][d - 1] == dp[c][d] - 1:
        ans = a[c - 1] + ans
        c -= 1
        d -= 1
    elif dp[c - 1][d] == dp[c][d]:
        c -= 1
    elif dp[c][d - 1] == dp[c][d]:
        d -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
a = input()
b = input()
n, m = len(a), len(b)

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

for i in range(n):
    for j in range(m):
        if a[i] == b[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(*dp, sep="\n")

c, d = n, m
ans = []
while dp[c][d]:
    if dp[c - 1][d - 1] == dp[c][d] - 1:
        ans.append(a[c - 1])
        c -= 1
        d -= 1
    elif dp[c - 1][d] == dp[c][d]:
        c -= 1
    elif dp[c][d - 1] == dp[c][d]:
        d -= 1
print("".join(ans[::-1]))

Submission status: Wrong Answer

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

sl = len(s)
tl = len(t)

dp = [[""] * (tl+1) for i in range(sl+1)]

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

print(dp[sl][tl])

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
len_s = len(s)
len_t = len(t)

dp = {}
for i in range(-1, len_s):
    dp[(i, -1)] = 0
for j in range(-1, len_t):
    dp[(-1, j)] = 0

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

print(dp[(len_s - 1, len_t - 1)])

answer = ''
i, j = len_s - 1, len_t - 1
while i > -1 and j > -1:
    now = dp[(i, j)]
    if dp[(i-1, j)] == now:
        i -= 1
        continue
    if dp[(i, j-1)] == now:
        j -= 1
        continue
    answer += s[i]
    i -= 1
    j -= 1

print(answer[::-1])

Submission status: Wrong Answer

Solution code:
tmp1 = input()
tmp2 = input()
s = ""
t = ""
if (len(tmp1)<=len(tmp2)):
    s = tmp1
    t = tmp2
else:
    t = tmp1
    s = tmp2

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

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

while(i>0 and j>0):
    if(dp[i][j] != dp[i-1][j-1]):
        ret = s[i-1] + ret
        i -= 1
        j -= 1
    else:
        if(dp[i][j]==dp[i-1][j]):
            i -= 1
        else:
            j -= 1

print(ret)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0 for i in range(m+1)] for j in range(n+1)]
lcs = [[(0,0) for i in range(m+1)] for j in range(n+1)]
for i in range(1,n+1):
  for j in range(1,m+1):
    if dp[i-1][j]>=dp[i][j-1]:
      dp[i][j] = dp[i-1][j]
      lcs[i][j] = (i-1,j)
    else:
      dp[i][j] = dp[i][j-1]
      lcs[i][j] = (i,j-1)
    if s[i-1] == t[j-1] and dp[i-1][j-1]+1>=dp[i][j]:
      dp[i][j] = dp[i-1][j-1]+1
      lcs[i][j] = (i,j)
ans = []
x = dp[n][m]
a = n
b = m
while x:
  if dp[a][b] == dp[a-1][b-1]+1 and dp[a][b] > max(dp[a-1][b],dp[a][b-1]):
    ans.append(s[lcs[a][b][0]-1])
    a -= 1
    b -= 1
    x -= 1
  elif dp[a][b] == dp[a-1][b]:
    a -= 1
  else:
    b -= 1
ans = ans[::-1]

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0 for i in range(m+1)] for j in range(n+1)]
lcs = [[(0,0) for i in range(m+1)] for j in range(n+1)]
for i in range(1,n+1):
  for j in range(1,m+1):
    if dp[i-1][j]>=dp[i][j-1]:
      dp[i][j] = dp[i-1][j]
      lcs[i][j] = (i-1,j)
    else:
      dp[i][j] = dp[i][j-1]
      lcs[i][j] = (i,j-1)
    if s[i-1] == t[j-1] and dp[i-1][j-1]+1>=dp[i][j]:
      dp[i][j] = dp[i-1][j-1]+1
      lcs[i][j] = (i,j)
ans = []
x = dp[n][m]
a = n
b = m
while x:
  if dp[a][b] == dp[a-1][b-1]+1:
    ans.append(s[lcs[a][b][0]-1])
    a -= 1
    b -= 1
    x -= 1
  else:
    b -= 1
ans = ans[::-1]
print(*ans,sep="")

Submission status: Wrong Answer

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

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

while(i>0 and j>0):
    if(dp[i][j] != dp[i-1][j-1]):
        ret = s[i-1] + ret
        i -= 1
        j -= 1
    else:
        if(dp[i][j]==dp[i-1][j]):
            i -= 1
        else:
            j -= 1

print(ret)

Submission status: Wrong Answer

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

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

if (i<j):
    while(i>0 and j>0):
        if(dp[i][j] != dp[i-1][j-1]):
            ret = s[i-1] + ret
            i -= 1
            j -= 1
        else:
            i -= 1
else:
    while(i>0 and j>0):
        if(dp[i][j] != dp[i-1][j-1]):
            ret = t[j-1] + ret
            i -= 1
            j -= 1
        else:
            j -= 1

print(ret)

Submission status: Wrong Answer

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

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

while(i>0 and j>0):
    if(dp[i][j] != dp[i-1][j-1]):
        ret = s[i-1] + ret
        i -= 1
        j -= 1
    else:
        i -= 1

print(ret)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(3000*3000)

A = input()
B = input()

dp = [[None] * (len(B) + 1) for _ in range(len(A) + 1)]
def dfs(a=0, b=0):
    if a >= len(A) or b >= len(B):
        return 0

    if dp[a][b] is not None:
        return dp[a][b]

    match = A[a] == B[b]
    if match:
        r = dfs(a + 1, b + 1) + 1
    else:
        r = max(dfs(a + 1, b), dfs(a, b + 1))
    dp[a][b] = r
    return r

dfs()

# print(dfs())
# print(dp)

# print("---")
# for v in dp:
#     print(*map(lambda x: x if x is not None else "*", v))

def or_inf(v):
    return float('inf') if v is None else v

def reconst(a=0, b=0):
    if a >= len(A) or b >= len(B):
        return ''

    match = A[a] == B[b]
    if match:
        return reconst(a + 1, b + 1) + A[a]
    else:
        if or_inf(dp[a + 1][b]) >= or_inf(dp[a][b + 1]):
            return reconst(a + 1, b)
        else:
            return reconst(a, b + 1)
print(reconst()[::-1])

Submission status: Wrong Answer

Solution code:
s,t=input(),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][j+1]=max(dp[i][j],dp[i][j+1])
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
            continue
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1,dp[i][j+1],dp[i+1][j])

#print(dp)

#部分配列を復元する

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

Submission status: Wrong Answer

Solution code:
def main():
    s=input()
    t=input()
    dp=list([[]]*(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][:]
                dp[i][j].append(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)
    print("".join(dp[len(s)][len(t)]))
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
s = input() + "!"
t = input() + "@"
len_s = len(s)
len_t = len(t)

dp=[[0 for _ in range(3100)] for _ in range(3100)]

# dp[i][j] := sをi+1番目,tをj+1番目まで見たときの最長部分列
# 最後の文字を使うか使わないか
ans = ''
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])

j= len_t - 1
for i in range(len_t)[::-1]:
    while(dp[i][j - 1] == dp[i][j] and j >= 1):
        j -= 1
    if dp[i - 1][j] == dp[i][j]:
        continue
    ans += s[i -1]
print(ans[::-1])

Submission status: Wrong Answer

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

A = len(S)
B = len(T)

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

lcs_len = dp[A][B]
i = A
j = B
ans = ""
while lcs_len > 0:
    if S[i-1] == T[j-1]:
        ans = S[i-1] + ans
        i -= 1
        j -= 1
        lcs_len -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        i -= 1

Submission status: Wrong Answer

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

x = input().rstrip()
y = input().rstrip()

lx = len(x)
ly = len(y)
c1 = [[0 for _ in range(lx+1)] for _ in range(ly+1)]
for i in range(1,ly+1):
    e1 = y[i-1]
    for j in range(1,lx+1):
        if (e1 == x[j-1]):
            c1[i][j] = c1[i-1][j-1] + 1
        else:
            c1[i][j] = max(c1[i-1][j],c1[i][j-1])
i = ly
j = lx
s = ''
bj = j
m = c1[i][j]
while c1[i][j] > 0:
    if c1[i][j] > c1[i-1][j] and c1[i][j] > c1[i][j-1] and c1[i][j] > c1[i-1][j-1] and c1[i][j] == m:
        s = x[j-1] + s
        i = i - 1
        j = j - 1
        bj = j
        m = m - 1
    else:
        j = j - 1
        if j < 1:
            i = i - 1
            j = bj

print (s)

Submission status: Wrong Answer

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

x = input().rstrip()
y = input().rstrip()

lx = len(x)
ly = len(y)
c1 = [[0 for _ in range(lx+1)] for _ in range(ly+1)]
for i in range(1,ly+1):
    e1 = y[i-1]
    for j in range(1,lx+1):
        if (e1 == x[j-1]):
            c1[i][j] = c1[i-1][j-1] + 1
        else:
            c1[i][j] = max(c1[i-1][j],c1[i][j-1])
i = ly
j = lx
s = ''
bj = j
while c1[i][j] > 0:
    if c1[i][j] > c1[i-1][j] and c1[i][j] > c1[i][j-1] and c1[i][j] > c1[i-1][j-1]:
        s = x[j-1] + s
        i = i - 1
        j = j - 1
        bj = j
    else:
        j = j - 1
        if j < 1:
            i = i - 1
            j = bj

print (s)

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
m=len(s)
n=len(t)
#print(m)
#print(n)
C=[[0]*(n+1) for i in  range(m+1)]
#print(C)
ans=""
for i in range(m):
    for j in range(n):
        if(s[i]==t[j]):
            C[i+1][j+1]=C[i][j]+1
            #ans=ans+s[i]
        else:
            if(C[i][j+1]>C[i+1][j]):
                C[i+1][j+1]=C[i][j+1]
            else:
                C[i+1][j+1]=C[i+1][j]
#print(C)
#print(ans)
"""
for i in range(n):
    if(C[0][i+1]>C[0][i]):
        ans+=t[i]
for i in range(m):
    #print(C[i+1][n])
    if(C[i+1][n]>C[i][n]):
        ans+=s[i]
#print(C)
#print(C[:,m])
"""
q=m
p=n
k=C[m][n]
while(1):
    if(k==0):
        break
    if(C[q][p]==C[q-1][p-1]+1):
        k-=1
        print(s[q-1])
        ans+=s[q-1]
        p=p-1
        q=q-1
    else:
        if(C[q][p]==C[q-1][p]):
            q=q-1
        else:
            p=p-1

ans=ans[::-1]
print(ans)

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
m=len(s)
n=len(t)
#print(m)
#print(n)
C=[[0]*(n+1) for i in  range(m+1)]
#print(C)
ans=""
for i in range(m):
    for j in range(n):
        if(s[i]==t[j]):
            C[i+1][j+1]=C[i][j]+1
            #ans=ans+s[i]
        else:
            if(C[i][j+1]>C[i+1][j]):
                C[i+1][j+1]=C[i][j+1]
            else:
                C[i+1][j+1]=C[i+1][j]
#print(C)
#print(ans)
"""
for i in range(n):
    if(C[0][i+1]>C[0][i]):
        ans+=t[i]
for i in range(m):
    #print(C[i+1][n])
    if(C[i+1][n]>C[i][n]):
        ans+=s[i]
#print(C)
#print(C[:,m])
"""
q=m
p=n
k=C[m][n]
while(1):
    if(k==0):
        break
    if(C[q][p]==C[q-1][p-1]+1):
        k-=1
        ans+=s[q-1]
    else:
        if(C[q][p]==C[q][p-1]):
            p=p-1
        else:
            q=q-1

ans=ans[::-1]
print(ans)

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
m=len(s)
n=len(t)
#print(m)
#print(n)
C=[[0]*(n+1) for i in  range(m+1)]
#print(C)
ans=""
for i in range(m):
    for j in range(n):
        if(s[i]==t[j]):
            C[i+1][j+1]=C[i][j]+1
            #ans=ans+s[i]
        else:
            if(C[i][j+1]>C[i+1][j]):
                C[i+1][j+1]=C[i][j+1]
            else:
                C[i+1][j+1]=C[i+1][j]
#print(C)
#print(ans)
for i in range(n):
    if(C[0][i+1]>C[0][i]):
        ans+=t[i]
for i in range(m):
    #print(C[i+1][n])
    if(C[i+1][n]>C[i][n]):
        ans+=s[i]
#print(C)
#print(C[:,m])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)


def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)

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

    for i, sc in enumerate(s):
        for j, tc in enumerate(t):
            if sc == tc:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

    def to_s():
        i = ls
        j = lt
        ans = ""
        while i > 0 and j > 0:
            if dp[i][j] == dp[i - 1][j]:
                i -= 1
                continue
            if dp[i][j] == dp[i][j-1]:
                j -= 1
                continue
            ans = ans + s[i-1]
            i -= 1
            j -= 1

        return ans

    print(to_s())


main()

Submission status: Wrong Answer

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

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

ret = ""
for i in range(1,ls+1):
    if dp[-1][i] != dp[-1][i-1]:
        ret += s[i-1]
    
print(ret)

Submission status: Wrong Answer

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


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

for i, s in enumerate(S):
  for j, t in enumerate(T):
    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])

ans = []
s = (len(S)-1, len(T)-1)
while True:
  x, y = s
  if x < 0 or y < 0:
    break
  if S[x] == T[y]:
    ans.append(S[x])
    s = (x-1, y-1)
  else:
    if dp[x-1][y] > dp[x][y-1]:
      s = (x-1, y)
    else:
      s = (x, y-1)

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

Submission status: Wrong Answer

Solution code:
#import numpy as np
s = input()
t = input()
n, m = len(s), len(t)

# dp
# dp[i][j] := s[:i]とt[:j]の最長共通
dp = [[0]*m for _ in range(n)]

# 0th
for i in range(n):
    if s[i]==t[0]:
        dp[i][0]=1
    else:
        dp[i][0]=0

# 0th
for i in range(m):
    if s[0]==t[i]:
        dp[0][i]=1
    else:
        dp[0][i]=0

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

res = ''
i, j = n-1, m-1
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        res += s[i]
        i -= 1
        j -= 1
    else:
        if dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
answer = res[::-1]
print(answer)

Submission status: Wrong Answer

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

# dp
# dp[i][j] := s[:i]とt[:j]の最長共通
dp = [[0]*m for _ in range(n)]

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

res = ''
i, j = n-1, m-1
while i>=0 and j>=0:
    if s[i]==t[j]:
        res += s[i]
        i -= 1
        j -= 1
    elif i==0:
        j -= 1
    elif j==0:
        i -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
answer = res[::-1]
print(answer)

Submission status: Wrong Answer

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

# dp
# dp[i][j] := s[:i]とt[:j]の最長共通
dp = [[0]*m for _ in range(n)]

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

tmp = 0
res = []
for i in range(n):
    for j in range(m):
        if tmp < dp[i][j]:
            tmp = dp[i][j]
            res.append(s[i])
answer = ''.join(res)
print(answer)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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


M = dp[n][m]
ans = []
i = n; j = m
while i != 0 and j != 0:
  # print(i,j,repair[i][j])
  ni,nj = repair[i][j]
  if dp[ni][nj] < dp[i][j]:
    ans.append(s[ni])
  i,j = ni,nj
ans.reverse()
print(*ans, sep = "")
print(dp)
print(repair)