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
sys.setrecursionlimit(10**7)
class Solution:
	def solve(self,s1,s2,x,y):
		if x==0 or y==0:
			return self.dp[x][y]
		elif self.dp[x][y]!=-1:
			return self.dp[x][y]
		else:
			if s1[x-1]==s2[y-1]:
				self.dp[x][y]=1+self.solve(s1,s2,x-1,y-1)
				return self.dp[x][y]
			else:
				self.dp[x][y]=max(self.solve(s1,s2,x,y-1),self.solve(s1,s2,x-1,y))
				return self.dp[x][y] 
	def longestCommonSubsequence(self, text1: str, text2: str) -> int:
		m=len(text1)
		n=len(text2)
		self.dp=[[-1 for i in range(n+1)] for j in range(m+1)]
		for i in range(n+1):
			self.dp[0][i]=0
		for i in range(m+1):
			self.dp[i][0]=0
		self.solve(text1,text2,m,n)
		common=""
		target=1
		for i in range(1,m+1):
			for j in range(1,n+1):
				if self.dp[i][j]==target:
					common+=text1[i-1]
					target+=1
		return common
if __name__ == "__main__":
	s=input()
	t=input()
	obj=Solution()
	ans1=obj.longestCommonSubsequence(s,t)
	print(ans1)

Submission status: Wrong Answer

Solution code:
# ライブラリのインポート
import numpy as np


# メイン関数
def main():
    # 入力データ
    s = input()
    t = input()
    
    len_s = len(s)
    len_t = len(t)

    # dpテーブルの作成
    dp = np.zeros((len_s + 1, len_t + 1), dtype='int')
    for i in range(1, len_s + 1):
        for j in range(1, len_t + 1):
            print(i, j)
            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])

    # 部分列の復元
    length = dp[len_s][len_t]
    ans = ''
    i = len_s
    j = len_t
    while length > 0:
        if s[i - 1] == t[j - 1]:
            ans = s[i - 1] + ans
            i -= 1
            j -= 1
            length -= 1
        elif dp[i][j] == dp[i - 1][j]:
            i -= 1
        else:
            j -= 1

    # 解答の出力
    print(ans)
    return


# 実行
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# ライブラリのインポート
import numpy as np


# メイン関数
def main():
    # 入力データ
    s = input()
    t = input()

    # dpテーブルの作成
    dp = np.zeros((len(s) + 1, len(t) + 1), dtype='int')
    for i in range(1, len(s) + 1):
        for j in range(1, len(t) + 1):
            print(i, j)
            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])

    # 部分列の復元
    length = dp[len(s)][len(t)]
    ans = ''
    i = len(s)
    j = len(t)
    while length > 0:
        if s[i - 1] == t[j - 1]:
            ans = s[i - 1] + ans
            i -= 1
            j -= 1
            length -= 1
        elif dp[i][j] == dp[i - 1][j]:
            i -= 1
        else:
            j -= 1

    # 解答の出力
    print(ans)
    return


# 実行
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
S,T=len(s),len(t)
dp=[[0]*(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][j+1],dp[i+1][j])

len=dp[S][T]
x,y=S-1,T-1
ans=[0]*len
while len>0:
    if s[x]==t[y]:
        ans[len-1]=s[x]
        x-=1
        y-=1
        len-=1
    else:
        if dp[x][y]==dp[x-1][y]: x-=1
        else: y-=1
print("".join(ans))

Submission status: Wrong Answer

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

#import
#import math
#import numpy as np
#= int(input())
S = input()
T = input()

ls = len(S)
lt = len(T)

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

for i in range(1, ls + 1):
    for j in range(1, lt + 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])
            
l = dp[-1][-1]
i = ls - 1
j = lt - 1
ans = ""

while l > 0:
    if S[i] == T[j]:
        ans = S[i] + ans
        i -= 1
        j -= 1
        l -= 1

    elif dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

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

    len_s = len(s)
    len_t = len(t)

    # dp[i][j] = the maximum length of common part of s[:i+1] and t[:j+1]
    dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
    for i in range(1, len_s + 1):
        for j in range(1, len_t + 1):
            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])

    i, j = len_s, len_t
    ans = ''
    while dp[i][j] > 0:
        if dp[i-1][j-1] < dp[i][j]:
            ans += s[i-1]
            i -= 1
            j -= 1
        elif dp[i-1][j] == dp[i][j]:
            i -= 1
        else:
            j -= 1

    print(ans[::-1])

main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

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

    len_s = len(s)
    len_t = len(t)

    # dp[i][j] = the maximum length of common part of s[:i+1] and t[:j+1]
    dp = [[0] * len_t for _ in range(len_s)]
    for j in range(len_t):
        if dp[0][j-1] == 1 or s[0] == t[j]:
            dp[0][j] = 1
    for i in range(len_s):
        if dp[i-1][0] == 1 or s[i] == t[0]:
            dp[i][0] = 1
    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])

    cnt = dp[-1][-1]
    i, j = len_s - 1, len_t - 1
    ans = ''
    while cnt > 0:
        if i > 0 and j > 0 and dp[i-1][j-1] < dp[i][j]:
            ans += s[i]
            cnt -= 1
            i -= 1
            j -= 1
        elif i > 0 and dp[i-1][j] == dp[i][j]:
            i -= 1
        elif j > 0 and dp[i][j-1] == dp[i][j]:
            j -= 1
        else:
            ans += s[0]
            cnt -= 1

    print(ans[::-1])

main()

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

ans = ''
for j in range(dp[len(t)][len(s)]):
    for i in range(len(s), -1, -1):
        if dp[len(t)-j][i] == dp[len(t)][len(s)]-1-j:
            ans += s[i]
            break
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
import numpy as np
s = np.array(list(input()))
t = np.array(list(input()))
dp = np.zeros((len(s)+1, len(t)+1), dtype=int)

equal = s[:, None] == t[None, :]

for i in range(len(s)):
    dp[i+1, 1:] = np.maximum(dp[i, :-1]+equal[i], dp[i, 1:])
    dp[i+1] = np.maximum.accumulate(dp[i+1])

l = int(dp[len(s)][len(t)])
i = len(s)-1
j = len(t)-1
ans = []

while l>0:
    if s[i] == t[j]:
        ans.append(s[i])
        i -= 1
        j -= 1
        l -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else :
        j -= 1
print(''.join(ans[::-1]))

Submission status: Wrong Answer

Solution code:
import numpy as np
s = input()
t = input()
dp = np.zeros((len(s)+1, len(t)+1))

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

l = int(dp[len(s)-1][len(t)-1])
i = len(s)-1
j = len(t)-1
ans = []

while i>0 and j>0:
    if s[i] == t[j]:
        ans.append(s[i])
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else :
        j -= 1
print(''.join(ans[::-1]))

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
slen = len(s)
tlen = len(t)

dp = [[0]*(tlen+1) for _ in range(slen+1)]

for i in range(slen):
    for j in range(tlen):
        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])

length = dp[slen][tlen]

ans = ''
i,j = slen-1,tlen-1
while length>0:
    if s[i] == t[j]:
        ans += s[i]
        i -= 1
        j -= 1
        length -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        i -= 1
print(ans[::-1])

Submission status: Wrong Answer

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

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

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

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

ans=""
l=dp[ls][lt]-1
i=ls-1
j=lt-1
while l>=0:
    if s[i]==t[j]:
        ans=s[i]+ans
        i-=1
        j-=1
        l-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        i-=1

print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_f?lang=ja


def lcs(s1,s2):
    n1,n2 = len(s1),len(s2)
    dp = [ [0]*(n2+1) for _ in range(n1+1) ]
    for i in range(1,n1+1):
        for j in range(1,n2+1):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 
            if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]+1
    return dp[-1][-1]



s1 = input()
s2 = input()
ans = lcs(s1,s2)
print(ans,flush=True)

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(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-1][j],dp[i][j-1])
    # print(dp[i])
ans=''
i,j=len(s),len(t)
while i > 0:
    while j > 0:
        if s[i-1]==t[j-1]:
            ans=s[i-1]+ans
            i=i-1
            j=j-1
        else:
            if dp[i-1][j]>dp[i][j-1]:
                i-=1
            else:
                j-=1
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

    l = dp[slen][tlen]
    i = slen-1
    j = tlen-1
    ans = ''
    while l > 0:
        if s[i] == t[j]:
            ans = s[i]+ans
            j -= 1
            i -= 1
            l -= 1
        elif dp[i][j] == dp[i-1][j]:
            i-=1
        else:
            j-=1
    print(ans)

edu_dp_f_lcs()

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(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)
      #print(max(dp[i+1][j+1],dp[i][j]+1))
    dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1],dp[i+1][j])
    #print(dp)
#print(dp)
len=dp[lens][lent]
#print(len)
i=lens-1
j=lent-1
ans=["" for _ in range(len)]
while len>0:
  #print(i,j,ans)
  if s[i]==t[j]:
    #print(i,j,ans)
    ans[len-1]=s[i]
    i-=1
    j-=1
    len-=1
    #print(ans)
  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()
lens=len(s)
lent=len(t)
dp=[[0 for _ in range(lent)] for _ in range(lens)] 
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]+1
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
print(dp)

Submission status: Wrong Answer

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

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

dp=[[0]*T for i in range(S)]

for i in range(1,S):
  for j in range(1,T):
    if s[i-1]==t[j-1]:
      dp[i][j] = max(dp[i][j],dp[i-1][j-1] + 1)
    dp[i][j] = max(dp[i][j],dp[i-1][j]) 
    dp[i][j] = max(dp[i][j],dp[i][j-1])
    
res=""
i=len(s)
j=len(t)
while i>0 and j>0:
  #s[i]=t[j]であり、(i-1,j-1)->(i,j)に更新した場合
  if dp[i][j] == dp[i-1][j-1] + 1:
    res = s[i-1] + res
    i -= 1
    j -= 1
  #(i-1,j)->(i,j)に更新した場合
  elif dp[i][j] == dp[i-1][j]:
    i -= 1
  #(i,j-1)->(i,j)に更新した場合
  elif dp[i][j] == dp[i][j-1]:
    j -= 1
print(res)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
def LCS(s,t,rec=False):
  S=np.array(list(s),'U1')[:-1]
  T=np.array(list(t),'U1')[:-1]
  LS,LT=len(S),len(T)
  dp=np.zeros((LS+1,LT+1),np.int32)
  for n in range(1,LS+1):
    dp[n,1:]=dp[n-1,:-1]+(S[n-1]==T)
    np.maximum(dp[n],dp[n-1],out=dp[n])
    np.maximum.accumulate(dp[n],out=dp[n])
  if rec:
    tmp=[]
    while LS>0 and LT>0:
      if S[LS-1]==T[LT-1]:
        LS,LT=LS-1,LT-1
        tmp.append(S[LS])
      elif dp[LS,LT]==dp[LS-1,LT]:
        LS-=1
      else:
        LT-=1
    return ''.join(reversed(tmp))
  else:
    return dp[LS][LT]
s=input()
t=input()
print(LCS(s,t,True))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import deque

def mymax(a:int, b:int, c:int):
    if a > b:
        if c > a:
            return c
        else:
            return a
    else:
        if c > b:
            return c
        else:
            return b


def main():
    s = input()
    t = input()
    lens = len(s)
    lent = len(t)
    dp = [[0] * (lent+1) for _ in range(lens+1)]


    for i in range(1, lens + 1):
        for j in range(1, lent + 1):
            dp[i][j] = mymax(
                dp[i-1][j-1] + (s[i-1] == t[j-1]),
                dp[i-1][j],
                dp[i][j-1]
            )
    
    string = deque([])
    for i in range(lens, 0, -1):
        if dp[i][lent] > dp[i-1][lent]:
            string.appendleft(s[i-1])
        if dp[i-1][lent] == 0:
            break
    print(''.join(string))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

    for i in range(1,m+1):
        for j in range(1,n+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = 1+ dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    
    
    substr = ""
    i,j = m,n
    while i!=0 or j!=0:
        if s[i-1] == t[j-1]:
            substr+=s[i-1]
            i-=1
            j-=1
        elif dp[i][j-1]>dp[i-1][j]:
            j-=1
        else:
            i-=1
    return substr[::-1]
    
    

s = "abracadabra"
t = "avadakedavra"
# s = "axyb"
# t = "abyxb"

print(lcs(s,t))

Submission status: Wrong Answer

Solution code:
a = input()
b = input()
dp = [[0 for j in range(len(b)+1)] for i in range(len(a)+1)]
for i in range(1, len(a)+1):
    for j in range(1, len(b)+1):
        if a[i-1] == b[j-1] :
            dp[i][j] = dp[i-1][j-1] + 1
            continue
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
m = dp[-1][-1]
ans = ''
i,j=-1,-1
while(len(ans)<m):
    print(i, j)
    if a[i] == b[j]:
        ans = a[i] + ans
        i-=1
        j-=1
    elif dp[i-1][j] > dp[i][j-1]:
        i-=1
    else:
        j-=1
print(ans)

Submission status: Wrong Answer

Solution code:
a = input()
b = input()
dp=[[0 for i in range(len(b)+1)] for j in range(len(a)+1)]
for p in range(2, len(a)+len(b)+1):
    for j in range(max(1, p-len(a)), min(p, len(b)+1)):
        i = p-j
        if a[i-1]==b[j-1]:
            x1 = 1 + dp[i-1][j-1]
        else:
            x1 = dp[i-1][j-1]
        x2 = dp[i][j-1]
        x3 = dp[i-1][j]
        dp[i][j] = max(x1, x2, x3)
mm = (dp[-1][-1])
ans = ''
i = len(a)
j = len(b)
while(len(ans)<mm):
    x1 = dp[i-1][j-1]
    x2 = dp[i-1][j]
    x3 = dp[i][j-1]
    x = dp[i][j]
    if x-x1==1:
        ans = a[i-1] + ans
        i-=1
        j-=1
    elif x-x2==1:
        ans = a[i-1] + ans
        i-=1
    elif x-x3==1:
        ans = b[j-1] + ans
    elif x==x2:
        i-=1
    else:
      	j-=1
print(ans)

Submission status: Wrong Answer

Solution code:
'''
from sys import stdin, setrecursionlimit as srl
from threading import stack_size, Thread
srl(int(1e9)+7)
stack_size(int(1e8))

def solve():
    t = int ( input () )
    for _ in range ( t ) :
        


Thread(target=solve).start()
solve()
'''

a = input()
b = input()
dp=[[0 for i in range(len(b)+1)] for j in range(len(a)+1)]
for p in range(2, len(a)+len(b)+1):
    for j in range(max(1, p-len(a)), min(p, len(b)+1)):
        i = p-j
        if a[i-1]==b[j-1]:
            x1 = 1 + dp[i-1][j-1]
            dp[i][j] = x1
            continue
        x2 = dp[i][j-1]
        x3 = dp[i-1][j]
        dp[i][j] = max(x2, x3)
mm = (dp[-1][-1])
ans = ''
i = len(a)
j = len(b)
while(len(ans)<mm):
    if a[i-1]==b[j-1]:
        ans = a[i-1] + ans
        i-=1
        j-=1
        continue
    x2 = dp[i-1][j]
    x3 = dp[i][j-1]
    x = dp[i][j]
    if x-x2==1:
        ans = a[i-1] + ans
        i-=1
    elif x-x3==1:
        ans = b[j-1] + ans
    elif x==x2:
        i-=1
    else:
        j-=1
print(ans)

Submission status: Wrong Answer

Solution code:
a = input()
b = input()
dp=[[0 for i in range(len(b)+1)] for j in range(len(a)+1)]
for p in range(2, len(a)+len(b)+1):
    for j in range(max(1, p-len(a)), min(p, len(b)+1)):
        i = p-j
        if a[i-1]==b[j-1]:
            x1 = 1 + dp[i-1][j-1]
        else:
            x1 = dp[i-1][j-1]
        x2 = dp[i][j-1]
        x3 = dp[i-1][j]
        dp[i][j] = max(x1, x2, x3)
mm = (dp[-1][-1])
ans = ''
i = len(a)
j = len(b)
while(len(ans)<mm):
    x1 = dp[i-1][j-1]
    x2 = dp[i-1][j]
    x3 = dp[i][j-1]
    x = dp[i][j]
    if x-x1==1:
        ans = a[i-1] + ans
        i-=1
        j-=1
    elif x-x2==1:
        ans = a[i-1] + ans
        i-=1
    elif x-x3==1:
        ans = b[j-1] + ans
    else:
        i-=1
print(ans)

Submission status: Wrong Answer

Solution code:
s1 = input()
s2 = input()
arra = ["-"]
arrb = ["-"]
for i in s1:
    arra.append(i)
for i in s2:
    arrb.append(i)
n1 = len(s1)
n2 = len(s2)
temparr = ["" for i in range(n2 + 1)]
dp = [temparr[::] for i in range(n1 + 1)]

for i in range(1, n1 + 1):
    for j in range(1 , n2 + 1):
        print("i " + str(i) + " j " + str(j))
        if arra[i] != arrb[j]:
            dig = dp[i -1][j-1]
            upp = dp[i - 1][j]
            left = dp[i][j - 1]
            dign = len(dig)
            uppn = len(upp)
            leftn = len(left)
            if dign >= uppn and dign >= leftn:
                dp[i][j] = dig 
            elif uppn >= dign and uppn >= leftn:
                dp[i][j] = upp
            else:
                dp[i][j] = left
        else:
            dig = dp[i -1][j-1] + arra[i]
            upp = dp[i - 1][j]
            left = dp[i][j - 1]
            dign = len(dig)
            uppn = len(upp)
            leftn = len(left)
            if dign >= uppn and dign >= leftn:
                dp[i][j] = dig 
            elif uppn >= dign and uppn >= leftn:
                dp[i][j] = upp
            else:
                dp[i][j] = left

# for i in dp:
#     print(i) 
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

# Input#
# n = int(input())
# n, k = map(int, input().split())
# a = list(map(int, input().split()))

s = input()
t = input()

memo = [[-1 for i in range(len(t) + 1)] for j in range(len(s) + 1)]

for i in range(len(s) + 1):
    memo[i][0] = 0

for i in range(len(t) + 1):
    memo[0][i] = 0


def dp(i, j):
    if memo[i][j] == -1:
        if s[i - 1] == t[j - 1]:
            memo[i][j] = dp(i - 1, j - 1) + 1
        else:
            memo[i][j] = max(dp(i - 1, j), dp(i, j - 1))

    return memo[i][j]


for i in range(min(len(s), len(t))):
    tmp = dp(i, i)

for i in range(len(s)):
    tmp = dp(i, len(t))

for i in range(len(t)):
    tmp = dp(len(s), i)

max = dp(len(s), len(t))

ans = ""

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

while i > 0 and j > 0:
    if memo[i][j] == memo[i - 1][j - 1] + 1:
        ans = s[i - 1] + ans
        i -= 1
        j -= 1
    elif memo[i][j] == memo[i - 1][j]:
        i -= 1
    else:
        j -= 1

print("{}".format(ans))

Submission status: Wrong Answer

Solution code:
s1=list(input())
s2=(input())
m=len(s1)
n=len(s2)
ans=[]
def lcs(i,j):
    if i<0 or j<0:
        return 0
    if s1[i]==s2[j]:
        global ans
        ans.append(i)
        count=lcs(i-1,j-1)+1
    else:
        count=max(lcs(i-1,j),lcs(i,j-1))
    return count

#print(lcs(m-1,n-1))
ans.sort()
word=''
for i in set(ans):
    word+=s1[i]
print(word)

Submission status: Wrong Answer

Solution code:
#import sys


#def input(): return sys.stdin.readline().rstrip()


S = input()
T = input()
dp = [[[0, "", (0,0)] for i in range(len(T))] for j in range(len(S))]
# dp[i][j] := i,j までの最大のもの。(length, string,before)
for i in range(len(S)):
    for j in range(len(T)):
        if i==0 or j==0 : continue
        if S[i] == T[j]:
            dp[i][j][0] = dp[i-1][j-1][0]+1
            dp[i][j][1] = S[i]
            dp[i][j][2] = (i-1, j-1)
        else:
            if dp[i][j-1][0] >= dp[i-1][j][0]:
                dp[i][j][0] = dp[i][j-1][0]
                dp[i][j][2] = (i, j-1)

            elif dp[i][j-1][0] < dp[i-1][j][0]:
                dp[i][j][0] = dp[i-1][j][0]
                dp[i][j][2] = (i-1, j)

def solve(X, Y):
 
    if X == 0:
        for i in range(Y):
            if T[i] == S[X]:
                return S[X]
        return ""
    elif Y == 0:
        for i in range(X):
            if S[i] == T[Y]:
                return T[Y]
        return ""

    else:
        x, y = dp[X][Y][2]
        return solve(x, y)+dp[X][Y][1]
    
print(solve(len(S)-1,len(T)-1))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(6009)
s=input()
t=input()
n=len(s)
m=len(t)
dp=[[-1 for j in range(m+1)] for i in range(n+1)]
def lcs(i,j):
	if dp[i][j]!=-1:
		return dp[i][j]
	if i*j==0:
		return 0
	if s[i-1]==t[j-1]:
		r=lcs(i-1,j-1)+1
	else:
		r=max(lcs(i,j-1),lcs(i-1,j))
	dp[i][j]=r
	return r
		
		

lcs(n,m)

i=n
j=m
st=""
while dp[i][j]!=-1:
	while dp[i-1][j]==dp[i][j]:
		i-=1
	while dp[i][j-1]==dp[i][j]:
		j=j-1
	j-=1
	st+=s[i-1]
	i-=1
print(st[::-1])

Submission status: Wrong Answer

Solution code:
text1 = input()
text2 = input()
n, m = len(text1), len(text2)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    if text1[i] == text2[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])

Submission status: Wrong Answer

Solution code:

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

Submission status: Wrong Answer

Solution code:

s=input()
n=len(s)
t=input()
m=len(t)
dp=[["" for i in range(m)] for j in range(n)]

if s[0]==t[0]:
	dp[0][0]=s[0]
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]+s[i]
		else:
			a=dp[i-1][j]
			b=dp[i][j-1]
			if len(a)>len(b):
				dp[i][j]=a
			else:
				dp[i][j]=b
print(dp[n-1][m-1])

Submission status: Wrong Answer

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

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


ans = " "
i = len(s) - 1
j = len(t) - 1
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        ans = s[i] + ans
        i -= 1
        j -= 1
    elif i == 0:
        if dp[i][j] == 1:
            ans = s[i] + ans
        break
    elif j == 0:
        if dp[i][j] == 1:
            ans = t[j] + ans
        break
    else:
        if dp[i-1][j] != dp[i][j]:
            j -= 1
        elif dp[i][j-1] != dp[i][j]:
            i -= 1
        else:
            j -= 1
            i -= 1
print(ans)

Submission status: Wrong Answer

Solution code:


INF = float('inf')


def tc():
    s = input()
    t = input()
    n, m = len(s), len(t)

    # dp[i][j] = LCS so far up to pos i in s and pos j in 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]:  # if chars are the same, use them both
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
            dp[i][j + 1] = max(dp[i][j + 1], dp[i][j])

    ans_len = max(max(r) for r in dp)
    i, j = n, m
    ans = ''
    # prev = t[-1]
    while len(ans) < ans_len:
        if dp[i - 1][j - 1] < dp[i][j]:
            ans += t[j - 1]
            i -= 1
        # prev = t[j - 1]
        j -= 1
        if j < 0:
            i -= 1
            j = m
    print(''.join(reversed(ans)))


tc()

Submission status: Wrong Answer

Solution code:


INF = float('inf')


def tc():
    s = input()
    t = input()
    n, m = len(s), len(t)

    # dp[i][j] = LCS so far up to pos i in s and pos j in 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]:  # if chars are the same, use them both
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
            dp[i][j + 1] = max(dp[i][j + 1], dp[i][j])

    ans_len = max(max(r) for r in dp)
    i, j = n, m
    ans = ''
    # prev = t[-1]
    while len(ans) < ans_len:
        if dp[i - 1][j - 1] < dp[i][j]:
            print(i, j)
            ans += t[j - 1]
            i -= 1
        # prev = t[j - 1]
        j -= 1
        if j < 0:
            i -= 1
            j = m
    print(''.join(reversed(ans)))


tc()

Submission status: Wrong Answer

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

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

i, j = n, m

ans = []

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

print(reversed(ans))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


s = S()
t = S()
S,T = len(s),len(t)
dp = [[0]*(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] = 1 + dp[i][j]
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])



ans = ""
while dp[S][T]:
    if dp[S][T] == dp[S-1][T-1] + 1:
        S -= 1
        T -= 1
        ans = s[S] + ans
    elif dp[S][T] == dp[S - 1][T]:
        S -= 1
    else:
        T -= 1


if len(ans) == 0:
    print("")
else:
    print(ans)