Problem:


Score : 100 points

Problem Statement

You are given strings s and t.
Find one longest string that is a subsequence of both s and t.

Notes

A subsequence of a string x is the string obtained by removing zero or more characters from x and concatenating the remaining characters without changing the order.

Constraints

s and t are strings consisting of lowercase English letters.

1 \leq |s|, |t| \leq 3000

Input

Input is given from Standard Input in the following format:

s
t

Output

Print one longest string that is a subsequence of both s and t.
If there are multiple such strings, any of them will be accepted.

Sample Input 1

axyb
abyxb

Sample Output 1

axb

The answer is axb or ayb; either will be accepted.

Sample Input 2

aa
xayaz

Sample Output 2

aa

Sample Input 3

a
z

Sample Output 3

The answer is  (an empty string).

Sample Input 4

abracadabra
avadakedavra

Sample Output 4

aaadara



Sample input:
axyb
abyxb


Sample output:
axb

Submission status: Wrong Answer

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

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

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

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i+1][j+1] = 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])

i = n
j = m
ans = ''
while i > 0 or j > 0:
    if i > 0 and dp[i][j] == dp[i-1][j]:
        i -= 1
        continue
    if j > 0 and dp[i][j] == dp[i][j-1]:
        j -= 1
        continue
    i -= 1
    j -= 1
    ans += s[i]

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

Submission status: Wrong Answer

Solution code:
import sys

def lcs_count(A,B):
    dp = [[0]*(l2+1) for _ in range(l1+1)]
    for i in range(1,l1+1):
        for j in range(1,l2+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    return dp

def lcs_string(dp):
    string = []
    for i,j in zip([m for m in range(l1,0,-1)],[n for n in range(l2,0,-1)]):
        if dp[i][j] > dp[i-1][j-1]:
            string.insert(0,chr(s[i-1]+97))
    print("".join(string))

s = [ord(a)-97 for a in list(sys.stdin.readline().rstrip())]
t = [ord(b)-97 for b in list(sys.stdin.readline().rstrip())]
l1 = len(s)
l2 = len(t)

DP = lcs_count(s,t)
lcs_string(DP)

Submission status: Wrong Answer

Solution code:
import sys

def lcs_count(A,B):
    # initial value setting
    dp = [[0]*(l2+1)]*(l1+1)
    # create table
    for i in range(1,l1+1):
        for j in range(1,l2+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    return dp

def lcs_string(dp):
    string = []
    for i,j in zip([m for m in range(l1,0,-1)],[n for n in range(l2,0,-1)]):
        if dp[i][j] > dp[i-1][j-1]:
            string.insert(0,chr(s[i-1]+97))
    print("".join(string))

s = [ord(a)-97 for a in list(sys.stdin.readline().rstrip())]
t = [ord(b)-97 for b in list(sys.stdin.readline().rstrip())]
l1 = len(s)
l2 = len(t)

DP = lcs_count(s,t)
lcs_string(DP)

Submission status: Wrong Answer

Solution code:

s = input()
t = input()

sl = len(s)+1
tl = len(t)+1

tab = [ [0]*sl for _ in range(tl)]

for i in range(1,sl):

    si = s[i-1]

    for j in range(1,tl):
        ti = t[j-1]

        if si == ti:
            tab[j][i] = tab[j-1][i-1] + 1
        else:
            tab[j][i] = max(tab[j-1][i], tab[j][i-1])


# for li in tab:
#   print(li)

ans = ''
for i, e in enumerate(tab[-1][1:]):
    if len(ans)<e:
        ans += s[i]

print(ans)

Submission status: Wrong Answer

Solution code:

s = input()
t = input()

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


# print(tab[1])

for i in range(1,len(s)+1):

    si = s[i-1]

    for j in range(1,len(t)+1):
        ti = t[j-1]

        if si == ti:
            tab[j][i] = tab[j-1][i-1] + 1
        else:
            tab[j][i] = max(tab[j-1][i], tab[j][i-1])


# for li in tab:
#   print(li)

ans = ''
for i, e in enumerate(tab[-1][1:]):
    if len(ans)<e:
        ans += s[i]

print(ans)

Submission status: Wrong Answer

Solution code:

s = input()
t = input()

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


# print(tab[1])

for i in range(1,len(s)+1):

    si = s[i-1]

    for j in range(1,len(t)+1):
        ti = t[j-1]

        if si == ti:
            tab[j][i] = tab[j-1][i-1] + 1
        else:
            tab[j][i] = max(tab[j-1][i], tab[j][i-1])


#for li in tab:
#    print(li)

ans = ''
for i, e in enumerate(tab[-1]):
    if len(ans)<e:
        ans += s[i-1]

print(ans)

Submission status: Wrong Answer

Solution code:
# s = input()
# t= input()
s = "abracadabra"
t = "avadakedavra"

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

while i>0 and j>0:
#     print("現在精査している文字は{}と{}です。もとのsは{}で、tは{}です。sの長さは{}, tの長さは{}です".format(s[i-1],t[j-1],s[:i-1], t[:j-1], i,j))
    if s[i-1] == t[j-1]:
        ans += s[i-1]
        i -= 1
        j -= 1
#         print("一致")
    elif dp[i][j-1] > dp[i-1][j]:
        j -= 1
    else:
        i -= 1
        
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
# s = input()
# t= input()
s = "abracadabra"
t = "avadakedavra"

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

while i>0 and j>0:
#     print("現在精査している文字は{}と{}です。もとのsは{}で、tは{}です。sの長さは{}, tの長さは{}です".format(s[i-1],t[j-1],s[:i-1], t[:j-1], i,j))
    if s[i-1] == t[j-1]:
        ans += s[i-1]
        i -= 1
        j -= 1
#         print("一致")
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1
        
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
# s = input()
# t= input()
s = "abracadabra"
t = "avadakedavra"

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

while i>0 and j>0:
#     print("現在精査している文字は{}と{}です。もとのsは{}で、tは{}です。sの長さは{}, tの長さは{}です".format(s[i-1],t[j-1],s[:i-1], t[:j-1], i,j))
    if s[i-1] == t[j-1]:
        ans += s[i-1]
        i -= 1
        j -= 1
        dp_len -= 1
#         print("一致")
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1
        
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    """
    N個の足場があります。足場には1,2,…,Nと番号が振られています。 
    各i (1≤i≤N) について、足場 i の高さは hi です。
    最初、足場 1 にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。
    足場 i にいるとき、足場 i+1 または i+2 へジャンプする。
    このとき、ジャンプ先の足場を j とすると、コスト |hi−hj| を支払う。
    カエルが足場 N に辿り着くまでに支払うコストの総和の最小値を求めてください。

    制約
        入力はすべて整数である。
    2≤N≤10**5
    1≤hi≤10**4
    """
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]))
    print(dp[n-1])
    return

#B
def B():
    n, K = LI()
    h = LI()
    dp = [float("INF") for i in range(n + K + 1)]
    dp[0] = 0
    for i in range(n):
        for k in range(1, K + 1):
            if i + k >= n:
                break
            dp[i + k] = min(dp[i + k], dp[i] + abs(h[i] - h[i + k]))
    print(dp[n-1])
    return

#C
def C():
    n = II()
    abc = LIR(n)
    dp = [0 for i in range(3 * n + 1)]
    dp[0] = abc[0][0]
    dp[1] = abc[0][1]
    dp[2] = abc[0][2]
    for i in range(1,n):
        dp[3 * i] = max(dp[3 * i], dp[3 * (i - 1) + 1] + abc[i][0], dp[3 * (i - 1) + 2] + abc[i][0])
        dp[3 * i + 1] = max(dp[3 * i + 1], dp[3 * (i - 1) + 2] + abc[i][1], dp[3 * (i - 1)] + abc[i][1])
        dp[3 * i + 2] = max(dp[3 * i + 2], dp[3 * (i - 1) + 1] + abc[i][2], dp[3 * (i - 1)] + abc[i][2])
    dp[3 * n] = max(dp)
    print(dp[3*n])

    return

#D
def D():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**5
    1≤wi≤W
    1≤vi≤10**9"""
    n, w = LI()
    wv = LIR(n)
    dp = [[0 for k in range(w + 1)] for i in range(n + 2)]
    for i in range(1,n + 1):
        for j in range(w + 1):
            if j < wv[i-1][0]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i - 1][0]] + wv[i - 1][1])
    print(dp[n+1][w])

    
    return

#E
def E():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**9
    1≤wi≤W
    1≤vi≤10**3"""
    n, w = LI()
    wv = LIR(n)
    dp = [[float("INF") for i in range(10 ** 5 + 1)] for k in range(n + 1)]
    dp[0][0] = 0
    for i in range(n):
        for k in range(10 ** 5 + 1):
            if k < wv[i][1]:
                dp[i + 1][k] = dp[i][k]
            else:
                dp[i + 1][k] = min(dp[i][k], dp[i][k - wv[i][1]] + wv[i][0])
    ans = 0
    for i in range(10 ** 5 + 1):
        if dp[n][i] <= w:
            ans = i
    print(ans)

    return

#F
def F():
    s = S()
    t = S()
    dp = [[0 for i in range(len(t)+1)] for k 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:
                if dp[i][j + 1] < dp[i + 1][j]:
                    dp[i + 1][j + 1] = dp[i + 1][j]
                else:
                    dp[i + 1][j + 1] = dp[i][j + 1]
    ss = len(s)
    tt = len(t)
    ans = ""
    si = ss
    ti = tt
    while si > 0 and ti > 0:
        if dp[si][ti] == dp[si - 1][ti]:
            si -= 1
        elif dp[si][ti] == dp[si][ti - 1]:
            ti -= 1
        else:
            si -= 1
            ti -= 1
            ans = s[i]+ans


    print(ans)
    return

#G
def G():
    n, m = LI()
    xy = LIR_(m)
    edge = [[] for i in range(n)]
    for x,y in xy:
        edge[x].append(y)
    dp = [0 for i in range(n)]
    def ans(dp, i):
        #print(dp, i)
        if dp[i] != 0:
            return dp[i]
        else:
            if len(edge[i]) == 0:
                return 0
            ansb = 0
            for k in edge[i]:
                #print(dp, k , i)
                ansb = max(ansb, ans(dp, k) + 1)
                dp[i] = max(ansb, dp[i])
                #print(dp)
            return ansb
            
    for i in range(n):
        dp[i] = ans(dp, i)
    print(max(dp))
    return

#H
def H():
    h, w = LI()
    a = SR(h)
    dp = [[0 for i in range(w)] for k in range(h)]
    for i in range(w):
        if a[0][i] == "#":
            break
        dp[0][i] = 1
    for i in range(h):
        if a[i][0] == "#":
            break
        dp[i][0] = 1
    for i in range(1,w):
        for k in range(1, h):
            #print(i,k, dp)
            if a[k - 1][i] == ".":
                if a[k][i - 1] == ".":
                    dp[k][i] = dp[k - 1][i] + dp[k][i - 1] % mod
                else:
                    dp[k][i] = dp[k - 1][i]
            else:
                if a[k][i - 1] == ".":
                    dp[k][i] = dp[k][i - 1]
    print(dp[h-1][w-1] % mod)

    return

#I
def I():
    n = II()
    p = LF()
    dp = [[0 for k in range(n+1)] for i in range(n+1)]
    dp[1][1] = p[0]
    dp[1][0] = 1-p[0]
    for i in range(2,n+1):
        for k in range(i + 1):
            if k == 0:
                
                dp[i][k] = dp[i-1][k] * (1 - p[i-1])
            else:
                dp[i][k] = dp[i - 1][k - 1] * p[i - 1] + dp[i - 1][k] * (1 - p[i - 1])
    #print(dp)
    print(sum(dp[n][n//2+1:]))
    return 
#J
def J():
    n = II()
    a = LI()


#K


#L

#M
#N
# O
# P
# Q
# R
# S
# T
# U
# V
# W
# X
# Y
# Z


#Solve
if __name__ == '__main__':
    F()

Submission status: Wrong Answer

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
#
# 蟻本のdp回に出てくる！
#
import sys

s = str(input())
t = str(input())
dp = ["" for j in range(len(t)+1)]

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

print(dp[-1])

Submission status: Wrong Answer

Solution code:
s1=input()
s2=input()
dp=[0]*(len(s1)+1)
dp[0]=[0]*(len(s2)+1)
for i in range(1,len(s1)+1):
	dp[i]=[0]*(len(s2)+1)
	for j in range(1,len(s2)+1):
		if s1[i-1]==s2[j-1]:
			dp[i][j]=dp[i-1][j-1]+1
		else:
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])
for i in range(len(s1)+1):
	print(dp[i])
s=""
i,j=len(s1),len(s2)
while(i>0 and j>0):
	if s1[i-1]==s2[j-1]:
		s+=s1[i-1]
		i-=1
		j-=1
	elif dp[i][j-1]>dp[i-1][j]:
		j-=1
	else:
		i-=1
print(s[::-1])

Submission status: Wrong Answer

Solution code:
s = list(input())
t = list(input())
n = len(s)
m = len(t)

dp = [['']*m for i in range(n)]
if s[0] == t[0]:
    dp[0][0] = s[0]

for i in range(1,m):
    if s[0] == t[i]:
        dp[0][i] = s[0]
    else:
        dp[0][i] = dp[0][i-1]
for i in range(1,n):
    if t[0] == s[i]:
        dp[i][0] = t[0]
    else:
        dp[i][0] = dp[i-1][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:
            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('a')

Submission status: Wrong Answer

Solution code:
s = raw_input()
t = raw_input()
ls = len(s)
lt = len(t)
dp = [[0]*(lt+1) for i in range(ls+1)]
dpp = [[None]*(lt+1) for i in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1], dp[i][j]+(1 if s[i]==t[j] else 0))
    if dp[i+1][j+1]==dp[i+1][j]:
      dpp[i+1][j+1]=(i+1,j)
    elif dp[i+1][j+1]==dp[i][j+1]:
      dpp[i+1][j+1]=(i,j+1)
    else:
      dpp[i+1][j+1]=(i,j)
r = []
i = ls
j = lt
while dpp[i][j] is not None:
  if s[i-1]==t[j-1]:
    r.append(s[i-1])
  i,j = dpp[i][j]
print("".join(r[::-1]))

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    # dp[i][j] = LCS(s[:i+1],t[:j+1])
    sLen, tLen = len(s),len(t),
    dp = [ [( 0 , -1 )]*(tLen+1)  for _ in range(sLen+1) ]
    for i in range(1,sLen+1):
        for j in range(1,tLen+1):
            comp = [ dp[i][j-1][0],dp[i-1][j-1][0]+int(s[i-1]==t[j-1]),dp[i-1][j][0]]
            argmax = comp.index(max(comp))
            dp[i][j] = ( comp[argmax] , argmax )

    ans = ""
    i,j = sLen, tLen
    for _ in range(sLen+tLen):
        if dp[i][j][1] == 0:
            j -= 1
        elif dp[i][j][1] == 1:
            ans += s[i-1]
            i -= 1
            j -= 1
        elif dp[i][j][1] == 2:
            i -= 1
        else:
            break
    return reversed(ans)

if __name__ == '__main__':
    s = sys.stdin.readline()
    t = sys.stdin.readline()
    print(solve())

Submission status: Wrong Answer

Solution code:
def trace(i,j):
    global ans
    if dp[i][j][1] == 0:
        trace(i,j-1)
    elif dp[i][j][1] == 1:
        ans += s[i-1]
        trace(i-1,j-1)
    elif dp[i][j][1] == 2:
        trace(i-1,j)
    else:
        return

s = input()
t = input()
# dp[i][j] = LCS(s[:i+1],t[:j+1])
dp = [ [( 0 , -1 )]*(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):
        comp = [ dp[i][j-1][0],dp[i-1][j-1][0]+int(s[i-1]==t[j-1]),dp[i-1][j][0]]
        argmax = comp.index(max(comp))
        dp[i][j] = ( comp[argmax] , argmax )

ans = ""
#trace(len(s),len(t))
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/6
Update on 2019/3/6
Solved on 2019/3/
@author: shinjisu
"""


# Educational Dynamic Programming
# import math
import numpy as np


def getInt(): return int(input())


# def getIntList(): return [int(x) for x in input().split()]
def getIntList(): return np.array(input().split(), dtype=np.longlong)


# def zeros(n): return [0]*n
def zeros(n): return np.zeros(n, dtype=np.longlong)


# def getIntLines(n): return [int(input()) for i in range(n)]
def getIntLines(n):
    data = zeros(n)
    for i in range(n):
        data[i] = getInt()
    return data


def getIntMat(n, m):  # n行に渡って、1行にm個の整数
    mat = zeros((n, m))
    for i in range(n):
        mat[i] = getIntList()
    return mat


# def zeros2(n, m): return [zeros(m)]*n # obsoleted zeros((n, m))で代替


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**18


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def lcsLen(S, T, n, m):
    if n == -1 or m == -1:
        return 0
    elif S[n] == T[m]:
        return lcsLen(S, T, n-1, m-1)+1
    else:
        return max(lcsLen(S, T, n-1, m), lcsLen(S, T, n, m-1))


def lcs(S, T, n, m):
    if n == -1 or m == -1:
        return 0, ''
    elif S[n] == T[m]:
        lcstr = lcs(S, T, n-1, m-1)
        return lcstr[0]+1, lcstr[1]+S[n]
    else:
        lcstr1 = lcs(S, T, n-1, m)
        lcstr2 = lcs(S, T, n, m-1)
        if lcstr1[0] > lcstr2[0]:
            lcstr = lcstr1
        else:
            lcstr = lcstr2
        return lcstr


def prob_F_recur():  # LCS - Longest Common Subsequence
    S = input()
    T = input()
    dmp((S, T), 'S, T')
    lenS, lenT = len(S), len(T)
    dmp((lenS, lenT), '(lenS, lenT)')
    lcstr = lcs(S, T, lenS-1, lenT-1)
    dmp(lcstr, 'lcs')
    return lcstr[1]


def prob_F_TLE():  # LCS - Longest Common Subsequence  12/18 TLE
    S = input()
    T = input()
    dmp((S, T), 'S, T')
    lenS, lenT = len(S), len(T)
    dmp((lenS, lenT), '(lenS, lenT)')
    dp = [[[0, ''] for j in range(lenT+1)] for i in range(lenS+1)]
    dmp(dp)
    for i in range(lenS+1):
        for j in range(lenT+1):
            if i == 0 or j == 0:
                pass
            elif S[i-1] == T[j-1]:
                lcstr = dp[i-1][j-1]
                dp[i][j] = lcstr[0]+1, lcstr[1]+S[i-1]
            else:
                lcstr1 = dp[i-1][j]
                lcstr2 = dp[i][j-1]
                if lcstr1[0] > lcstr2[0]:
                    dp[i][j] = lcstr1
                else:
                    dp[i][j] = lcstr2
    dmp(dp)
    lcstr = dp[lenS][lenT]
    dmp(lcstr)
    return lcstr[1]


def lcs_rec2(S, T, n, m, dp):
    if n == 0 or m == 0:
        return ''
    elif S[n-1] == T[m-1]:
        return lcs(S, T, n-1, m-1, dp)+S[n-1]
    elif dp[n-1][m] > dp[n][m-1]:
        return lcs(S, T, n-1, m, dp)
    else:
        return lcs(S, T, n, m-1, dp)


def lcs(S, T, n, m, dp):
    lcstr = ''
    while True:
        if n == 0 or m == 0:
            return lcstr
        elif S[n-1] == T[m-1]:
            lcstr += S[n-1]
            n -= 1
            m -= 1
        elif dp[n-1][m] > dp[n][m-1]:
            n -= 1
        else:
            m -= 1


def prob_F():  # LCS - Longest Common Subsequence
    S = input()
    T = input()
    dmp((S, T), 'S, T')
    lenS, lenT = len(S), len(T)
    dmp((lenS, lenT), '(lenS, lenT)')
#    dp = [[0 for j in range(lenT+1)] for i in range(lenS+1)]
    dp = zeros((lenS+1, lenT+1))
    dmp(dp)
    for i in range(lenS+1):
        for j in range(lenT+1):
            if i == 0 or j == 0:
                pass
            elif 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])
    dmp(dp)
    return dmp(lcs(S, T, lenS, lenT, dp))


debug = False  # True False
ans = prob_F()
print(ans)
#for row in ans:
#    print(row)

Submission status: Wrong Answer

Solution code:
from __future__ import division
import collections

import six

def _ngrams(words, n):
    queue = collections.deque(maxlen=n)
    for w in words:
        queue.append(w)
        if len(queue) == n:
            yield tuple(queue)

def _ngram_counts(words, n):
    return collections.Counter(_ngrams(words, n))

def _ngram_count(words, n):
    return max(len(words) - n + 1, 0)

def _counter_overlap(counter1, counter2):
    result = 0
    for k, v in six.iteritems(counter1):
        result += min(v, counter2[k])
    return result

def _safe_divide(numerator, denominator):
    if denominator > 0:
        return numerator / denominator
    else:
        return 0

def _safe_f1(matches, recall_total, precision_total, alpha):
    recall_score = _safe_divide(matches, recall_total)
    precision_score = _safe_divide(matches, precision_total)
    denom = (1.0 - alpha) * precision_score + alpha * recall_score
    if denom > 0.0:
        return (precision_score * recall_score) / denom
    else:
        return 0.0

def rouge_n(peer, models, n, alpha):
    """
    Compute the ROUGE-N score of a peer with respect to one or more models, for
    a given value of `n`.
    """
    matches = 0
    recall_total = 0
    peer_counter = _ngram_counts(peer, n)
    for model in models:
        model_counter = _ngram_counts(model, n)
        matches += _counter_overlap(peer_counter, model_counter)
        recall_total += _ngram_count(model, n)
    precision_total = len(models) * _ngram_count(peer, n)
    return _safe_f1(matches, recall_total, precision_total, alpha)

def rouge_1(peer, models, alpha):
    """
    Compute the ROUGE-1 (unigram) score of a peer with respect to one or more
    models.
    """
    return rouge_n(peer, models, 1, alpha)

def rouge_2(peer, models, alpha):
    """
    Compute the ROUGE-2 (bigram) score of a peer with respect to one or more
    models.
    """
    return rouge_n(peer, models, 2, alpha)

def rouge_3(peer, models, alpha):
    """
    Compute the ROUGE-3 (trigram) score of a peer with respect to one or more
    models.
    """
    return rouge_n(peer, models, 3, alpha)

def lcs(a, b):
    """
    Compute the length of the longest common subsequence between two sequences.
    Time complexity: O(len(a) * len(b))
    Space complexity: O(min(len(a), len(b)))
    """
    # This is an adaptation of the standard LCS dynamic programming algorithm
    # tweaked for lower memory consumption.
    # Sequence a is laid out along the rows, b along the columns.
    # Minimize number of columns to minimize required memory
    if len(a) < len(b):
        a, b = b, a
    # Sequence b now has the minimum length
    # Quit early if one sequence is empty
    if len(b) == 0:
        return 0
    # Use a single buffer to store the counts for the current row, and
    # overwrite it on each pass
    row = [0] * len(b)
    k=""
    for ai in a:
        left = 0
        diag = 0
        for j, bj in enumerate(b):
            up = row[j]
            if ai == bj:
                value = diag + 1
                k+=ai
            else:
                value = max(left, up)
            row[j] = value
            left = value
            diag = up
    # Return the last cell of the last row
    return k

def rouge_l(peer, models, alpha):
    """
    Compute the ROUGE-L score of a peer with respect to one or more models.
    """
    matches = 0
    recall_total = 0
    for model in models:
        matches += lcs(model, peer)
        recall_total += len(model)
    precision_total = len(models) * len(peer)
    return _safe_f1(matches, recall_total, precision_total, alpha)

    a = input()
    b = input()
    print(lcs(a,b))

Submission status: Wrong Answer

Solution code:
def solve(s, t):
    # 1-origin
    s_size, t_size = len(s), len(t)
    dp = [[0] * (t_size + 1) for _ in range(s_size + 1)]

    for i in range(1, s_size + 1):
        for j in range(1, t_size + 1):
            prev_i, prev_j = i - 1, j - 1
            dp[i][j] = max(dp[prev_i][j], dp[i][prev_j])
            if s[prev_i] != t[prev_j]:
                # 不一致
                continue
            if dp[prev_i][prev_j] + 1 <= dp[i][j]:
                # maxを超えないとき
                continue
            dp[i][j] = dp[prev_i][prev_j] + 1

    # 文字復元
    buff = []
    min_length = 0
    for key in range(t_size + 1):
        if min_length < dp[s_size][key]:
            min_length = dp[s_size][key]
            buff.append(t[key - 1])
    return "".join(buff)


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

    ans = solve(s, t)
    print(ans)


main()

Submission status: Wrong Answer

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

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

INF = float('inf')
dp = [[-INF] * (len_t+1) for _ in range(len_s+1)]

dp[0][0] = 0

for i in range(len_s):
    for j in range(len_t):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

i = len_s
j = len_t
res = ""
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:
        res += s[i-1]
        i -= 1
        j -= 1

print(res[::-1])

Submission status: Wrong Answer

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

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

INF = float('inf')
dp = [[-INF] * (len_t+1) for _ in range(len_s+1)]

dp[0][0] = 1

for i in range(len_s):
    for j in range(len_t):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

i = len_s
j = len_t
res = ""
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:
        res += s[i-1]
        i -= 1
        j -= 1

print(res[::-1])

Submission status: Wrong Answer

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

len_s = len(s)
len_t = len(t)
INF = float('inf')

dp = [[0] * (len_t+1) for _ in range(len_s+1)]

dp[0][0] = 0

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

i = len_s
j = len_t
ans = ""
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j-1] + 1:
        ans += s[i-1]
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1

print(ans[::-1])

Submission status: Wrong Answer

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

len_s = len(s)
len_t = len(t)
INF = float('inf')

dp = [[0] * (len_t+1) for _ in range(len_s+1)]

dp[0][0] = 0

for i in range(len_s+1):
    for j in range(len_t+1):
        if i+1 <= len_s and j <= len_t:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if i <= len_s and j+1 <= len_t:
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])
        if i+1 <= len_s and j+1 <= len_t and s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)

i = len_s
j = len_t
ans = ""
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j-1] + 1:
        ans += s[i-1]
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1

print(ans[::-1])

Submission status: Wrong Answer

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

len_s = len(s)
len_t = len(t)
INF = float('inf')

dp = [[-INF] * (len_t+1) for _ in range(len_s+1)]

dp[0][0] = 0

for i in range(len_s+1):
    for j in range(len_t+1):
        if i+1 <= len_s and j <= len_t:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if i <= len_s and j+1 <= len_t:
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])
        if i+1 <= len_s and j+1 <= len_t and s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)

i = len_s
j = len_t
ans = ""
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j-1] + 1:
        ans += s[i-1]
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1

print(ans[::-1])

Submission status: Wrong Answer

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

len_s = len(s)
len_t = len(t)
INF = float('inf')

dp = [[-INF] * (len_t+1) for _ in range(len_s+1)]

dp[0][0] = 0

for i in range(len_s+1):
    for j in range(len_t+1):
        if i+1 <= len_s and j+1 <= len_t and s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        if i+1 <= len_s and j <= len_t:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if i <= len_s and j+1 <= len_t:
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])

i = len_s
j = len_t
ans = ""
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j-1] + 1:
        ans += s[i-1]
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1

print(ans[::-1])

Submission status: Wrong Answer

Solution code:
class Solution(object):
    def lcs(self, a, b):
        dp = [[[0,[]] for _ in range(len(b)+1)] for _ in range(len(a)+1)]
        # print(dp[0][0][0], dp[0][0][1])

        for i in range(len(a)):
            curr_a = a[i]
            for j in range(len(b)):
                curr_b = b[j]
                if curr_a == curr_b:
                    dp[i+1][j+1][0] = dp[i][j][0]+1
                    dp[i+1][j+1][1] =  dp[i][j][1] + [curr_a]
                else:
                    dp[i+1][j+1][0] = max(dp[i][j+1][0], dp[i+1][j][0])
                    if dp[i][j+1][0] > dp[i+1][j][0]:
                        dp[i+1][j+1][1] += dp[i][j+1][1]
                    else:
                        dp[i+1][j+1][1] += dp[i+1][j][1]

        print("".join(dp[-1][-1][1]))










if __name__ == '__main__':
    a = str(input())
    b = str(input())
    sol = Solution()
    res = sol.lcs(a, b)
    print(res)