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=list(input())
t=list(input())
dp=[[0]*(3030) for j in range(3030)]
ans=[]
memo=-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
             if memo < i:
                 ans.append(t[j])
                 memo = i

        else:
            dp[i+1][j+1] =max(dp[i][j+1],dp[i+1][j])

#print(dp[len(s)][len(t)])
answer=[]
i,j=len(s),len(t)
d=dp[i-1][j-1]
while i>0 and j>0:
    if dp[i-1][j-1]!=dp[i][j]:
        answer.append(s[i-1])
        i-=1
        j-=1
    elif dp[i-1][j]==dp[i][j]:
        i-=1
    elif dp[i][j-1]==dp[i][j]:
        j-=1
print("".join(reversed(answer)))

Submission status: Wrong Answer

Solution code:
s=list(input())
t=list(input())
dp=[[0]*(3030) for j in range(3030)]
ans=[]
memo=-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
             if memo < i:
                 ans.append(t[j])
                 memo = i

        else:
            dp[i+1][j+1] =max(dp[i][j+1],dp[i+1][j])

#print(dp[len(s)][len(t)])
answer=[]
i,j=len(s),len(t)
d=dp[i-1][j-1]
while i>0 :
    if dp[i-1][j-1]!=dp[i][j]:
        answer.append(s[i-1])
        i-=1
        j-=1
    elif dp[i-1][j]==dp[i][j]:
        i-=1
    elif dp[i][j-1]==dp[i][j]:
        j-=1
print("".join(reversed(answer)))

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
len_s = len(s)
len_t = len(t)
dp = [[0]*(len_t+1) for _ in range(len_s+1)]
# dp[i][j]はi、j文字目までのs[i],t[j]で、最長の部分列の長さ
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])

        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])
print(dp)
ans = ""
while len_t > 0 and len_s > 0:
    if dp[len_s][len_t] == dp[len_s-1][len_t]:
        len_s -= 1
    elif dp[len_s][len_t] == dp[len_s][len_t-1]:
        len_t -= 1
    else:
        ans += s[len_s-1]
        len_s -= 1
        len_t -= 1
print(ans[::-1])

Submission status: Wrong Answer

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

maxLength = [[0 for i in range(len(s)+2)] for j in range(len(t)+2)] # index_s, index_t

for i_t in range(1,len(t)+1) :
	for i_s in range(1,len(s)+1) :
		if s[i_s-1] == t[i_t-1] :
			maxLength[i_t][i_s] = max(maxLength[i_t-1][i_s-1] + 1, maxLength[i_t][i_s])
		maxLength[i_t+1][i_s] = max(maxLength[i_t+1][i_s], maxLength[i_t][i_s])
		maxLength[i_t][i_s+1] = max(maxLength[i_t][i_s+1],maxLength[i_t][i_s])

str = ''
next_s = len(s)
max = maxLength[len(t)][len(s)]
for i in range(len(t), -1, -1) :
	for j in range(next_s, -1, -1) :
		if max - 1 == maxLength[i][j] :
			str = s[j] + str # (j + 1)文字目
			max -= 1
			next_s = j
			break
	if max == 0 :
		break

print(str)

Submission status: Wrong Answer

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

maxLength = [[0 for i in range(len(s)+2)] for j in range(len(t)+2)] # index_s, index_t

for i_t in range(1,len(t)+1) :
	for i_s in range(1,len(s)+1) :
		if s[i_s-1] == t[i_t-1] :
			maxLength[i_t][i_s] = max(maxLength[i_t-1][i_s-1] + 1, maxLength[i_t][i_s])
		maxLength[i_t+1][i_s] = max(maxLength[i_t+1][i_s], maxLength[i_t][i_s])
		maxLength[i_t][i_s+1] = max(maxLength[i_t][i_s+1],maxLength[i_t][i_s])

str = ''
next_s = len(s)
max = maxLength[len(t)][len(s)]
for i in range(len(t), -1, -1) :
	for j in range(next_s, -1, -1) :
		if max - 1 == maxLength[i][j] :
			str = s[j] + str # (j + 1)文字目
			max -= 1
			next_s = j
			break
	if max == 0 :
		break

if len(str) == 0 :
	print('\'\'')
else :
	print(str)

Submission status: Wrong Answer

Solution code:
s=list(input())
t=list(input())
dp=[[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]:
            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])

path=[]
i=len(s)
j=len(t)
while dp[i][j]!=0:
    if dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        path.append(j-1)
        i-=1
        j-=1
path.sort()
if path==[]:
    print("")
else:
    for i in path:
        print(t[i],end="")

Submission status: Wrong Answer

Solution code:

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

ans=""
for i in range(len(s)):
    if dp[i][len(t)]!=dp[i+1][len(t)]:
        ans+=s[i]
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


s=data()
t=data()
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]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
m=max(max(dp))
ans=''
for i in range(len(t)-1,-1,-1):
    for j in range(len(s)-1,-1,-1):
        if dp[i+1][j+1]==m and s[j]==t[i]:
            ans=s[j]+ans
            m-=1
            break
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


s=data()
t=data()
dp1=[0]*len(s)
for i in range(len(t)):
    m=0
    for j in range(len(s)):
        if s[j]==t[i]:
            k=dp1[j]
            dp1[j]=m+1
            m=max(k,m)
        else:
            m=max(m,dp1[j])

m=max(dp1)
cnt=m
ans=''
ind=len(s)-1
for i in range(len(t)-1,-1,-1):
    for j in range(ind,-1,-1):
        if dp1[j]>=cnt and s[j]==t[i]:
            ans+=s[j]
            cnt-=1
            ind-=1
            break
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


s=data()
t=data()
dp1=[0]*len(s)
for i in range(len(t)):
    m=0
    for j in range(len(s)):
        if s[j]==t[i]:
            k=dp1[j]
            dp1[j]=m+1
            m=max(k,m)
        else:
            m=max(m,dp1[j])

dp2=[0]*len(s)
for i in range(len(t)-1,-1,-1):
    m=0
    for j in range(len(s)-1,-1,-1):
        if s[j]==t[i]:
            k=dp2[j]
            dp2[j]=m+1
            m=max(k,m)
        else:
            m=max(m,dp2[j])

m=max(dp1)
cnt=m
ans=''
for j in range(len(s)-1,-1,-1):
    if dp1[j]>=cnt and dp2[j]>=m-cnt+1:
        ans+=s[j]
        cnt-=1
print(ans[::-1])

Submission status: Wrong Answer

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

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

            
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

from pprint import pprint
from collections import deque, defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
inf = float("inf")

s = input()
t = input()
# print(s, t)

len_s, len_t = len(s), len(t)
max_len = max(len_s, len_t)
dp = [[0 for j in range(max_len + 1)] for i in range(max_len + 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])

# pprint(dp)
# print(dp[len(s)][len(t)])

res = ''
i, j = len_s, len_t
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        # (i - 1, j) -> (i, j)
        i -= 1
    elif dp[i][j] == dp[i - 1][j]:
        # (i, j - 1) -> (i, j)
        j -= 1
    else:
        # (i - 1, j - 1) -> (i, j)
        res = s[i - 1] + res
        i -= 1
        j -= 1

print(res)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
sl = len(s)
tl = len(t)
dp = [[""]*(tl) for _ in range(sl)]
#sのi番目までの文字とtのj番目までの文字の最長共通

for i in range(sl):
  for j in range(tl):
    a = len(dp[i-1][j-1])
    b = len(dp[i][j-1])
    c = len(dp[i-1][j])
    if s[i] == t[j]:
      if i>1 and j>1:
        dp[i][j] = dp[i-1][j-1] + s[i]
      else:
        dp[i][j] = s[i]
    else:
      if b > c:
        dp[i][j] = dp[i][j-1]
      else:
        dp[i][j] = dp[i-1][j]
      
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
sl = len(s)
tl = len(t)
dp = [[""]*(tl) for _ in range(sl)]
#sのi番目までの文字とtのj番目までの文字の最長共通

for i in range(sl):
  for j in range(tl):
    a = len(dp[i-1][j-1])
    b = len(dp[i][j-1])
    c = len(dp[i-1][j])
    if s[i] == t[j]:
      dp[i][j] = dp[i-1][j-1] + s[i]
    else:
      if b > c:
        dp[i][j] = dp[i][j-1]
      else:
        dp[i][j] = dp[i-1][j]
      
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
X = input()
Y = input()
x = len(X)
y = len(Y)

dp = [[0 for _ in range(y + 1)] for _ in range(x + 1)]
for i in range(x):
    for j in range(y):
        if X[i] == Y[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[x][y])
# print(dp)

Submission status: Wrong Answer

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

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
def al(str):
    return alphabetlist.index(str)+1

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

firsts=N
for i in range(0,N):
    if s[i]==t[0]:
        firsts=i
        break

firstt=M
for i in range(0,M):
    if t[i]==s[0]:
        firstt=i
        break

for i in range(0,N):
    if i>=firsts:
        dp[i+1][0]=1

for i in range(0,M):
    if i>=firstt:
        dp[0][i+1]=1

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

ans=[]
i=N
j=M
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.append(s[i-1])
        i-=1
        j-=1

ans=ans[::-1]
print(''.join(ans))

Submission status: Wrong Answer

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

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
def al(str):
    return alphabetlist.index(str)+1

dp=[[0 for i in range(0,M)] for i in range(0,N)]

firsts=N
for i in range(0,N):
    if s[i]==t[0]:
        firsts=i
        break

firstt=M
for i in range(0,M):
    if t[i]==s[0]:
        firstt=i
        break

for i in range(0,N):
    if i>=firsts:
        dp[i][0]=1

for i in range(0,M):
    if i>=firstt:
        dp[0][i]=1

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

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

if dp[0][j]==1:
    ans.append(s[0])

ans=ans[::-1]
print(''.join(ans))

Submission status: Wrong Answer

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

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
def al(str):
    return alphabetlist.index(str)+1

dp=[[0 for i in range(0,M)] for i in range(0,N)]

firsts=N
for i in range(0,N):
    if s[i]==t[0]:
        firsts=i
        break

firstt=M
for i in range(0,M):
    if t[i]==s[0]:
        firstt=i
        break

for i in range(0,N):
    if i>=firsts:
        dp[i][0]=1

for i in range(0,M):
    if i>=firstt:
        dp[0][i]=1

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

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

if dp[0][j]==1:
    ans.append(s[0])

ans=ans[::-1]
print(''.join(ans))

Submission status: Wrong Answer

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

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
def al(str):
    return alphabetlist.index(str)+1

dp=[[0 for i in range(0,M)] for i in range(0,N)]

firsts=N
for i in range(0,N):
    if s[i]==t[0]:
        firsts=i
        break

firstt=M
for i in range(0,M):
    if t[i]==s[0]:
        firstt=i
        break

for i in range(0,N):
    if i>=firsts:
        dp[i][0]=1

for i in range(0,M):
    if i>=firstt:
        dp[0][i]=1

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

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

if dp[0][j]==1:
    ans.append(s[0])

ans=ans[::-1]
print(''.join(ans))

Submission status: Wrong Answer

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

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
def al(str):
    return alphabetlist.index(str)+1

dp=[[0 for i in range(0,M)] for i in range(0,N)]

firsts=N
for i in range(0,N):
    if s[i]==t[0]:
        firsts=i
        break

firstt=M
for i in range(0,M):
    if t[i]==s[0]:
        firstt=i
        break

for i in range(0,N):
    if i>=firsts:
        dp[i][0]=1

for i in range(0,M):
    if i>=firstt:
        dp[0][i]=1

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

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

ans=ans[::-1]
print(''.join(ans))

Submission status: Wrong Answer

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

dp=[['' for i in range(0,M)] for i in range(0,N)]

firsts=N
for i in range(0,N):
    if s[i]==t[0]:
        firsts=i
        break

firstt=M
for i in range(0,M):
    if t[i]==s[0]:
        firstt=i
        break

for i in range(0,N):
    if i>=firsts:
        dp[i][0]=s[0]

for i in range(0,M):
    if i>=firstt:
        dp[0][i]=t[0]

for i in range(1,N):
    for j in range(1,M):
        if s[i]==t[j]:
            x=[dp[i-1][j-1],s[i]]
            dp[i][j]=''.join(x)
        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]

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

Submission status: Wrong Answer

Solution code:
import copy,bisect

s=input()
N=len(s)
t=input()
M=len(t)

dp=[[0 for i in range(0,M)] for i in range(0,N)]

for i in range(0,N):
    if s[0:i+1].count(t[0])>0:
        dp[i][0]=1

for i in range(0,M):
    if t[0:i+1].count(s[0])>0:
        dp[0][i]=1

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

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

Submission status: Wrong Answer

Solution code:
import copy,bisect

s=input()
N=len(s)
t=input()
M=len(t)

dp=[['' for i in range(0,M)] for i in range(0,N)]

for i in range(0,N):
    if s[0:i+1].count(t[0])>0:
        dp[i][0]=s[0]

for i in range(0,M):
    if t[0:i+1].count(s[0])>0:
        dp[0][i]=s[0]

for i in range(1,N):
    for j in range(1,M):
        if s[i]==t[j]:
            x=[dp[i-1][j-1],s[i]]
            dp[i][j]=''.join(x)
        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]

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

Submission status: Wrong Answer

Solution code:
import copy,bisect

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

Index={moji:[] for moji in alphabetlist}
for i in range(N):
    Index[s[i]].append(i)

dp=[0 for i in range(0,N)]

for i in range(0,N):
    if Index[t[0]]:
        if i>=Index[t[0]][0]:
            dp[i]=1

for i in range(1,M):
    x=t[i]
    if Index[x]:
        for j in range(N-1,Index[x][0]-1,-1):
            next=Index[x][bisect.bisect_right(Index[x],j)-1]-1
            if next>=0:
                if dp[j]<1+dp[next]:
                    dp[j]=dp[next]+1
            else:
                if dp[j]==0:
                    dp[j]=1


print(dp[-1])

Submission status: Wrong Answer

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

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

index={moji:[] for moji in alphabetlist}
for i in range(N):
    index[s[i]].append(i)

dp=[[[] for i in range(0,N)] for j in range(0,M)]

for i in range(0,N):
    if index[t[0]]:
        if i>=index[t[0]][0]:
            dp[0][i]=[t[0]]

for i in range(0,M):
    for j in range(0,N):
        x=t[i]
        if index[x] and j>=index[x][0]:
            start=0
            end=len(index[x])-1
            while end-start>1:
                test=(end+start)//2
                if j>=index[x][test]:
                    start=test
                else:
                    end=test
            if j>=index[x][end]:
                next=index[x][end]-1
            else:
                next=index[x][start]-1
            if next>=0:
                if len(dp[i-1][j])>1+len(dp[i-1][next]):
                    dp[i][j]=dp[i-1][j]
                else:
                    dp[i][j]=dp[i-1][next]+[t[i]]
            else:
                if dp[i-1][j]=="":
                    dp[i][j]=[t[i]]
                else:
                    dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=dp[i-1][j]

print(''.join(dp[M-1][N-1]))

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)+1):
  for j in range(len(t)+1):
    if i == 0 and j == 0:
      continue
    if i == 0:
      dp[i][j] = dp[i][j-1]
      continue
    if j == 0:
      dp[i][j] = dp[i-1][j]
      continue
    if s[i-1] == t[j-1]:
      dp[i][j] = dp[i-1][j-1] + 1
    else:
      if dp[i-1][j] > dp[i][j-1]:
        dp[i][j] = dp[i-1][j]
      else:
        dp[i][j] = dp[i][j-1]
print(dp[len(s)][len(t)])

Submission status: Wrong Answer

Solution code:
import copy

s = input()
t = input()

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
key = [[[0, 0] for _ in range(len(t)+1)] for _ in range(len(s)+1)]
for i in range(len(s)+1):
  for j in range(len(t)+1):
    if i == 0 and j == 0:
      continue
    if i == 0:
      dp[i][j] = dp[i][j-1]
      continue
    if j == 0:
      dp[i][j] = dp[i-1][j]
      continue
    if s[i-1] == t[j-1]:
      dp[i][j] = dp[i-1][j-1] + 1
      key[i][j] = [i-1, j-1]
    else:
      if dp[i-1][j] > dp[i][j-1]:
        dp[i][j] = dp[i-1][j]
        key[i][j] = copy.deepcopy(key[i-1][j])
      else:
        dp[i][j] = dp[i][j-1]
        key[i][j] = copy.deepcopy(key[i][j-1])

ans = []
i, j = map(int, key[len(s)][len(t)])
while True:
  ans.append(t[j])
  if i == 0 or j == 0:
    break
  i, j = map(int, key[i][j])
ans.reverse()
print("".join(ans))

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0for i in range(n+1)]for j in range(m+1)]
letter = [[""for i in range(n+1)]for j in range(m+1)]

for i,a in enumerate(t):
    for j,b in enumerate(s):
        if dp[i+1][j]<dp[i][j]:
            letter[i + 1][j] = letter[i][j]
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if dp[i][j+1]<dp[i][j]:
            letter[i][j+1] = letter[i][j]
        dp[i][j+1] = max(dp[i][j+1],dp[i][j])
        if a == b:
            if dp[i+1][j+1]<dp[i][j]+1:
                letter[i+1][j+1] = letter[i][j]+a
            else:
                letter[i+1][j+1] = letter[i][j]
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1)

ansindex = dp[m].index(max(dp[m]))
print(letter[m][ansindex])

Submission status: Wrong Answer

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

dp = [[""]*(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] + s[i-1]
        else:
            if dp[i-1][j] < dp[i][j-1]:
                dp[i][j] = dp[i][j-1]
            else:
                dp[i][j] = dp[i-1][j]

print(dp[len(s)][len(t)])

Submission status: Wrong Answer

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

#N = ii()
#ss = [sys.stdin.readline().rstrip() for i in range(2*N)]
#for i in range(N):
S = input()
T = input()
#S = ss[2*i]
#T = ss[2*i+1]

ls, lt = len(S), len(T)
dp = dp2(0, ls+1, lt+1)
#if S[0] == T[0]:
    #dp[1][1] = 1

for i in range(1, lt+1):
    for j in range(1, ls+1):
        #if (i < lt and j < ls) and S[j] == T[i]:
            #dp[i+1][j+1] = dp[i][j] + 1
        #if j < ls:
            #dp[i][j+1] = max(dp[i][j], dp[i][j+1])
        #if i < lt:
            #dp[i+1][j] = max(dp[i][j], dp[i+1][j])
        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])

        
        
#if not dp[lt][ls]:
    #dp[lt][ls] = max(dp[lt-1][ls], dp[lt][ls-1])

print(dp[lt][ls])


i, j = lt, ls
ans = ''

while dp[i][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[j-1]
        i -= 1
        j -= 1

print(ans[::-1])

Submission status: Wrong Answer

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

#N = ii()
#ss = [sys.stdin.readline().rstrip() for i in range(2*N)]
#for i in range(N):
S = input()
T = input()
#S = ss[2*i]
#T = ss[2*i+1]

ls, lt = len(S), len(T)
dp = dp2(0, ls+1, lt+1)
#if S[0] == T[0]:
    #dp[1][1] = 1

for i in range(lt):
    for j in range(ls):
        if S[j] == T[i]:
            dp[i+1][j+1] = dp[i][j] + 1
        dp[i][j+1] = max(dp[i][j], dp[i][j+1])
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])
if not dp[lt][ls]:
    dp[lt][ls] = max(dp[lt-1][ls], dp[lt][ls-1])

    #print(dp[lt][ls])


i, j = lt, ls
ans = ''

while dp[i][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[j-1]
        i -= 1
        j -= 1

print(ans[::-1])

Submission status: Wrong Answer

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

S = input()
T = input()

ls, lt = len(S), len(T)
dp = dp2(0, ls+1, lt+1)

for i in range(1, lt+1):
    flag = 0
    for j in range(ls):
        if T[i-1] == S[j]:
            if flag:
                dp[i][j+1] = max(dp[i-1][j+1]+1, dp[i][j])
            else:
                dp[i][j+1] = max(dp[i-1][j+1], dp[i][j]+1)
                flag = 1
        else:
            dp[i][j+1] = max(dp[i][j], dp[i-1][j+1])

#print(dp[lt][ls])
i, j = lt, ls
ans = ''

while dp[i][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[j-1]
        i -= 1
        j -= 1

print(ans[::-1])

Submission status: Wrong Answer

Solution code:
a=str(input())
b=str(input())
dp=[[0 for i in range(len(a)+1)] for j in range(len(b)+1)]
for i in range(1,len(b)+1):
    for j in range(1,len(a)+1):
        if b[i-1]==a[j-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[-1][-1])

Submission status: Wrong Answer

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

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

for t in range(1, t_len + 1):
    for s in range(1, s_len + 1):
        ans_array[t][s] = max(ans_array[t - 1][s], ans_array[t][s - 1])
        if T[t - 1] == S[s - 1]:
            ans_array[t][s] = ans_array[t - 1][s - 1] + 1


ans_len = ans_array[-1][-1]
ans = [""] * ans_len
s_last = s_len
t_last = t_len
for i in range(ans_len - 1, -1, -1):
    s_next = 0
    t_next = 0
    for s in range(s_last, 0, -1):
        if ans_array[t_last][s] != ans_array[t_last][s - 1]:
            s_next = s
            break
    for t in range(t_last, 0, -1):
        if ans_array[t][s_last] != ans_array[t - 1][s_last]:
            t_next = t
            break
    ans[i] = S[s_next - 1]
    s_last = s_next - 1
    t_last = t_next - 1

print("".join(ans))

Submission status: Wrong Answer

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

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

for t in range(1, t_len + 1):
    for s in range(1, s_len + 1):
        ans_array[t][s] = max(ans_array[t - 1][s], ans_array[t][s - 1])
        if T[t - 1] == S[s - 1]:
            ans_array[t][s] = ans_array[t - 1][s - 1] + 1


ans = ""
for i in range(s_len):
    if ans_array[-1][i] != ans_array[-1][i+1]:
        ans += S[i]

print(ans)

Submission status: Wrong Answer

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

s=len(S)
t=len(T)
#DPテーブル作成
dp=[]
for i in range(s+1):
    dp.append(['']*(t+1))

for i in range(s):
    for j in range(t):
        if S[i] ==T[j]:
            dp[i+1][j+1] =dp[i][j] + S[i]
        else:
            dp[i+1][j+1] =  max([dp[i+1][j],dp[i][+1]],key=len)
#print(*dp,sep="\n")

print(dp[s][t])

Submission status: Wrong Answer

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

s=len(S)
t=len(T)
#DPテーブル作成
dp=[]
for i in range(s+1):
    dp.append(['']*(t+1))

for i in range(s):
    for j in range(t):
        if S[i] ==T[j]:
            dp[i+1][j+1] =dp[i][j] + S[i]
        else:
            dp[i+1][j+1] =  max([dp[i+1][j],dp[i][+1]],key=len)
print(*dp,sep="\n")

print(dp[s][t])

Submission status: Wrong Answer

Solution code:
def main():
    s = input()
    t = input()
    dp = [[0] * len(t) for _ in range(len(s))]
    for i,x in enumerate(s):
        for j,y in enumerate(t):
            if i == 0:
                dp[i][j] = 1 if x in t[:j+1] else 0
            elif j == 0:
                dp[i][j] = 1 if y in s[:i+1] else 0
            elif x == y:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

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

    print(ans[::-1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


def solve(s: str, t: str):
    if not s or not t:
        print("")
    dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]

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

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

    ans = []
    while m > 0 and n > 0:
        if s[m-1] == t[n-1]:
            ans.append(s[m-1])
            m -= 1
            n -= 1
        elif dp[m][n] == dp[m][n-1]:
            n -= 1
        else:
            m -= 1
    print("".join(reversed(ans)))


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)


if __name__ == '__main__':
    main()