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
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = np.array(list(readline().decode()), 'U1')[:-1]
T = np.array(list(readline().decode()), 'U1')[:-1]

def longest_common_subsequence(S, T):
    """compute table dp satisfying: 
    dp[i,j] = LCS(S[:i], T[:j])"""
    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])  # 左から
    return dp

dp = longest_common_subsequence(S, T)

answer = []
i, j = len(S), len(T)
while i > 0 and j > 0:
    if dp[i,j] == dp[i-1,j-1] + 1:
        answer.append(S[i-1])
        i,j = i-1,j-1
    elif dp[i,j] == dp[i-1,j]:
        i -= 1
    else:
        j -= 1
    
answer = ''.join(reversed(answer))
print(answer)

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])
len_=dp[len(s)][len(t)]
s_now=len(s)-1
t_now=len(t)-1
ans=''
if len_==0:
  print(ans)
  exit()
while len_>0:
  if s[s_now]==t[t_now]:
    ans=ans+s[s_now]
    len_+=-1
    s_now+=-1
    t_now+=-1
    
  else:
    if dp[s_now][t_now]==dp[s_now][t_now-1]:
      t_now=t_now-1
    else:
        s_now=s_now-1
ans=ans[::-1]
print(ans)

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])
len_=dp[len(s)][len(t)]
s_now=len(s)-1
t_now=len(t)-1
ans=''
if len_==0:
  print(ans)
  exit()
while len_>0:
  if s[s_now]==t[t_now]:
    ans=ans+s[s_now]
    len_+=-1
    s_now+=-1
    t_now+=-1
    
  else:
    if dp[s_now][t_now]==dp[s_now][t_now-1]:
      t_now=t_now-1
    else:
        s_now=s_now-1
print(ans)

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
n = len(s)
m = len(t)
dp=[]
for i in range(n):
    dp.append([""]*m)
if(s[0]==t[0]):
    for i in range(n):
        dp[i][0]=s[0]
    for j in range(m):
        dp[0][j]=s[0]
for i in range(1,n):
    for j in range(1,m):
        sb = max([dp[i-1][j-1],dp[i][j-1]],key=lambda x:len(x))
        if(s[i]==t[j]):
            dp[i][j]= max([dp[i-1][j-1]+s[i],sb],key=lambda x:len(x))
        else:
            dp[i][j] = sb
print(dp[n-1][m-1])

Submission status: Wrong Answer

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

dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]
ans=[[[0,0] for _ in range(len(t)+1)] for _ in range(len(s)+1)]

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

i=len(s)
j=len(t)
ss=[]
while i>0 and j>0:
    i,j=ans[i][j]
    ss.append(s[i])

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

Submission status: Wrong Answer

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

a=len(s)
b=len(t)

dp=[ [0 for _ in range(a+1)] for _ in range(b+1)]

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

#print(dp)
for i,k in enumerate(dp[-1]):
    if i==0:
        pass
    else:
        if dp[-1][i]>dp[-1][i-1]:
            ans += s[i-1]
            
print(ans)

Submission status: Wrong Answer

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

        
kotae = []
 
while(i >= 0 and j >= 0):
    if(dp[i+1][j+1] == dp[i][j+1]):
        i -= 1
    elif(dp[i+1][j+1] == dp[i+1][j]):
        j -= 1
    else:
        i -= 1
        j -= 1
        kotae.append(s[i])
 
kotae.reverse()
kotae = "".join(kotae)
print(kotae)

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
n=len(t)
m=len(s)
dp=[['']*(n+1) for i in range(m+1)]
lendp=[[0]*(n+1) for i in range(m+1)]
for i in range(m):
  for j in range(n):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+s[i]
      lendp[i+1][j+1]=lendp[i][j]+1

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

      else:
        dp[i+1][j+1]=dp[i+1][j]

        
print(dp[m][n])
#print(dp)

Submission status: Wrong Answer

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

for s_i in range(len(s)):
    for t_i in range(len(t)):
        if s[s_i] == t[t_i]:
            dp[s_i+1][t_i+1] = dp[s_i][t_i] + 1
        else:
            dp[s_i+1][t_i+1] = max(dp[s_i][t_i+1], dp[s_i+1][t_i])

for i in range(len(s)+1):
    print(dp[i])
ans = []
s_i = len(s)
t_i = len(t)
while s_i > 0 and t_i > 0:
    if dp[s_i][t_i] == dp[s_i][t_i-1]:
        t_i -= 1
    elif dp[s_i][t_i] == dp[s_i-1][t_i]:
        s_i -= 1
    else: #dp[s_i][t_i]  dp[s_i-1][t_i] == 1:
        s_i -= 1
        t_i -= 1
        if t_i >= 0:
            ans.append(t[t_i])


print("".join(ans[::-1]))

Submission status: Wrong Answer

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

for s_i in range(len(s)):
    for t_i in range(len(t)):
        if s[s_i] == t[t_i]:
            dp[s_i+1][t_i+1] = dp[s_i][t_i] + 1
        else:
            dp[s_i+1][t_i+1] = max(dp[s_i][t_i+1], dp[s_i+1][t_i])

ans = []
s_i = len(s)
t_i = len(t)
while s_i > 0 and t_i > 0:
    if dp[s_i][t_i] == dp[s_i][t_i-1] and dp[s_i-1][t_i-1] == dp[s_i][t_i]:
        s_i -= 1
        t_i -= 1
    elif dp[s_i][t_i] - dp[s_i-1][t_i-1] == 1:
        s_i -= 1
        t_i -= 1
        if s_i >= 0:
            ans.append(s[s_i])
    else: #dp[s_i][t_i] - dp[s_i-1][t_i] == 1:
        t_i -= 1
        if t_i >= 0:
            ans.append(t[t_i])

print("".join(ans[::-1]))

Submission status: Wrong Answer

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

ans = ''
sl = len(s)
tl = len(t)
while sl > 0 and tl > 0:
    if s[sl-1] == t[tl-1]:
        sl -= 1
        tl -= 1
        ans = s[sl] + ans
        continue
    if dp[tl][sl] == dp[tl][sl-1]:
        sl -= 1
    elif dp[tl][sl] == dp[tl-1][sl]:
        tl -= 1
print(ans)

Submission status: Wrong Answer

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

dp = [[0] * (len(s)+1) for _ in range(len(t)+1)]
for i in range(1, len(t)+1):
    ti = t[i-1]
    dp[i] = dp[i-1][:]
    for j in range(1, len(s)+1):
        if ti == s[j-1]:
            dp[i][j] = dp[i][j-1] + 1
        else:
            if dp[i][j-1] >= dp[i][j]:
                dp[i][j] = dp[i][j-1]
ans = ''
sl = len(s)
tl = len(t)
while sl > 0 and tl > 0:
    if s[sl-1] == t[tl-1]:
        sl -= 1
        tl -= 1
        ans = s[sl] + ans
        continue
    if dp[tl][sl] == dp[tl][sl-1]:
        sl -= 1
    elif dp[tl][sl] == dp[tl-1][sl]:
        tl -= 1
print(ans)

Submission status: Wrong Answer

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

dp = [[0] * (len(s)+1) for _ in range(len(t)+1)]
for i in range(1, len(t)+1):
    ti = t[i-1]
    dp[i] = dp[i-1].copy()
    for j in range(1, len(s)+1):
        if ti == s[j-1]:
            dp[i][j] = dp[i][j-1] + 1
        else:
            if dp[i][j-1] >= dp[i][j]:
                dp[i][j] = dp[i][j-1]
# ans = ''
# sl = len(s)
# tl = len(t)
# while sl > 0 and tl > 0:
    # if s[sl-1] == t[tl-1]:
        # sl -= 1
        # tl -= 1
        # ans = s[sl] + ans
        # continue
    # if dp[tl][sl] == dp[tl][sl-1]:
        # sl -= 1
    # elif dp[tl][sl] == dp[tl-1][sl]:
        # tl -= 1
# print(ans)

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

Submission status: Wrong Answer

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

dp = [[0] * (len(s)+1) for _ in range(len(t)+1)]
for i in range(1, len(t)+1):
    ti = t[i-1]
    dp[i] = dp[i-1]
    for j in range(1, len(s)+1):
        if ti == s[j-1]:
            dp[i][j] = dp[i][j-1] + 1
        else:
            if dp[i][j-1] >= dp[i][j]:
                dp[i][j] = dp[i][j-1]
ans = ''
sl = len(s)
tl = len(t)
while sl > 0 and tl > 0:
    if s[sl-1] == t[tl-1]:
        sl -= 1
        tl -= 1
        ans = s[sl] + ans
        continue

    if dp[tl][sl] == dp[tl][sl-1]:
        sl -= 1
    elif dp[tl][sl] == dp[tl-1][sl]:
        tl -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
s = list(input())
t = list(input())
ns=len(s)
nt=len(t)
dp=[[0]*(nt+1) for _ in range(ns+1)]
for i in range(ns):
    for j in range(nt):
        if s[i]==t[j]:
            dp[i+1][j+1]=max(dp[i+1][j+1], dp[i][j]+1)
        else:
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
ans=[]
i,j=ns,nt
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(''.join(ans))

Submission status: Wrong Answer

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

#dp[i][j] : sをi番目、tをj番目まで読んだ時の共通部分列の長さの最大

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

dp = [["" for _ in range(m)] for _ in range(n)]
if s[0] == t[0]:
    dp[0][0] = s[0]

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


import numpy as np

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:
            candi = [dp[i-1][j], dp[i][j-1]]
            longer = np.argmax(list(map(len, candi)))
            dp[i][j] = candi[longer]
print(dp[-1][-1])

Submission status: Wrong Answer

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

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

# dp[i][j] = s[:i], t[:j] まで見たときの最長共通部分列の長さ
dp = [[0]*(m+1) for _ in range(n+1)]

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

i = n
ans = ''
for j in reversed(range(1, m+1)):
    if dp[i][j] != dp[i-1][j-1]:
        ans += t[j-1]
        i -=1
print(ans[::-1])

Submission status: Wrong Answer

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

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

# dp[i][j] = s[:i], t[:j] まで見たときの最長共通部分列の長さ
dp = [[0]*(m+1) for _ in range(n+1)]

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

i = n
ans = ''
for j in reversed(range(1, m+1)):
    if dp[i][j] != dp[i][j-1]:
        ans += t[j-1]
        i -=1
print(ans[::-1])

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *
		
s = input()
t = input()

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

common = [[] for _ in range(len(t))]

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

ans = ""
for x in common:
	if x:
		ans += x[0]

print(ans)

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

  ns=len(s)
  nt=len(t)

  dp=[[0]*(ns+1) for _ in range(nt+1)]

  for i in range(nt):
    for j in range(ns):
      if t[i]==s[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])

  x=dp[nt][ns]
  # print(x)
  sty=nt
  stx=ns
  # print(dp)
  ans=''
  while True:
    if dp[sty][stx]==0:
      ans=list(ans)
      ans.reverse()
      return ''.join(ans)

    if dp[sty][stx]==dp[sty-1][stx-1]+1:
      ans+=s[stx-1]

      stx-=1
      sty-=1

    elif dp[sty][stx]==dp[sty-1][stx]:
      sty-=1
    elif dp[sty][stx]==dp[sty][stx-1]:
      stx-=1

    # print(stx,sty)

  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
s=input()
t=input()
dp=[[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
for i,sele in enumerate(s):
  for j ,tele in enumerate(t):
    if sele==tele:
      dp[i+1][j+1]=dp[i][j] +1
    else :
      dp[i+1][j+1]=dp[i+1][j] if dp[i+1][j]>=dp[i][j+1] else dp[i][j+1]     
res=""
i=len(s)
j=len(t)
#print(dp)
while True:
#for k in range(9):
  #rint(i,j,dp[i][j])
  if i-1>=0:
    if dp[i-1][j]==dp[i][j]:
      i=i-1
      continue
  if j-1>=0:
    if dp[i][j-1]==dp[i][j]:
      j=j-1
      continue
  if i-1>=0 and j-1>=0:
    if dp[i-1][j-1]==dp[i][j]-1:
      j=j-1
      i=i-1
      res=s[i]+res
      print(i,res)
      if dp[i][j]==0:
        break
      continue
  break
print(res)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
s=input()
t=input()
dp=[[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
for i,sele in enumerate(s):
  for j ,tele in enumerate(t):
    if sele==tele:
      dp[i+1][j+1]=dp[i][j] +1
    else :
      dp[i+1][j+1]=dp[i+1][j] if dp[i+1][j]>=dp[i][j+1] else dp[i][j+1]     
res=""
i=len(s)
j=len(t)
while True:
#for k in range(9):
  #rint(i,j,dp[i][j])
  if i-1>=0:
    if dp[i-1][j]==dp[i][j]:
      i=i-1
      continue
  if j-1>=0:
    if dp[i][j-1]==dp[i][j]:
      j=j-1
      continue
  if i-1>=0 and j-1>=0:
    if dp[i-1][j-1]==dp[i][j]-1:
      j=j-1
      i=i-1
      res+=s[i]
      if dp[i][j]==0:
        break
      continue
  break
print(res)

Submission status: Wrong Answer

Solution code:
import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

def LCS(s, t):
	n, m = len(s), len(t)
	dp = [[0 for i in range(m+1)] for j in range(n+1)]
	ans = ""; max_sf = 0
	for i in range(n+1):
		for j in range(m+1):
			if i == 0 or j == 0:
				dp[i][j] = 0
			elif s[i-1] == t[j-1]:
				dp[i][j] = 1 + dp[i-1][j-1]
				if max_sf < dp[i][j]:
					ans += s[i-1]
					max_sf += 1
			else:
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
	# index = dp[n][m]
	# ans = [" "]*index
	# i, j = n, m
	# while index:
	# 	if s[i-1] == t[j-1]:
	# 		ans[index-1] =  s[i-1]
	# 		index -= 1
	# 		i -= 1; j -= 1
	# 	elif dp[i-1][j] > dp[i][j-1]:
	# 		i -= 1
	# 	else:
	# 		j -= 1
	return(("").join(ans))

def solve():
	s1 = inp().strip(); s2 = inp().strip()
	print(LCS(s1, s2))









if __name__ == "__main__":
	solve()

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
x=len(s)
y=len(t)
dp=[[0 for i in range(y)] for i in range(x)]
for i in range(x):
	if(t[-1] in s[:i+1]):
		dp[i][y-1]=t[-1]
	else:
		dp[i][y-1]=""
for j in range(y):
	if(s[-1] in t[:j+1]):
		dp[x-1][j]=s[-1]
	else:
		dp[x-1][j]=""
for i in range(x-2,-1,-1):
	for j in range(y-2,-1,-1):
		if(s[i]==t[j]):
			dp[i][j]=s[i]+dp[i+1][j+1]
		else:
			if(len(dp[i+1][j])>len(dp[i][j+1])):
				dp[i][j]=dp[i+1][j]
			else:
				dp[i][j]=dp[i][j+1]
print(dp[0][0])

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
x=len(s)
y=len(t)
dp=[[0 for i in range(y)] for i in range(x)]
for i in range(x):
	if(t[-1] in s[:i+1]):
		dp[i][y-1]=t[-1]
	else:
		dp[i][y-1]=""
for j in range(y):
	if(s[-1] in t[:i+1]):
		dp[x-1][j]=s[-1]
	else:
		dp[x-1][j]=""
for i in range(x-2,-1,-1):
	for j in range(y-2,-1,-1):
		if(s[i]==t[j]):
			dp[i][j]=s[i]+dp[i+1][j+1]
		else:
			if(len(dp[i+1][j])>len(dp[i][j+1])):
				dp[i][j]=dp[i+1][j]
			else:
				dp[i][j]=dp[i][j+1]
print(dp[0][0])

Submission status: Wrong Answer

Solution code:
n=input()
m=input()
x=len(n)
 
y=len(m)
 
dp=[[0 for i in range(y+1)] for j in range(x+1)]
#print(len(dp),len(dp[0]))
for i in range(0,x+1):
  for j in range(0,y+1):
    if(i==0 or j==0):
      dp[i][j]=0
    elif n[i-1]==m[j-1]:
      dp[i][j]=1+dp[i-1][j-1]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
 
i=x
j=y
ans=""
 
while i>=0 and j>=0:
    if(n[i-1]==m[j-1]):
        ans=ans+n[i-1]
        #print(n[i-1],1)
        i=i-1
        j=j-1
    else:
        mx=max(dp[i-1][j],dp[i][j-1])
        if mx==dp[i-1][j]:
            i=i-1
        else:
            j=j-1
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
n=input()
m=input()
x=len(n)

y=len(m)

dp=[[0 for i in range(y+1)] for j in range(x+1)]
#print(len(dp),len(dp[0]))
for i in range(0,x+1):
  for j in range(0,y+1):
    if(i==0 or j==0):
      dp[i][j]=0
    elif n[i-1]==m[j-1]:
      dp[i][j]=1+dp[i-1][j-1]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
j=y
i=x
ans=""
#print(i,j)
while i>0 and j>0:
    if(n[i-1]==m[j-1]):
        print(n[i-1],m[j-1])
        ans=ans+n[i-1]
        #print(n[i-1],1)
        i=i-1
        j=j-1
    else:
        mx=max(dp[i-1][j],dp[i][j-1])
        if mx==dp[i-1][j]:
            i=i-1
        else:
            j=j-1

print(ans[::-1])

Submission status: Wrong Answer

Solution code:
n=input()
m=input()
x=len(n)

y=len(m)

dp=[[0 for i in range(y+1)] for j in range(x+1)]
#print(len(dp),len(dp[0]))
for i in range(0,x+1):
  for j in range(0,y+1):
    if(i==0 or j==0):
      dp[i][j]=0
    elif n[i-1]==m[j-1]:
      dp[i][j]=1+dp[i-1][j-1]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
 
i=x
j=y
ans=""

while i>=0 and j>=0:
    if(n[i-1]==m[j-1]):
        ans=ans+n[i-1]
        #print(n[i-1],1)
        i=i-1
        j=j-1
    else:
        mx=max(dp[i-1][j],dp[i][j-1])
        if mx==dp[i-1][j]:
            i=i-1
        else:
            j=j-1

print(ans[::-1])

Submission status: Wrong Answer

Solution code:
n=input()
m=input()
x=len(n)

y=len(m)

dp=[[0 for i in range(y+1)] for j in range(x+1)]
#print(len(dp),len(dp[0]))
for i in range(0,x+1):
  for j in range(0,y+1):
    if(i==0 or j==0):
      dp[i][j]=0
    elif n[i-1]==m[j-1]:
      dp[i][j]=1+dp[i-1][j-1]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
 
i=x
j=y
ans=""

while i>=0 and j>=0:
    if(n[i-1]==m[j-1]):
        ans=ans+n[i-1]
        #print(n[i-1],1)
        i=i-1
        j=j-1
    else:
        mx=max(dp[i-1][j],dp[i][j-1])
        if mx==dp[i-1][j]:
            i=i-1
        else:
            j=j-1

print(ans[::-1])

Submission status: Wrong Answer

Solution code:
a, b = input(), input()
n, m = len(a), len(b)
dp = [[[0, 0, 0] for _ in range(m+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        skip_a = dp[i][i+1]
        skip_b = dp[i+1][j]
        match = dp[i][j]
        match_len = match[0] + 1 if a[i] == b[j] else 0
        if skip_a[0] >= skip_b[0] and skip_a[0] >= match_len:
            dp[i+1][j+1] = [skip_a[0], i, j+1]
        elif skip_b[0] >= skip_a[0] and skip_b[0] >= match_len:
            dp[i+1][j+1] = [skip_b[0], i+1, j]
        else:
            dp[i+1][j+1] = [match_len, i, j]
ans = []
r = n
c = m
while r >= 1 and c >= 1:
    parent = [dp[r][c][1], dp[r][c][2]]
    
    if parent[0] == r-1 and parent[1] == c-1:
        ans.append(a[r-1])
    
    r = parent[0]
    c = parent[1]

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

"""
int main() {
    string a;
    string b;
    cin >> a >> b;
    
    //scanf("%s%s", &a.c_str(), &b.c_str());
    int n = a.length();
    int m = b.length();
    vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(m+1, vector<int>(3)));
    // {length, parent_r, parent_c}
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            vector<int> skip_a = dp[i][j+1];
            vector<int> skip_b = dp[i+1][j];
            vector<int> match = dp[i][j];
            int match_len = a[i] == b[j] ? match[0] + 1 : 0;
            if (skip_a[0] >= skip_b[0] && skip_a[0] >= match_len) {
                dp[i+1][j+1] = {skip_a[0], i, j+1};
            }
            else if (skip_b[0] >= skip_a[0] && skip_b[0] >= match_len) {
                dp[i+1][j+1] = {skip_b[0], i+1, j};
            }
            else {
                dp[i+1][j+1] = {match_len, i, j};
            }
        }
    }
    
    string ans;
    int r = n;
    int c = m;
    while (r >= 1 && c >= 1) {
        //cout << r << " " << c << endl;
        vector<int> parent = {dp[r][c][1], dp[r][c][2]};
        
        if (parent[0] == r-1 && parent[1] == c-1) {
            ans.push_back(a[r-1]);
        }
        r = parent[0];
        c = parent[1];
    }
    reverse(ans.begin(), ans.end());
	cout << ans << endl;
	//cout << dp[n][m][0] << endl;
	
	return 0;
}
"""

Submission status: Wrong Answer

Solution code:
def LCS(s1, s2):
    l1, l2 = len(s1), len(s2)
    dp = [[0 for _ in range(l2 + 1)] for _ in range(l1 + 1)]
    for i in range(1, l1 + 1):
        for j in range(1, l2 + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
    return dp[l1][l2]


if __name__ == '__main__':
    s1 = input()
    s2 = input()
    print(LCS(s1, s2))

Submission status: Wrong Answer

Solution code:
def lcs(s1,s2,m,n,t):
    l=[]
    for i in range(0,m+1):
        t[i][0]=1
    for i in range(1,n+1):
        t[0][i]=0
    for i in range(1,m+1):
        for j in range(1,n+1):
            if s1[i-1]==s2[j-1]:
                t[i][j]=t[i-1][j-1]+1
            else:
                t[i][j]=max(t[i-1][j],t[i][j-1])
    i=m
    j=n
    while(i>0 and j>0):
        if s1[i-1]==s2[j-1]:
            l.append(s1[i-1])
            i-=1
            j-=1
        else:
            if t[i-1][j]>t[i][j-1]:
                i-=1
            else:
                j-=1
    l.reverse()            
    b="".join(str(a) for a in l)
    return b
s1=input()
s2=input()
m=len(s1)
n=len(s2)
t=[[0 for x in range(n+1)] for x in range(m+1)] 
d=lcs(s1,s2,m,n,t)
print(d)

Submission status: Wrong Answer

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): 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)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

S = list(ST())
T = list(ST())
dp = FILL2(0,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+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])

l = dp[len(S)][len(T)]
i = len(S)
j = len(T)
ans = ''
while l > 0:
    if S[i-1]==T[j-1]:
        i -= 1
        j -= 1
        l -= 1
        ans = S[i]+ans
    else:
        if dp[i][j-1]==dp[i][j]:
            j -= 1
        else:
            i -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
if len(s)>len(t):
    s,t=t,s
lenS = len(s)
lenT = len(t)
dp = []
for i in range(lenS+1):
    dp.append([0]*(lenT+1))
for i in range(1,lenS+1):
    for j in range(1,lenT+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])

ans=""
maxlen=dp[lenS][lenT]
i=lenS
j=lenT
while dp[i][j]==maxlen and dp[i][j]!=0:
    j-=1
    if dp[i][j]!=maxlen:
        ans+=t[j]
        i-=1
        maxlen=dp[i][j]
print(ans[::-1])

Submission status: Wrong Answer

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

print()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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