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:
#!/usr/bin/env python3
import sys


def solve(s: str, t: str):
    ls=len(s)
    lt=len(t)
    dp=[[0]*(lt+1) for _ in range(ls+1)] # dp[0:ls+1][0:lt+1]

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

    ans=""
    la=dp[ls][lt]
    ttag=lt
    for i in reversed(range(ls+1)):
        if dp[i][ttag]<la:
            assert(dp[i][ttag]==la-1)
            ans=s[i]+ans
            la-=1
            ttag-=1
    assert(la==0)
    
    print(ans)

    return


# 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()

Submission status: Wrong Answer

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


def solve(s: str, t: str):
    ls=len(s)
    lt=len(t)
    dp=[[0]*(lt+1) for _ in range(ls+1)] # dp[0:ls+1][0:lt+1]

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

    ans=""
    la=dp[ls][lt]
    ttag=lt
    for i in reversed(range(ls+1)):
        if dp[i][ttag]<la:
            ans=s[i]+ans
            la-=1
            ttag-=1
    assert(la==0)
    
    print(ans)

    return


# 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()

Submission status: Wrong Answer

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


def solve(s: str, t: str):
    ls=len(s)
    lt=len(t)
    dp=[[0]*(lt+1) for _ in range(ls+1)] # dp[0:ls+1][0:lt+1]

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

    ans=""
    la=dp[ls][lt]
    ttag=lt
    for i in reversed(range(ls+1)):
        if dp[i][ttag]<la:
            ans=s[i]+ans
            la-=1
            ttag-=1

    print(ans)

    return


# 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()

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
sl,tl=len(s),len(t)
lcs=[[0]*(tl+1) for _ in range(sl+1)]
ans=''
for i in range(1,sl+1):
    for j in range(1,tl+1):
        if s[i-1]==t[j-1]:
            lcs[i][j]=lcs[i-1][j-1]+1
            ans+=s[i-1]
        else:
            lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1])
print(ans)

Submission status: Wrong Answer

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


def lcs(s, t)->list:
    sn = len(s)
    tn = len(t)
    dp = [[0 for _ in range(tn+1)] for _ in range(sn+1)]
    for i in range(sn):
        for j in range(tn):
            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+1][j+1], dp[i+1][j], dp[i][j+1])
    print(dp)
    return dp


def restore_str(lcs_dp)->str:
    restore = str()
    i = len(s)
    j = len(t)

    while i > 0 and j > 0:
        #print(i, j)
        if lcs_dp[i][j] == lcs_dp[i-1][j]: i -= 1
        elif lcs_dp[i][j] == lcs_dp[i][j-1]: j -= 1
        else: 
            restore = s[i-1] + restore
            i -= 1
            j -= 1

    return restore


def main():
    lcs_dp = lcs(s, t)
    ans = restore_str(lcs_dp)
    return print(ans)


if __name__ == '__main__':
    main()

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

match = []
now_row = Ls
now_column = Lt
for _ in range(dp[-1][-1]):
    for i in range(now_column):
        if dp[now_row][now_column-i] != dp[now_row][now_column-i-1]:
            match.append(T[now_column - i-1])
            now_row -= 1
            now_column -= i+1
            break

match.reverse()
print("".join(match))

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    s = np.array([str(i) for i in input()], dtype=np.unicode)
    t = np.array([str(i) for i in input()], dtype=np.unicode)

    num_s = int(s.shape[0])
    num_t = int(t.shape[0])


    dp = np.zeros((num_s +1, num_t +1), dtype='int32')

    eq = s[:,None] == t[None,:]
    # print(len(eq[0]))

    for i in range(num_s):
        np.maximum(dp[i, 1:], dp[i, :-1] + eq[i], out=dp[i+1, 1:])
        np.maximum.accumulate(dp[i+1], out=dp[i+1])
    # print(dp)

    res=''
    pos_s = num_s
    pos_t = num_t


    while len(res) < np.max(dp[num_s]):
        temp = dp[pos_s, pos_t]
        # print(temp)
        if dp[pos_s-1, pos_t] == temp:
            pos_s -= 1

        if dp[pos_s, pos_t-1] == temp:
            pos_t -= 1

        else:
            res += s[pos_s-1]
            pos_s -= 1
            pos_t -= 1

        # print(res, pos_s-1)
        
    print(res[::-1])

main()

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    s = np.array([str(i) for i in input()], dtype='U1')
    t = np.array([str(i) for i in input()], dtype='U1')

    num_s = int(s.shape[0])
    num_t = int(t.shape[0])


    dp = np.zeros((num_s +1, num_t +1), dtype='int32')

    eq = s[:,None] == t[None,:]
    # print(len(eq[0]))

    for i in range(num_s):
        np.maximum(dp[i, 1:], dp[i, :-1] + eq[i], out=dp[i+1, 1:])
        np.maximum.accumulate(dp[i+1], out=dp[i+1])
    # print(dp)

    res=''
    pos_s = num_s
    pos_t = num_t


    while len(res) < np.max(dp[num_s]):
        temp = dp[pos_s, pos_t]
        # print(temp)
        if dp[pos_s-1, pos_t] == temp:
            pos_s -= 1

        if dp[pos_s, pos_t-1] == temp:
            pos_t -= 1

        else:
            res += s[pos_s-1]
            pos_s -= 1
            pos_t -= 1

        # print(res, pos_s-1)
        
    print(res[::-1])

main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
s = input()
t = input()
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(len(s)):
    dp[i][0] = 0
for j in range(len(t)):
    dp[0][j] = 0
for i in range(0, len(s)):
    for j in range(0, 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])
dpt = list(map(list, zip(*dp)))
i = len(s)
j = len(t)
ans = ''
for a in range(dp[len(s)][len(t)], 0, -1):
    jj = bisect_left(dp[i], a)
    ii = bisect_left(dpt[j], a)
    ans += t[jj - 1]
    i = ii - 1
    j = jj - 1
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def calc_lcs(s, t):
  dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
  for i, si in enumerate(s, 1):
    for j, tj in enumerate(t, 1):
      dp[i][j] = max((dp[i-1][j-1] + 1) if si==tj else 0, dp[i-1][j], dp[i][j-1])

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

def main():
  s = input().strip()
  t = input().strip()
  print(calc_lcs(s, t))


if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def calc_lcs(s, t):
  dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
  for i, si in enumerate(s, 1):
    for j, tj in enumerate(t, 1):
      dp[i][j] = max((dp[i-1][j-1] + (1 if si==tj else 0), dp[i-1][j], dp[i][j-1]))

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

def main():
  s = input().strip()
  t = input().strip()
  print(calc_lcs(s, t))


if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def lcs(s, t):
  dp = [['' for _ in range(len(t)+1)] for _ in range(len(s)+1)]
  jmax = 0
  for i, si in enumerate(s, 1):
    for j, tj in enumerate(t[jmax:], jmax+1):
      dp[i][j] = min([(dp[i-1][j-1]+si) if si==tj else '', dp[i-1][j], dp[i][j-1]], key=lambda x: -len(x))
      if dp[i][j] < dp[i][j-1]:
        jmax = j-1
  return dp[-1][-1]

def main():
  s = input().strip()
  t = input().strip()
  print(lcs(s, t))


if __name__=='__main__':
  main()

Submission status: Wrong Answer

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

dp = [[0 for i in range(len(S)+1)] for j in range(len(T)+1)]

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

ans = []
for i in range(len(S)):
    if dp[len(T)][i+1]-dp[len(T)][i] == 1:
        ans.append(S[i])
print("".join(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    s = np.array([str(i) for i in input()], dtype='O')
    t = np.array([str(i) for i in input()], dtype='O')

    num_s = int(s.shape[0])
    num_t = int(t.shape[0])


    dp = np.zeros((num_s +1, num_t +1), dtype='int32')

    eq = s[:,None] == t[None,:]
    # print(len(eq[0]))

    for i in range(num_s):
        np.maximum(dp[i, 1:], dp[i, :-1] + eq[i], out=dp[i+1, 1:])
        np.maximum.accumulate(dp[i+1], out=dp[i+1])
    # print(dp)

    res=''
    pos_s = num_s
    pos_t = num_t


    while len(res) < np.max(dp[num_s]):
        temp = dp[pos_s, pos_t]
        # print(temp)
        if dp[pos_s-1, pos_t] == temp:
            pos_s -= 1

        if dp[pos_s, pos_t-1] == temp:
            pos_t -= 1

        else:
            res += s[pos_s-1]
            pos_s -= 1
            pos_t -= 1

        # print(res, pos_s-1)
        
    print(res[::-1])

main()

Submission status: Wrong Answer

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

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

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

            if dp[i - 1][j] < dp[i][j - 1]:
                mem_i[i][j] = i
                mem_j[i][j] = j - 1
            else:
                mem_i[i][j] = i - 1
                mem_j[i][j] = j

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

result = []
while (i != 0 and j != 0):
    _s = s[i-1]
    _t = t[j-1]

    if _s == _t:
        result.append(_s)
    i = mem_i[i][j] 
    j = mem_j[i][j]

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

Submission status: Wrong Answer

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

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

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

            if dp[i - 1][j] < dp[i][j - 1]:
                mem_i[i][j] = i
                mem_j[i][j] = j - 1
            else:
                mem_i[i][j] = i - 1
                mem_j[i][j] = j

i = len(s)
j = max(enumerate(dp[-1]), key=lambda x: x[1])[0]

result = []
while (i != 0 and j != 0):
    _s = s[i-1]
    _t = t[j-1]

    if _s == _t:
        result.append(_s)
    i = mem_i[i][j] 
    j = mem_j[i][j]

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

Submission status: Wrong Answer

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

dp = [[0 for _ in range(len(t))] for _ in range(len(s))]
mem_i = [[0 for _ in range(len(t))] for _ in range(len(s))]
mem_j = [[0 for _ in range(len(t))] for _ in range(len(s))]

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

            if dp[i - 1][j] < dp[i][j - 1]:
                mem_i[i][j] = i
                mem_j[i][j] = j - 1
            else:
                mem_i[i][j] = i - 1
                mem_j[i][j] = j

i = len(s)-1
j = max(enumerate(dp[-1]), key=lambda x: x[1])[0]

result = []
while (i != -1 and j != -1):
    _s = s[i]
    _t = t[j]

    if _s == _t:
        result.append(_s)
    i = mem_i[i][j] 
    j = mem_j[i][j]

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

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    readline = sys.stdin.readline

    s = readline().rstrip()
    t = readline().rstrip()

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

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

    rest = dp[len(s)][len(t)]

    ret = ''
    i, j = len(s), len(t)

    while rest > 0:
        if dp[i][j] == dp[i - 1][j - 1] + 1:
            ret = s[i - 1] + ret
            rest -= 1
            i -= 1
            j -= 1

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

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    readline = sys.stdin.readline

    s = readline().rstrip()
    t = readline().rstrip()

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

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

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

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

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


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

import bisect

def main():
	s=input().rstrip().decode('utf-8')
	t=input().rstrip().decode('utf-8')
	slen=len(s)
	tlen=len(t)
	
	dp=[[0]*(slen+1) for _ in range(tlen+1)]
	pr=[[0]*(slen+1) for _ in range(tlen+1)]
	
	
	for i in range(tlen):
		for j in range(slen):
			if s[j]==t[i]:
				dp[i+1][j+1]=dp[i][j]+1
				pr[i+1][j+1]=1
			elif dp[i][j+1]<dp[i+1][j]:
				dp[i+1][j+1]=dp[i+1][j]
				pr[i + 1][j + 1] = 2
			else:
				dp[i+1][j+1]=dp[1][j+1]
				pr[i + 1][j + 1] = 3
	
	ss=slen
	tt=tlen
	ans=""
	while ss>0 and tt>0:
		if pr[tt][ss]==1:
			ans+=s[ss-1]
			tt-=1
			ss-=1
		elif pr[tt][ss]==2:
			ss-=1
		else:
			tt-=1
	print(ans[::-1])
	
	
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    s = np.array([str(i) for i in input()])
    t = np.array([str(i) for i in input()])

    num_s = int(s.shape[0])
    num_t = int(t.shape[0])


    dp = np.zeros((num_s +1, num_t +1), dtype='int64')

    eq = s[:,None] == t[None,:]
    # print(len(eq[0]))

    for i in range(num_s):
        np.maximum(dp[i, 1:], dp[i, :-1] + eq[i], out=dp[i+1, 1:])
        np.maximum.accumulate(dp[i+1], out=dp[i+1])
    # print(dp)

    res=''
    pos_s = num_s
    pos_t = num_t


    while len(res) < np.max(dp[num_s]):
        temp = dp[pos_s, pos_t]
        # print(temp)
        if dp[pos_s-1, pos_t] == temp:
            pos_s -= 1

        if dp[pos_s, pos_t-1] == temp:
            pos_t -= 1

        else:
            res += s[pos_s-1]
            pos_s -= 1
            pos_t -= 1

        # print(res, pos_s-1)
        
    print(res[::-1])

main()

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    s = np.array([str(i) for i in input()])
    t = np.array([str(i) for i in input()])

    num_s = int(s.shape[0])
    num_t = int(t.shape[0])


    dp = np.zeros((num_s +1, num_t +1), dtype='int64')

    eq = s[:,None] == t[None,:]
    # print(len(eq[0]))

    for i in range(num_s):
        np.maximum(dp[i, 1:], dp[i, :-1] + eq[i], out=dp[i+1, 1:])
        np.maximum.accumulate(dp[i+1], out=dp[i+1])
    # print(dp)

    res=''
    pos_s = num_s
    pos_t = num_t


    while len(res) < np.max(dp[num_s]):
        temp = dp[pos_s, pos_t]
        # print(temp)
        if dp[pos_s-1, pos_t] == temp:
            pos_s -= 1

        if dp[pos_s, pos_t-1] == temp:
            pos_t -= 1

        if dp[pos_s-1, pos_t-1] != temp:
            res += s[pos_s-1]
            pos_s -= 1
            pos_t -= 1

        # print(res, pos_s-1)
            

    print(res[::-1])

main()

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    s = np.array([i for i in input()])
    t = np.array([i for i in input()])

    num_s = int(s.shape[0])
    num_t = int(t.shape[0])


    dp = np.zeros((num_s +1, num_t +1), dtype='int64')

    eq = s[:,None] == t[None,:]
    # print(len(eq[0]))

    for i in range(num_s):
        np.maximum(dp[i, 1:], dp[i, :-1] + eq[i], out=dp[i+1, 1:])
        np.maximum.accumulate(dp[i+1], out=dp[i+1])
    # print(dp)

    res=''
    pos_s = num_s
    pos_t = num_t


    while len(res) < np.max(dp[num_s]):
        temp = dp[pos_s, pos_t]
        # print(temp)
        if dp[pos_s-1, pos_t] == temp:
            pos_s -= 1

        if dp[pos_s, pos_t-1] == temp:
            pos_t -= 1

        if dp[pos_s-1, pos_t-1] != temp:
            res += s[pos_s-1]
            pos_s -= 1
            pos_t -= 1

        # print(res, pos_s-1)
            

    print(res[::-1])

main()

Submission status: Wrong Answer

Solution code:
import numpy as np

s = np.array([i for i in input()])
t = np.array([i for i in input()])

num_s = int(s.shape[0])
num_t = int(t.shape[0])


dp = np.zeros((num_s +1, num_t +1), dtype='int64')

eq = s[:,None] == t[None,:]
# print(len(eq[0]))

for i in range(num_s):
    np.maximum(dp[i, 1:], dp[i, :-1] + eq[i], out=dp[i+1, 1:])
    np.maximum.accumulate(dp[i+1], out=dp[i+1])
# print(dp)

res=''
pos_s = num_s
pos_t = num_t


while len(res) < np.max(dp):
    temp = dp[pos_s, pos_t]
    # print(temp)
    if dp[pos_s-1, pos_t] == temp:
        pos_s -= 1

    if dp[pos_s, pos_t-1] == temp:
        pos_t -= 1

    if dp[pos_s-1, pos_t-1] != temp:
        res += s[pos_s-1]
        pos_s -= 1
        pos_t -= 1

    # print(res, pos_s-1)
        

print(res[::-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

s = np.array([i for i in input()])
t = np.array([i for i in input()])

num_s = int(s.shape[0])
num_t = int(t.shape[0])


dp = np.zeros((num_s +1, num_t +1), dtype='int64')

eq = s[:,None] == t[None,:]
print(len(eq[0]))

for i in range(num_s):
    np.maximum(dp[i, 1:], dp[i, :-1] + eq[i], out=dp[i+1, 1:])
    np.maximum.accumulate(dp[i+1], out=dp[i+1])
# print(dp)

res=''
pos_s = num_s
pos_t = num_t


while len(res) < np.max(dp):
    temp = dp[pos_s, pos_t]
    # print(temp)
    if dp[pos_s-1, pos_t] == temp:
        pos_s -= 1

    if dp[pos_s, pos_t-1] == temp:
        pos_t -= 1

    if dp[pos_s-1, pos_t-1] != temp:
        res += s[pos_s-1]
        pos_s -= 1
        pos_t -= 1

    # print(res, pos_s-1)
        

print(res[::-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

s = input()
t = input()

num_s = len(s)
num_t = len(t)

dp = np.zeros(num_t + 1, dtype='int64')

res = ""
for i in range(1,num_s):
    if s[i] in t[i:]:
        np.maximum(dp[1:], dp[:-1] + 1, out=dp[1:])
        res += s[i]
    # print(dp)


print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np

s = input()
t = input()

num_s = len(s)
num_t = len(t)

dp = np.zeros(num_t + 1, dtype='int64')

res = ""
for i in range(num_s):
    if s[i] in t[i:]:
        np.maximum(dp[1:], dp[:-1] + 1, out=dp[1:])
        res += s[i]
    # print(dp)


print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np

s = input()
t = input()

num_s = len(s)
num_t = len(t)

dp = np.zeros((num_s + 1, num_t + 1), dtype='int64')

for i in range(num_s):
    for j in range(num_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])
    # print(dp[i])

res = ""
prev=0
for k, num in enumerate(dp[num_s, :]):
    if num > prev and k > 0:
        res += t[k-1]
    prev = num
    # print(res)
print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np

s = input()
t = input()

num_s = len(s)
num_t = len(t)

dp = np.zeros((num_s + 1, num_t + 1), dtype='int64')

for i in range(num_s):
    for j in range(i,num_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])
    # print(dp[i])

res = ""
prev=0
for k, num in enumerate(dp[:,-1]):
    if num > prev and k > 0:
        res += s[k-1]
    prev = num
print(res)

Submission status: Wrong Answer

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

t_len = len(t)
s_len = len(s)

dp = [[0]*(t_len+1) for _ in range(s_len+1)]

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

s_len_tmp = s_len
t_len_tmp = t_len
ans = ''

while s_len_tmp > 0 and t_len_tmp > 0:
    if dp[s_len_tmp][t_len_tmp] == dp[s_len_tmp-1][t_len_tmp-1] + 1:
        ans += s[s_len_tmp-1]
        s_len_tmp -= 1
        t_len_tmp -= 1
    elif dp[s_len_tmp-1][t_len_tmp] > dp[s_len_tmp][t_len_tmp-1]:
        t_len_tmp -= 1
    else:
        s_len_tmp -= 1

print(ans[::-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)):
    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])

ans = ""

i, j = len(s), len(t)
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 = s[i-1] + ans
        i -= 1
        j -= 1

print(ans)
for _dp in dp:
    print(_dp)

Submission status: Wrong Answer

Solution code:
def solve():
    S = input()
    T = input()
    len_t = len(T)
    len_s = len(S)
    dp = [[0] * (len_t+1) for _ in range(len_s+1)]
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            dp[i+1][j+1] = max(dp[i][j]+1 * (s == t),
                               dp[i][j+1],
                               dp[i+1][j])
    print(dp)
    res = ''
    while len_t > 0 and len_s > 0:
        current = dp[len_s][len_t]
        if current == dp[len_s-1][len_t]:
            len_s -= 1
        elif current == dp[len_s][len_t-1]:
            len_t -= 1
        else:
            res = S[len_s-1] + res
            len_s -= 1
            len_t -= 1
    return res


if __name__ == "__main__":
    answer = solve()
    print(answer)

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
#dp[i][j]をs,tをそれぞれ右からi,j番目まで見た時の最大の部分列の長さとする。
lenS = len(S)
lenT = len(T) 
memo = []
dp = [[0]*(lenS+1) for _ in range(lenT+1)]
for i in range(1,lenT+1):
    for j in range(1,lenS+1):
        if S[j-1] == T[i-1]:
            dp[i][j] = max(dp[i-1][j-1]+1,dp[i][j-1],dp[i-1][j])
        else:
            dp[i][j] = max(dp[i][j-1],dp[i-1][j])

print(dp[lenT][lenS])
#dpから最澄列を復元する。
ans = ""
s = lenS
t = lenT
while s>0 and t>0:
    if S[s-1] == T[t-1]:
        ans += S[s-1]
        s -= 1
        t -= 1
    else:
        if dp[t][s-1] > dp[t-1][s]:
            s -= 1
        else:
            t -= 1
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,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 LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

  lns=len(s)
  lnt=len(t)

  dp=[[0 for _ in range(lns+1)]for _ in range(lnt+1)]
  for i in range(lnt):
    for j in range(lns):
      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])

  ans=''
  i=lnt
  j=lns
  while dp[i][j]!=0:
    if dp[i-1][j-1]==dp[i][j]-1:
      ans+=s[j-1]
      i-=1
      j-=1
    else:
      if dp[i-1][j]<dp[i][j-1]:
        j-=1
      else:
        i-=1

  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
s = str(input()).strip()
t = str(input()).strip()

def find_lcs_2(s, t):
    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)
    buffer = ''
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j-1] + 1:
            buffer += s[i-1]
            i, j = i - 1, j - 1
        elif dp[i][j] == dp[i-1][j]:
            i -= 1
        else:
            j -= 1
    return buffer[::-1]
 
print(find_lcs_2(s, t))

Submission status: Wrong Answer

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

def find_lcs_2(s, t):
    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)
    buffer = []
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j-1] + 1:
            buffer.append(s[i - 1])
            i, j = i - 1, j - 1
        elif dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            raise Exception('wtf')
    return ''.join(reversed(buffer))
 
print(find_lcs_2(s, t))