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:
import sys
s= sys.stdin.readline() 
t= sys.stdin.readline() 
Ns=len(s)
Nt=len(t)
dp=[["" for i in range(Nt+1)]for j in range(Ns+1)]
for i in range(1,Ns+1):
    for j in range(1,Nt+1):
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+s[i-1]
        else:
            if len(dp[i][j-1])>len(dp[i-1][j]):
                dp[i][j]=dp[i][j-1]
            else:
                dp[i][j]=dp[i-1][j]

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

S = np.frombuffer(readline().rstrip(),'S1')
T = np.frombuffer(readline().rstrip(),'S1')

S,T

def LCS(S,T):
    LS = len(S); LT = len(T)
    dp = np.zeros((LS+1,LT+1),np.int64)
    for n,s in enumerate(S,1):
        equal = (s == T)
        np.maximum(dp[n,1:],dp[n-1,:-1]+equal*1,out=dp[n,1:])
        np.maximum.accumulate(dp[n],out=dp[n])
    return dp

dp = LCS(S,T)

answer = []
max_len = dp[-1,-1]
for n in range(len(S),0,-1):
    if max_len == 0:
        break
    equal = (S[n-1]==T)
    ind = np.where((dp[n,1:]*equal)==max_len)[0]
    if len(ind):
        i = ind[0]
        answer.append(T[i].decode('utf-8'))
        dp = dp[:,:i+1]; T = T[:i]
        max_len -= 1

print(''.join(answer[::-1]))

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
L=[]
for i in s:
	idx=-1
	for j in range(len(t)):
		if(t[j]==i):
			idx=j
	if (idx>=0):
		L.append([idx,i])
for i in range(len(L)-2,-1,-1):
	maxlen=-1
	index1=-1
	for j in range (i+1,len(L)):
		if(L[j][0]>L[i][0] and len(L[j][1])>maxlen):
			maxlen=len(L[j][1])
			index1=j
	if(index1>=0):
		L[i][1]=L[i][1]+L[index1][1]
if(len(L)==0):
	print('')
else:
	print(L[0][1])

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
s_length = len(s)
t_length = len(t)

dp = [[0 for j in range(t_length+1)] for i in range(s_length+1)]
#dp[i][j] = s[:i]とt[:j]に置けるLCS
for i in range(s_length):
    for j in range(t_length):
        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])

#print(dp)
#print(dp[s_length][t_length])

ans = ""
now = t_length
for i in range(s_length-1,-1,-1):
    if dp[i+1][now] == dp[i][now] + 1:
        ans += s[i]
        now -= 1

print(ans[::-1])

Submission status: Wrong Answer

Solution code:
import sys
def main():
  S=list(sys.stdin.readline())[:-1]
  T=list(sys.stdin.readline())[:-1]
  lS=len(S)
  lT=len(T)
  dp=[[0]*lS for _ in range(lT)]
  for iT in range(lT):
    for iS in range(lS):
      if S[iS]==T[iT]:
        if iS-1>=0 and iT-1>=0:
          dp[iT][iS] = dp[iT-1][iS-1]+1
        else:
          dp[iT][iS] = 1
      else:
        if iS-1>=0 and (iT-1<0 or dp[iT][iS-1]>=dp[iT-1][iS]):
          dp[iT][iS] = dp[iT][iS-1]
        elif iT-1>=0 and (iS-1<0 or dp[iT-1][iS]>=dp[iT][iS-1]):
          dp[iT][iS] = dp[iT-1][iS]

  iS = lS-1
  iT = lT-1
  ans = ""
  while(iS>0 and iT>0):
    if dp[iT][iS]==dp[iT-1][iS-1]:
      iS -= 1
      iT -= 1
    elif dp[iT][iS]==dp[iT][iS-1]:
      iS -= 1
    else:
      ans = S[iS]+ans
      iS -= 1
      iT -= 1
  if dp[iT][iS]==1:
    if iS == 0:
      ans = S[0]+ans
    else:
      ans = T[0]+ans
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline

class Solver(object):
    def __init__(self):
        pass

    def solve(self,s:str,t:str) -> int:
        ## DP loop
        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+1][j],dp[i][j+1])
        
        prev = 0
        ans = ""

        ## Recover the LCS from DP table
        ## checking the update point
        for i,LCS in enumerate(dp[-1]):
            if prev != LCS:
                ans += t[i-1]
            prev = LCS

        return ans

def main():
    s = input().rstrip()
    t = input().rstrip()
    solver = Solver()
    print(solver.solve(s,t))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
S = str(input())
T = str(input())
Slen = len(S)
Tlen = len(T)
dp = [[""] * (Tlen) for _ in range(Slen)]
anslen = int(0)

s = int(0)
d = int(0)
while (s==0 and d<Tlen):
    if S[0]==T[d]:
        s = 1
    d +=1
for i in range(d,Tlen):
    dp[0][i] = S[0]

t = int(0)
d = int(0)
while (t==0 and d<Slen):
    if S[d]==T[0]:
        t = 1
    d +=1
for i in range(d,Slen):
    dp[i][0] = T[0]

for i in range(1,Slen):
    for j in range(1,Tlen):
        if S[i]==T[j]:
            if len(dp[i-1][j-1])+1>len(dp[i][j]):
                dp[i][j] = dp[i-1][j-1]+S[i]
        if max(len(dp[i][j]),len(dp[i-1][j]),len(dp[i][j-1]))==len(dp[i-1][j]):
            dp[i][j] = dp[i-1][j]
        elif max(len(dp[i][j]),len(dp[i-1][j]),len(dp[i][j-1]))==len(dp[i][j-1]):
            dp[i][j] = dp[i][j-1]

ans = dp[Slen-1][Tlen-1]

print(ans)

Submission status: Wrong Answer

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


def solve(s: str, t: str):
    N = len(s)
    W = len(t)
    dp = [[0] * (W+1) for i in range(N+1)]

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

    ans = []
    while N > 0 and W > 0:
        if(dp[N][W] == dp[N-1][W]):
            N -= 1
        elif(dp[N][W] == dp[N][W-1]):
            W -= 1
        elif(dp[N][W] == dp[N-1][W-1]+1):
            ans += s[N-1]
            N -= 1
            W -= 1


    print(''.join(ans))

    return


# Generated by 1.1.4 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: Wrong Answer

Solution code:
s = input()
t = input()
Ls = len(s)
Lt = len(t)

dp = [[0]*(Ls+1) for i in range(Lt+1)]
Lans = 0

for i in range(1,Lt+1):
  for j in range(1,Ls+1):
    if s[j-1] == t[i-1]:
      dp[i][j] = dp[i-1][j-1] + 1
    else:
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    Lans = max(Lans,dp[i][j])
i = Lt
j = Ls
ans = [""]*Lans
count = 0
while Lans > 0:
  if s[j-1] == t[i-1]:
    Lans -= 1
    ans[Lans] = s[j-1]
    i -= 1
    j -= 1
    count += 1
  else:
    if j>1:
      j -= 1
    else:
      i -= 1
      j = Ls-count

print("".join(ans))

Submission status: Wrong Answer

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

DP = [""] * (len(S)+1)

for t in range(1, len(T)+1):
    next = [""] * (len(S)+1)
    for s in range(1, len(S)+1):
        if S[s-1] == T[t-1]:
            next[s] = next[s-1] + S[s-1]
        else:
            next[s] = DP[s] if len(DP[s]) > len(next[s-1]) else next[s-1]
    DP = next


print(DP[len(S)])

Submission status: Wrong Answer

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

DP = []
for _ in range(len(T)+1):
    DP.append([""] * (len(S)+1))


if S[0] == T[0]:
    DP[0][0] = S[0]

for t in range(1, len(T)+1):
    for s in range(1, len(S)+1):
        if S[s-1] == T[t-1]:
            DP[t][s] = DP[t][s-1] + S[s-1]
        else:
            if len(DP[t][s-1]) > len(DP[t-1][s]):
                DP[t][s] = DP[t][s-1]
            else:
                DP[t][s] = DP[t-1][s]


print(DP[len(T)][len(S)])

Submission status: Wrong Answer

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

ret_rev = ""

i, j = len(s) - 1, len(t) - 1
while i >= 0 and j >= 0:
    if dp[i + 1][j + 1] == dp[i][j] + 1:
        ret_rev += s[i]
        i, j = i - 1, j - 1
    elif dp[i + 1][j] == dp[i][j]:
        i, j = i - 1, j
    else: # i.e. dp[i][j + 1] == dp[i][j]
        i, j = i, j - 1

ret = ret_rev[::-1]

print(ret)

Submission status: Wrong Answer

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

ret_rev = ""

i, j = len(s) - 1, len(t) - 1
while i >= 0 and j >= 0:
    if dp[i + 1][j + 1] == dp[i][j] + 1:
        i, j = i - 1, j - 1
        ret_rev += s[i + 1]
    elif dp[i + 1][j] == dp[i][j]:
        i, j = i - 1, j
    else: # i.e. dp[i][j + 1] == dp[i][j]
        i, j = i, j - 1

ret = ret_rev[::-1]

print(ret)

Submission status: Wrong Answer

Solution code:
"""
Longest Common Subsequence
axyb
abyxb
-> axb or ayb
最長の共通部分文字列を取り出す
"""

S = input()
T = input()

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

ns = len(S)
ts = len(T)
# for i in range(ns+1):
#     print(*dp[i][:ts+1])

cnt = dp[ns][ts]
ans_r = ""
for i in range(ns,-1,-1):
    flg = True
    for j in range(ts,-1,-1):
        if flg and dp[i][j] == dp[i+1][j] == dp[i][j+1] == dp[i+1][j+1] -1 == cnt-1: 
            print(i,j,cnt, S[i],T[j])
            ans_r += S[i]
            flg = False
            cnt -= 1
print(ans_r[::-1])

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
N = len(s)
M = len(t)

dp = [[0]*(N+1) for i in range(M+1)]

for i in range(1,M+1):
  for j in range(1,N+1):
    dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    if s[j-1] == t[i-1]:
      dp[i][j] += 1
L = dp[-1][-1]
i = M
j = N
ans = [""]*L
cur = L-1
while i>=0 and j>=0:
  if dp[i][j] != dp[i-1][j] and dp[i][j] != dp[i][j-1]:
    ans[cur] = s[j-1]
    i -= 1
    j -= 1
    cur -= 1
  elif dp[i][j] == dp[i-1][j]:
    i -= 1
  else:
    j -= 1
print("".join(ans))

Submission status: Wrong Answer

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

dp_list = [ [ 0 for i in range(ls+1) ] for j in range(lt+1) ]

for i in range(lt):
    for j in range(ls):
        if t[i] == s[j]:
            a = dp_list[i][j] + 1 
            b = dp_list[i+1][j]
            c = dp_list[i][j+1]
            p = [a,b,c].index(max(a,b,c))
            dp_list[i+1][j+1] = [a,b,c][p]
        else:
            a = dp_list[i][j]
            b = dp_list[i+1][j]
            c = dp_list[i][j+1]
            p = [a,b,c].index(max(a,b,c))
            dp_list[i+1][j+1] = [a,b,c][p]          
print(dp_list[-1][-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#DPS F LSC 
s=input()
t=input()
a,b=len(s),len(t)
dp=[[""]*b for _ in range(a)]
c=-1
for i in range(b):
    if s[0]==t[i]:
        c=i
        break
if c>=0:
    for i in range(c,b):
        dp[0][i]=s[0]
for i in range(1,a):
    for j in range(1,b):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]+s[i]          
        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[a-1][b-1])

Submission status: Wrong Answer

Solution code:
#DPS F LSC 
s=input()
t=input()
a,b=len(s),len(t)
dp=[[" "]*(b+1) for _ in range(a+1)]
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:
            if len(dp[i+1][j])<len(dp[i][j]):
                dp[i+1][j]=dp[i][j]
            if len(dp[i][j+1])<len(dp[i][j]):
                dp[i][j+1]=dp[i][j]
ans=""
for i in range(1,b+1):
    if len(dp[a][i])>len(dp[a][i-1]):
        ans=dp[a][i]
print(ans[1:])

Submission status: Wrong Answer

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

S = len(s)
T = len(t)

dp = [[0 for _ in range(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]+1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
'''
for i in rage(S+1):
    print(dp[i])
'''

L =[]
while S>0 and T>0:
    if dp[S][T] != dp[S-1][T-1]+1:
        if dp[S][T] !=dp[S-1][T]:
            T-=1
        else:
            S-=1
    else:
        L.append(s[S-1])
        S-=1
        T-=1
print(''.join(L[::-1]))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#EDPC F

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

res = ''
while n > 0 and m > 0:
    if dp[n][m] == dp[n-1][m-1] + 1:
        res += s[n-1]
        n -= 1
        m -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    elif dp[n][m] == dp[n-1][m]:
        n -= 1

print(res[::-1])

Submission status: Wrong Answer

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

S = len(s)
T = len(t)

dp = [[0 for _ in range(T)] for _ in range(S)]
#初期条件
if s[0] == t[0]:
    dp[0][0] =1
for j in range(1, T):
    if s[0] == t[j]:
        dp[0][j] =1
    dp[0][j] = min(1, dp[0][j-1])
        
    
#print(dp)

for i in range(1, S):
    for j in range(T):
        if j ==0:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = dp[i][j-1]
        if s[i] == t[j]:
            dp[i][j] +=1
#print(dp)
ans =[]
k = 1
for i in range(S):
    for j in range(T):
        if dp[i][j] ==k:
            ans.append(s[i])
            k+=1
            break
print(''.join(ans))

Submission status: Wrong Answer

Solution code:
# 最長共通部分　LCS
strA = input()
strB = input()
### 一致したら左上+1、そうでない場合は上か左のMAX
# / | 0 | A | B | C | B | A |
# 0 | 0 | 0 | 0 | 0 | 0 | 0 |
# B | 0 | 0 | 1 | 1 | 1 | 1 |
# B | 0 | 0 | 1 | 1 | 2 | 2 |
# A | 0 | 0 | 1 | 1 | 2 | 3 |
dp = [[0] * (len(strA) + 1) for _ in range(len(strB) + 1)]

for i, A in enumerate(strA, 1):
    for j, B in enumerate(strB, 1):
        if A == B:
            dp[j][i] = dp[j - 1][i - 1] + 1
        else:
            dp[j][i] = max(dp[j - 1][i], dp[j][i - 1])
ans = ""
cnt = 1
lstAns = dp[-1]
for i, DP in enumerate(lstAns):
    if cnt == DP:
        cnt += 1
        ans += strA[i - 1]
print(ans)

Submission status: Wrong Answer

Solution code:
# 最長共通部分　LCS
strA = input()
strB = input()
### 一致したら左上+1、そうでない場合は上か左のMAX
# / | 0 | A | B | C | B | A |
# 0 | 0 | 0 | 0 | 0 | 0 | 0 |
# B | 0 | 0 | 1 | 1 | 1 | 1 |
# B | 0 | 0 | 1 | 1 | 2 | 2 |
# A | 0 | 0 | 1 | 1 | 2 | 3 |
dp = [[0] * (len(strA) + 1) for _ in range(len(strB) + 1)]

for i, A in enumerate(strA, 1):
    for j, B in enumerate(strB, 1):
        if A == B:
            dp[j][i] = dp[j - 1][i - 1] + 1
        else:
            dp[j][i] = max(dp[j - 1][i], dp[j][i - 1])

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

Submission status: Wrong Answer

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

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

    for i in range(1, s_len+1):
        for j in range(1, t_len+1):
            dp[i][j] = maxLength(dp[i][j-1], dp[i-1][j])
            if s[i-1] == t[j-1]:
                dp[i][j] = maxLength(dp[i][j-1], dp[i-1][j]+s[i-1])

    print(dp[s_len][t_len])


def maxLength(a, b):
    if len(a) >= len(b):
        return a
    else:
        return b


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
  s = input()
  t = input()
  a = len(s)
  b = len(t)
  dp = [[0]*(b+1) for _ in range(a+1)]
  prev_w = [[0]*(b+1) for _ in range(a+1)]
  for i in range(a):
    for j in range(b):
      if s[i]==t[j]:
        if dp[i][j]+1>dp[i+1][j+1]:
          dp[i+1][j+1] = dp[i][j]+1
          prev_w[i+1][j+1] = [i,j]
      else:
        if dp[i+1][j]>dp[i][j+1]:
          dp[i+1][j+1]=dp[i+1][j]
          prev_w[i+1][j+1] = [i+1,j]
        else:
          dp[i+1][j+1]=dp[i][j+1]
          prev_w[i+1][j+1] = [i,j+1]
  #print(dp[a][b])
  #print(prev_w[1][3])
  ans = ''
  while a!=0 and b !=0:
    l = dp[a][b]
    a,b=prev_w[a][b]
    if l>dp[a][b]:
      ans =s[a]+ans
  print(ans)
print(main())

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)]
prev_w = [[0]*(b+1) for _ in range(a+1)]
for i in range(a):
  for j in range(b):
    if s[i]==t[j]:
      if dp[i][j]+1>dp[i+1][j+1]:
        dp[i+1][j+1] = dp[i][j]+1
        prev_w[i+1][j+1] = [i,j]
    else:
      if dp[i+1][j]>dp[i][j+1]:
        dp[i+1][j+1]=dp[i+1][j]
        prev_w[i+1][j+1] = [i+1,j]
      else:
        dp[i+1][j+1]=dp[i][j+1]
        prev_w[i+1][j+1] = [i,j+1]
#print(dp[a][b])
#print(prev_w[1][3])
ans = ''
while a!=0 and b !=0:
  l = dp[a][b]
  a,b=prev_w[a][b]
  if l>dp[a][b]:
    ans +=s[a]
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

l = max(ls,lt)

DP = [[[] for __ in range(ls)] for _ in range(lt)]

for i in range(ls):
  for j in range(lt):
    a = 0
    if s[i] == t[j]:
      a = 1
      ad = s[i]
    mx = max (len(DP[j-1][i]),len(DP[j][i-1]),len(DP[j-1][i-1])+a)
    if len(DP[j-1][i]) == mx:
        DP[j][i] = DP[j-1][i]
    elif len(DP[j][i-1]) == mx:
        DP[j][i] = DP[j][i-1]
    else:
        if a==1:####?
            DP[j][i] = DP[j-1][i-1] + [ad]
        else:
            DP[j][i] =DP[j-1][i-1]
ans = ''.join(DP[lt-1][ls-1])
print(ans)

Submission status: Wrong Answer

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

dp = [ ['' for _ in range(len(t))] for _ in range(len(s))]

if s[0] == t[0]:
    dp[0][0] = s[0]
for i in range(1, len(s)):
    dp[i][0] = dp[i-1][0]
for i in range(1, len(t)):
    dp[0][i] = dp[0][i]

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main():
    s = SI()
    t = SI()

    # そこまでの最大の長さ
    dp_table_2 = [[0 for _ in range(len(s))] for _ in range(len(t))]
    # init:
    ume = 0
    for i in range(len(s)):
        if t[0] == s[i]:
            ume = 1
        dp_table_2[0][i] = ume
    ume = 0
    for i in range(len(t)):
        if t[i] == s[0]:
            ume = 1
        dp_table_2[i][0] = ume

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

    # print(dp_table_2)

    # print(dp_table_2[len(t)-1][len(s)-1])

    # 復元
    i = len(t) - 1
    j = len(s) - 1
    ans = ''
    while i >= 0 and j >= 0:
        if j == 0:
            if dp_table_2[i][j] >= 1:
                ans += s[0]
                break
        if i == 0:
            if dp_table_2[i][j] >= 1:
                ans += t[0]
                break
        if dp_table_2[i][j] != dp_table_2[i][j-1] and dp_table_2[i][j] != dp_table_2[i-1][j]:
            ans += t[i]
            i -= 1
            j -= 1
        elif dp_table_2[i][j] != dp_table_2[i][j-1]: 
            i -= 1
        elif dp_table_2[i][j] != dp_table_2[i-1][j]: 
            j -= 1
        else:
            j -= 1

    print(ans[::-1])

main()

Submission status: Wrong Answer

Solution code:
S = list(input())
T = list(input())
dp = [[0] * (len(T)) for _ in range(len(S))]
for i in range(0, len(T)-1):
  if T[i] == S[0]:
    dp[0][i] = 1
  dp[0][i+1] = dp[0][i]
for i in range(0, len(S)-1):
  if S[i] == T[0]:
    dp[i][0] = 1
  dp[i+1][0] = dp[i][0]
for i in range(1, len(S)):
  for j in range(1, len(T)):
    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])
i, j = len(S)-1, len(T)-1
max_len = dp[i][j]
# ans = [''] * (max_len)
idx = 0
# while idx < max_len:
#  while i > 0 and dp[i][j] == dp[i-1][j]:
#    i -= 1
#  while j > 0 and dp[i][j] == dp[i][j-1]:
#    j -= 1
#  ans[idx] = S[i]
#  idx += 1
#  i -= 1
#  j -= 1
# print(''.join(ans[::-1]))
print('hoge')

Submission status: Wrong Answer

Solution code:
S = list(input())
T = list(input())
dp = [[0] * (len(T)) for _ in range(len(S))]
for i in range(0, len(T)-1):
  if T[i] == S[0]:
    dp[0][i] = 1
  dp[0][i+1] = dp[0][i]
for i in range(0, len(S)-1):
  if S[i] == T[0]:
    dp[i][0] = 1
  dp[i+1][0] = dp[i][0]
for i in range(1, len(S)):
  for j in range(1, len(T)):
    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])
i, j = len(S)-1, len(T)-1
max_len = dp[i][j]
# ans = [''] * (max_len)
idx = 0
while idx < max_len:
  while i > 0 and dp[i][j] == dp[i-1][j]:
    i -= 1
  while j > 0 and dp[i][j] == dp[i][j-1]:
    j -= 1
  # ans[idx] = S[i]
  idx += 1
  i -= 1
  j -= 1
print('a')  
# print(''.join(ans[::-1]))

Submission status: Wrong Answer

Solution code:
from collections import deque 

S = list(input())
T = list(input())
ans = []
dp = [[0] * (len(T)) for _ in range(len(S))]
for i in range(0, len(T)-1):
  if T[i] == S[0]:
    dp[0][i] = 1
  dp[0][i+1] = dp[0][i]
for i in range(0, len(S)-1):
  if S[i] == T[0]:
    dp[i][0] = 1
  dp[i+1][0] = dp[i][0]
for i in range(1, len(S)):
  for j in range(1, len(T)):
    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])
i, j = len(S)-1, len(T)-1
max_len = dp[i][j]
ans = [''] * (max_len)
idx = 0
dp[i][j] = -1
while idx < max_len:
  while i > 0 and dp[i][j] == dp[i-1][j]:
    i -= 1
  while j > 0 and dp[i][j] == dp[i][j-1]:
    j -= 1
  ans[idx] = S[i]
  idx += 1
  i -= 1
  j -= 1
print(''.join(ans[::-1]))

Submission status: Wrong Answer

Solution code:
from collections import deque 

S = list(input())
T = list(input())
ans = []
dp = [[0] * (len(T)) for _ in range(len(S))]
for i in range(0, len(T)-1):
  if T[i] == S[0]:
    dp[0][i] = 1
  dp[0][i+1] = dp[0][i]
for i in range(0, len(S)-1):
  if S[i] == T[0]:
    dp[i][0] = 1
  dp[i+1][0] = dp[i][0]
for i in range(1, len(S)):
  for j in range(1, len(T)):
    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])
i, j = len(S)-1, len(T)-1
max_len = dp[i][j]
ans = []
dp[i][j] = -1
while len(ans) < max_len:
  while i > 0 and dp[i][j] == dp[i-1][j]:
    i -= 1
  while j > 0 and dp[i][j] == dp[i][j-1]:
    j -= 1
  ans.append(S[i])
  i -= 1
  j -= 1
print(''.join(ans[::-1]))

Submission status: Wrong Answer

Solution code:
from collections import deque 

S = input()
T = input()
ans = []
dp = [[0] * (len(T)) for _ in range(len(S))]
for i in range(0, len(T)-1):
  if T[i] == S[0]:
    dp[0][i] = 1
  dp[0][i+1] = dp[0][i]
for i in range(0, len(S)-1):
  if S[i] == T[0]:
    dp[i][0] = 1
  dp[i+1][0] = dp[i][0]
for i in range(1, len(S)):
  for j in range(1, len(T)):
    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])
i, j = len(S)-1, len(T)-1
max_len = dp[i][j]
ans = []
dp[i][j] = -1
while len(ans) < max_len:
  while dp[i][j] == dp[i-1][j] and i > 0:
    i -= 1
  while dp[i][j] == dp[i][j-1] and j > 0:
    j -= 1
  ans.append(S[i])
  i -= 1
  j -= 1
print(''.join(ans[::-1]))

Submission status: Wrong Answer

Solution code:
from collections import deque 

S = input()
T = input()
ans = []
dp = [[0] * (len(T)) for _ in range(len(S))]
for i in range(0, len(T)-1):
  if T[i] == S[0]:
    dp[0][i] = 1
  dp[0][i+1] = dp[0][i]
for i in range(0, len(S)-1):
  if S[i] == T[0]:
    dp[i][0] = 1
  dp[i+1][0] = dp[i][0]
for i in range(1, len(S)):
  for j in range(1, len(T)):
    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])
i, j = len(S)-1, len(T)-1
max_len = dp[i][j]
ans = []
dp[i][j] = -1
while len(ans) < max_len:
  while dp[i][j] == dp[i-1][j] and i > 0:
    i -= 1
  while dp[i][j] == dp[i][j-1] and j > 0:
    j -= 1
  ans.append(S[i])
  i -= 1
  j -= 1
print(''.join(ans[::-1]))

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
ans = []
dp = [[0] * (len(T)) for _ in range(len(S))]
for i in range(0, len(T)-1):
  if T[i] == S[0]:
    dp[0][i] = 1
  dp[0][i+1] = dp[0][i]
for i in range(0, len(S)-1):
  if S[i] == T[0]:
    dp[i][0] = 1
  dp[i+1][0] = dp[i][0]
for i in range(1, len(S)):
  for j in range(1, len(T)):
    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])
i, j = len(S)-1, len(T)-1
ans = []
len_a = dp[i][j]
while i >= 0 and j >= 0:
  cnt = dp[i][j]
  while i >= 0 and dp[i][j] == cnt:
    i -= 1
  while j >= 0 and dp[i+1][j] == cnt:
    j -= 1
  if len(ans) < len_a:
  	ans.append(S[i+1])
print(''.join(ans[::-1]))

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
ans = []
dp = [[0] * (len(T)) for _ in range(len(S))]
for i in range(0, len(T)-1):
  if T[i] == S[0]:
    dp[0][i] = 1
  dp[0][i+1] = dp[0][i]
for i in range(0, len(S)-1):
  if S[i] == T[0]:
    dp[i][0] = 1
  dp[i+1][0] = dp[i][0]
for i in range(1, len(S)):
  for j in range(1, len(T)):
    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])
i, j = len(S)-1, len(T)-1
ans = []
len_a = dp[len(S)-1][len(T)-1]
while i >= 0 and j >= 0:
  cnt = dp[i][j]
  while j >= 0 and dp[i][j] == cnt:
    j -= 1
  while i >= 0 and dp[i][j+1] == cnt:
    i -= 1
  if len(ans) < len_a:
  	ans.append(S[i+1])
print(''.join(ans[::-1]))

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
ans = []
dp = [[0] * (len(T)) for _ in range(len(S))]
for i in range(0, len(T)-1):
  if T[i] == S[0]:
    dp[0][i] = 1
  dp[0][i+1] = dp[0][i]
for i in range(0, len(S)-1):
  if S[i] == T[0]:
    dp[i][0] = 1
  dp[i+1][0] = dp[i][0]
for i in range(1, len(S)):
  for j in range(1, len(T)):
    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])
i, j = len(S)-1, len(T)-1
ans = []
len_a = dp[len(S)-1][len(T)-1]
while i >= 0 and j >= 0:
  cnt = dp[i][j]
  while j >= 0 and dp[i][j] == cnt:
    j -= 1
  while i >= 0 and dp[i][j+1] == cnt:
    i -= 1
  if len(ans) < len_a:
  	ans.append(S[i+1])
print(''.join(ans[::-1]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
dp = [[0 for _ in range(len(s)+1)] for i in range(len(t)+1)]
for i in range(len(t)+1):
    dp[i][0] = 0
for j in range(len(s)+1):
    dp[0][j] = 0
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] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
print(dp[len(t)][len(s)])