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:
s,t=[tuple(input()) for u in (1,1)]
l,li=[['' for i in range(len(s)+1)] for j in (1,1)]
f=0
for j in range(len(t)):
  for i in range(len(s)):
    if f:
      if t[j]==s[i]:
        l[i+1]=li[i]+t[j]
      else:l[i+1]=li[i+1] if len(li[i+1])>len(l[i]) else l[i]
    else:
      if t[j]==s[i]:
        li[i+1]=l[i]+t[j]
      else:li[i+1]=l[i+1] if len(l[i+1])>len(li[i]) else li[i]
    f=(f+1)%2
print(li[-1] if f else l[-1])

Submission status: Wrong Answer

Solution code:
# to measure the processing time

S = input()
T = input()

dp = [[0] * (len(T)+1) for i in range(len(S)+1)]
for i, s in enumerate(S, 1):
  for j, t in enumerate(T, 1):
    if s == t:
      dp[i][j] = dp[i-1][j-1] + 1
    else:
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Submission status: Wrong Answer

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

### LCS - Longest Common Sequence ###
def lcs(S, T):
  LS = len(S)
  LT = len(T)
 
  dp=[[0 for _ in range(LT + 1)] for _j in range(LS + 1)]
  # dp[Sのi番目][Tのj番目] := それまでの最大長
 
  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])
  
  return dp

dp = lcs(S, T)
i = len(dp)-1
lj = len(dp[0])-1
j = lj
answer = ""
while 1:
  if dp[i-1][j-1] == dp[i-1][j] == dp[i][j-1] == dp[i][j] - 1:
    lj = j - 1
    answer += S[i-1]
    i -= 1
  j -= 1
  if j < 0:
    if i > 0:
      j = lj
      i -= 1
    else:
      break
print(answer[::-1])

Submission status: Wrong Answer

Solution code:
S = list(input())
T = list(input())
MAX_LEN = 3007
dp = [[0] * MAX_LEN for _ in range(MAX_LEN)]

for i in range(len(S)):
    for j in range(len(T)):
        ii = i + 1
        jj = j + 1
        if S[i] == T[j]:
            dp[ii][jj] = dp[ii - 1][jj - 1] + 1
        else:

            dp[ii][jj] = max(dp[ii - 1][jj],
                             dp[ii][jj - 1]
                             )

i = len(S)
j = len(T)
from collections import deque

ans = deque(maxlen=dp[i][j])
while i > 0 and j > 0:
    if dp[i][j] - 1 == dp[i - 1][j - 1]:
        ans.appendleft(S[i - 1])
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        i -= 1
print(*ans, sep='')

Submission status: Wrong Answer

Solution code:
S = list(input())
T = list(input())
MAX_LEN = 3007
dp = [[0] * MAX_LEN for _ in range(MAX_LEN)]

for i in range(len(S)):
    for j in range(len(T)):
        ii = i + 1
        jj = j + 1
        if S[i] == T[j]:
            dp[ii][jj] = dp[ii - 1][jj - 1] + 1
        else:

            dp[ii][jj] = max(dp[ii - 1][j],
                             dp[ii][jj - 1]
                             )

i = len(S)
j = len(T)
from collections import deque

ans = deque(maxlen=dp[i][j])
while i > 0 and j > 0:
    if dp[i][j] - 1 == dp[i - 1][j - 1]:
        ans.appendleft(S[i - 1])
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        i -= 1
print(*ans, sep='')

Submission status: Wrong Answer

Solution code:
S = list(input())
T = list(input())
MAX_LEN = 3007
dp = [[0] * MAX_LEN for _ in range(MAX_LEN)]

for i in range(len(S)):
    for j in range(len(T)):
        ii = i + 1
        jj = j + 1
        if S[i] == T[j]:
            dp[ii][jj] = max(dp[ii - 1][j],
                             dp[ii][jj - 1],
                             dp[ii - 1][jj - 1] + 1)
        else:

            dp[ii][jj] = max(dp[ii - 1][j],
                             dp[ii][jj - 1]
                             )

i = len(S)
j = len(T)
from collections import deque
ans = deque(maxlen=dp[i][j])
while i > 0 and j > 0:
    if dp[i][j] > dp[i - 1][j - 1]:
        ans.appendleft(S[i - 1])
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        i -= 1
print(*ans,sep='')

Submission status: Wrong Answer

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

dp = [[0]*(lt+1) for i in range(ls+1)]
ans, ai, aj = '', -1, -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
            if i > ai and j > aj:
                ans += s[i]
                ai, aj = i, j
        else:
            dp[i+1][j+1] = max([dp[i+1][j], dp[i][j+1]])

print(ans)

Submission status: Wrong Answer

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

dp = [[0]*(lt+1) for i in range(ls+1)]
ans, ai, aj = '', -1, -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
            if i > ai and j > aj:
                ans += s[i]
                ai, aj = i, j
        else:
            dp[i+1][j+1] = max([dp[i+1][j], dp[i][j+1]])
    print(dp[i+1])
print(ans)

Submission status: Wrong Answer

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

S = input()
T = input()

# print(S, T)

# lcs[Sのi文字目まで][Tのj文字目まで]
# 求める答えはlcs[len(S)][len(T)]
lcs = [[0 for _ in range(len(T)+1)] for __ in range(len(S)+1)]

for i in range(1, len(S)+1):
  for j in range(1, len(T)+1):
    if S[i-1] == T[j-1]:
      lcs[i][j] = max(lcs[i-1][j-1] + 1, lcs[i-1][j], lcs[i][j-1])
    else:
      # print(i,j)
      lcs[i][j] = max(lcs[i][j-1], lcs[i-1][j])

# print(lcs)
# print(lcs[len(S)][len(T)])

lcs_string = ""

i, j = len(S), len(T)

while (i > 0 and j > 0):
  if lcs[i][j] == lcs[i-1][j-1] + 1:
    lcs_string = S[i-1] + lcs_string
    i -= 1
    j -= 1
  elif lcs[i][j] == lcs[i-1][j]:
    i -= 1
  elif lcs[i][j] == lcs[i][j-1]:
    j -= 1

print(lcs_string)

Submission status: Wrong Answer

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

S = input()
T = input()

# print(S, T)

# lcs[Sのi文字目まで][Tのj文字目まで]
# 求める答えはlcs[len(S)][len(T)]
lcs = [[0 for _ in range(len(T)+1)] for __ in range(len(S)+1)]

for i in range(1, len(S)+1):
  for j in range(1, len(T)+1):
    if S[i-1] == T[j-1]:
      lcs[i][j] = max(lcs[i-1][j-1] + 1, lcs[i-1][j], lcs[i][j-1])
    else:
      # print(i,j)
      lcs[i][j] = max(lcs[i][j-1], lcs[i-1][j])

# print(lcs)
# print(lcs[len(S)][len(T)])

lcs_string = ""

i, j = len(S), len(T)

while i > 0 and j > 0:
  if lcs[i][j] == lcs[i-1][j-1] + 1:
    lcs_string = S[i-1] + lcs_string
    i -= 1
    j -= 1
  elif lcs[i][j] == lcs[i-1][j]:
    i -= 1
  elif lcs[i][j] == lcs[i][j-1]:
    j -= 1

print(lcs_string)

Submission status: Wrong Answer

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

S = input()
T = input()

# print(S, T)

# lcs[Sのi文字目まで][Tのj文字目まで]
# 求める答えはlcs[len(S)][len(T)]
lcs = [[0 for _ in range(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]:
      lcs[i+1][j+1] = max(lcs[i][j] + 1, lcs[i+1][j], lcs[i][j+1])
    else:
      # print(i,j)
      lcs[i+1][j+1] = max(lcs[i][j+1], lcs[i+1][j])

# print(lcs)
# print(lcs[len(S)][len(T)])

lcs_string = ""

i, j = len(S), len(T)

while i > 0 and j > 0:
  if lcs[i][j] == lcs[i-1][j-1] + 1:
    lcs_string = S[i-1] + lcs_string
    i -= 1
    j -= 1
  elif lcs[i][j] == lcs[i-1][j]:
    i -= 1
  elif lcs[i][j] == lcs[i][j-1]:
    j -= 1

print(lcs_string)

Submission status: Wrong Answer

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

S = input()
T = input()

# print(S, T)

# lcs[Sのi文字目まで][Tのj文字目まで]
# 求める答えはlcs[len(S)][len(T)]
lcs = [[0 for _ in range(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]:
      lcs[i+1][j+1] = max(lcs[i][j] + 1, lcs[i-1][j], lcs[i][j-1])
    else:
      # print(i,j)
      lcs[i+1][j+1] = max(lcs[i][j+1], lcs[i+1][j])

# print(lcs)
# print(lcs[len(S)][len(T)])

lcs_string = ""

i, j = len(S), len(T)

while i > 0 and j > 0:
  if lcs[i][j] == lcs[i-1][j-1] + 1:
    lcs_string = S[i-1] + lcs_string
    i -= 1
    j -= 1
  elif lcs[i][j] == lcs[i-1][j]:
    i -= 1
  elif lcs[i][j] == lcs[i][j-1]:
    j -= 1

print(lcs_string)

Submission status: Wrong Answer

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

S = input()
T = input()

# print(S, T)

# lcs[Sのi文字目まで][Tのj文字目まで]
# 求める答えはlcs[len(S)][len(T)]
lcs = [[0 for _ in range(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]:
      lcs[i+1][j+1] = lcs[i][j] + 1
    else:
      # print(i,j)
      lcs[i+1][j+1] = max(lcs[i][j+1], lcs[i+1][j])

# print(lcs)
# print(lcs[len(S)][len(T)])

lcs_string = ""

i, j = len(S), len(T)

while i > 0 and j > 0:
  if lcs[i][j] == lcs[i-1][j-1] + 1:
    lcs_string = S[i-1] + lcs_string
    i -= 1
    j -= 1
  elif lcs[i][j] == lcs[i-1][j]:
    i -= 1
  elif lcs[i][j] == lcs[i][j-1]:
    j -= 1

print(lcs_string)

Submission status: Wrong Answer

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

S = input()[:-1]
T = input()[:-1]

# print(S, T)

# lcs[Sのi文字目まで][Tのj文字目まで]
# 求める答えはlcs[len(S)][len(T)]
lcs = [[0 for _ in range(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]:
      lcs[i+1][j+1] = lcs[i][j] + 1
    else:
      # print(i,j)
      lcs[i+1][j+1] = max(lcs[i][j+1], lcs[i+1][j])

# print(lcs)
# print(lcs[len(S)][len(T)])

lcs_string = ""

i, j = len(S), len(T)

while i > 0 and j > 0:
  if lcs[i][j] == lcs[i-1][j-1] + 1:
    lcs_string = S[i-1] + lcs_string
    i -= 1
    j -= 1
  elif lcs[i][j] == lcs[i-1][j]:
    i -= 1
  elif lcs[i][j] == lcs[i][j-1]:
    j -= 1
  else:
    pdb.set_trace()

print(lcs_string)

Submission status: Wrong Answer

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

S = input()[:-1]
T = input()[:-1]

# print(S, T)

# lcs[Sのi文字目まで][Tのj文字目まで]
# 求める答えはlcs[len(S)][len(T)]
lcs = [[0 for _ in range(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]:
      lcs[i+1][j+1] = lcs[i][j] + 1
    else:
      # print(i,j)
      lcs[i+1][j+1] = max(lcs[i][j+1], lcs[i+1][j])

# print(lcs)
# print(lcs[len(S)][len(T)])

lcs_string = ""

i, j = len(S), len(T)

while i > 0 and j > 0:
  if lcs[i][j] == lcs[i-1][j-1] + 1:
    lcs_string = S[i-1] + lcs_string
    i -= 1
    j -= 1
  elif lcs[i][j] == lcs[i-1][j]:
    i -= 1
  elif lcs[i][j] == lcs[i][j-1]:
    j -= 1

print(lcs_string)

Submission status: Wrong Answer

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

dp = ['']* len(t)
# dp_len = [0]* len(t)

for i in range(len(s)):
    s_temp = s[i]
    temp_max = ''
    for j in range(len(t)):
        if(s_temp == t[j]):
            dp_temp = temp_max + s_temp
        else:
            dp_temp = dp[j]

        if( len(dp[j]) > len(temp_max)):
            temp_max = dp[j]
        dp[j] = dp_temp

if( len(dp_temp) > len(temp_max)):
    temp_max = dp_temp

print(temp_max)

Submission status: Wrong Answer

Solution code:
s1=input()
s2=input()
m=len(s1)
n=len(s2)
lcs=[[(0,'') for i in range(n+1)] for j in range(m+1)]
for i in range(m):
    for j in range(n):
        if s1[i]==s2[j]:
            lcs[i+1][j+1]=(lcs[i][j][0]+1,s1[i])
        else:
            if lcs[i][j+1]>lcs[i+1][j]:
                lcs[i+1][j+1]=lcs[i][j+1]
            else:
                lcs[i+1][j+1]=lcs[i+1][j]
ans=''
i=m
j=n
while i!=0 and j!=0:
    if lcs[i-1][j][0]==lcs[i][j-1][0]:
        if lcs[i-1][j][0]!=lcs[i][j][0]:
            ans+=lcs[i][j][1]
        i-=1
        j-=1
    elif lcs[i][j-1][0]>lcs[i-1][j][0]:
        j-=1
    else:
        i-=1
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
s = list(input())
t = list(input())
a = len(s)
b = len(t)
dp = [[0]*(b+1) for _ in range(a+1)]
ans = ""
#dp[i][j]はi文字目までのsとtのj文字目までの共通部分
for i in range(a):
  for j in range(b):
    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])
print(dp[-1][-1])
i = a
j = b
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 = t[j-1]+ans
    i -= 1
    j -= 1
print(ans)

Submission status: Wrong Answer

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

    # dp[s][t]: value
    dp = [[False for _ in range(len(t))] for _ in range(len(s))]

    for s_i in range(len(s)):
        for t_i in range(len(t)):
            if s[s_i] == t[t_i]:
                dp[s_i][t_i] = True

    ret = ""
    max_t_i = 0
    for s_i in range(len(s)):
        for t_i in range(max_t_i, len(t)):
            if dp[s_i][t_i]:
                max_t_i = t_i
                ret += s[s_i]
                break

    # print("dp={}".format(dp))

    print(ret)


main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
lenS = len(S)
lenT = len(T)
dp = [[0 for _ in range(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:
      if dp[i+1][j] >= dp[i][j+1]:
        dp[i+1][j+1] = dp[i+1][j]
      else:
         dp[i+1][j+1] = dp[i][j+1]

ans = ''
n = lenS
m = lenT
while (n>0 and m>0):
  if S[n-1] != T[m-1]:
    if dp[n-1][m] >= dp[n][m-1]: n -= 1
    else: m -= 1
  else:
    ans += S[n-1]
    n -= 1
    m - -1
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
lenS = len(S)
lenT = len(T)
dp = [[0 for _ in range(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 = ''
n = lenS
m = lenT
while (n>0 and m>0):
  if S[n-1] != T[m-1]:
    if dp[n-1][m] >= dp[n][m-1]: n -= 1
    else: m -= 1
  else:
    ans += S[n-1]
    n -= 1
    m - -1
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
lenS = len(S)
lenT = len(T)
dp = [[0 for _ in range(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 = ''
n = lenS
m = lenT
while (n>0 and m>0):
  if S[n-1] != T[m-1]:
    if dp[n-1][m] > dp[n][m-1]: n -= 1
    else: m -= 1
  else:
    ans += S[n-1]
    n -= 1
    m - -1
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
a=[[""]*(len(t)+1)for i in range(len(s)+1)]
b=[[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]:
            b[i+1][j+1]=b[i][j]+1
            a[i+1][j+1]=a[i][j]+s[i]
        else:
            if b[i][j+1]>b[i+1][j]:
                b[i+1][j+1]=b[i][j+1]
                a[i+1][j+1]=a[i][j+1]
            else:
                b[i+1][j+1]=b[i][j+1]
                a[i+1][j+1]=a[i+1][j]
print(a[-1][-1])

Submission status: Wrong Answer

Solution code:
s = list(input())
t = list(input())
a = len(s)
b = len(t)
dp = [[""]*(b+1) for _ in range(a+1)]
#dp[i][j]はi文字目までのsとtのj文字目までの共通部分
for i in range(a):
  for j in range(b):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j]+s[i]
    else:
      dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
print(dp[-1][-1])