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

lens = len(s)
lent = len(t)

dp = [[None] * lent for _ in range(lens)]
# def dfs(aindex=0, bindex=0):
#     if aindex >= lens:
#         return 0
#     if bindex >= lent:
#         return 0
#
#     if dp[aindex][bindex] is not None:
#         return dp[aindex][bindex]
#
#     if s[aindex] == t[bindex]:
#         r = dfs(aindex + 1, bindex + 1) + 1
#     else:
#         r = max(dfs(aindex + 1, bindex), dfs(aindex, bindex + 1))
#     dp[aindex][bindex] = r
#     return r
#
# print(dfs())

dp = [[0] * (lent + 1) for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            r = dp[aindex + 1][bindex + 1] + 1
        else:
            r = max(dp[aindex + 1][bindex], dp[aindex][bindex + 1])
        dp[aindex][bindex] = r
# for d in dp:
#     print(*d)

prev = dp[0][0]
for bindex, l in enumerate(dp[0]):
    if prev != l:
        print(t[bindex - 1], end="")
        prev = l
print()

Submission status: Wrong Answer

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

lens = len(s)
lent = len(t)

dp = [[None] * lent for _ in range(lens)]
# def dfs(aindex=0, bindex=0):
#     if aindex >= lens:
#         return 0
#     if bindex >= lent:
#         return 0
#
#     if dp[aindex][bindex] is not None:
#         return dp[aindex][bindex]
#
#     if s[aindex] == t[bindex]:
#         r = dfs(aindex + 1, bindex + 1) + 1
#     else:
#         r = max(dfs(aindex + 1, bindex), dfs(aindex, bindex + 1))
#     dp[aindex][bindex] = r
#     return r
#
# print(dfs())

dp = [[0] * (lent + 1) for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            r = dp[aindex + 1][bindex + 1] + 1
        else:
            r = max(dp[aindex + 1][bindex], dp[aindex][bindex + 1])
        dp[aindex][bindex] = r
# for d in dp:
#     print(*d)

prev = dp[0][0]
for bindex, l in enumerate(dp[0]):
    if prev != l:
        print(t[bindex - 1])
        prev = l

Submission status: Wrong Answer

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

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

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

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

n, m = len(s), len(t)
ans = ""
while n != 0 and m != 0:
    if dp[n][m] == dp[n-1][m]:
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    else:
        n -= 1
        m -= 1
        ans = s[n] + ans
print(dp)
print(ans)

Submission status: Wrong Answer

Solution code:
s=input()
l1=len(s)
t=input()
l2=len(t)
arr=[[0]*(l2+1) for _ in range(l1+1)]
for i in range(l1):
  for j in range(l2):
    if s[i]==t[j]:
      arr[i+1][j+1]=1
for i in range(1,l1+1):
  for j in range(1,l2+1):
    if arr[i][j]==1:
      arr[i][j]+=arr[i-1][j-1]
    else:
      arr[i][j]=max(arr[i-1][j],arr[i][j-1])
check=arr[l1][l2]
pos=0
ans=''
for i in range(l1,-1,-1):
  for j in range(l2-pos,-1,-1):
    if j==0:
      continue
    if arr[i][j]==check and arr[i-1][j-1]==check-1:
      ans+=t[j-1]
      pos=l2-j+1
      check-=1
      break
print(ans[::-1])

Submission status: Wrong Answer

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

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

string = ""
cnt = dp[s_len][t_len]

for i in range(s_len + 1):
    print(dp[i])

while t_len > 0 and s_len > 0:
    if dp[s_len][t_len] == dp[s_len - 1][t_len]:
        s_len -= 1
    elif dp[s_len][t_len] == dp[s_len][t_len - 1]:
        t_len -= 1
    else:
        string += s[s_len - 1]
        s_len -= 1
        t_len -= 1


print(string[::-1])

Submission status: Wrong Answer

Solution code:
def main():
    s = input()
    t = input()
    dp = [''] * (len(t) + 1)
    for i in range(1, len(s) + 1):
        ss = s[i - 1]
        for j in range(1, len(t) + 1):
            tt = t[j - 1]
            if ss == tt:
                if len(dp[j - 1]) > len(dp[j] + ss):
                    dp[j] = dp[j - 1] + ss
                else:
                    dp[j] = dp[j] + ss
            else:
                if len(dp[j - 1]) > len(dp[j]):
                    dp[j] = dp[j - 1]
    print(dp[-1])


main()

Submission status: Wrong Answer

Solution code:
def main():
    s = input()
    t = input()
    dp = [[''] * (len(t) + 1) for _ in range(len(s) + 1)]
    for i in range(1, len(s) + 1):
        ss = s[i - 1]
        for j in range(1, len(t) + 1):
            tt = t[j - 1]
            if ss == tt:
                if len(dp[i - 1][j] + ss) >= len(dp[i][j - 1]):
                    dp[i][j] = dp[i - 1][j] + ss
                else:
                    dp[i][j] = dp[i][j - 1] + ss
            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[-1][-1])


main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template

# BEGIN CUT HERE
def lcs(s, t):
    '''s,tは文字列をリスト化したもの'''
    n = len(s)
    m = len(t)
    s.append('$')
    t.append('%')
    dp = [[0 for _j in range(m + 2)] for _i in range(n + 2)]
    dp[0][0] = 0
    for i in range(n+1):
        for j in range(m+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])
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + (s[i] == t[j]))
    # return dp[n][m]
    '''復元する'''
    length = dp[n][m]
    ans = ['']*(length+1)
    while(length > 0):
        if(s[n] == t[m]):
            ans[length] = s[n]
            n-=1
            m-=1
            length-=1
        elif(dp[n][m] == dp[n-1][m]):
            n-=1
        else:
            m-=1
    return ''.join(ans[1:])
# END CUT HERE

def ALDS1_10_C():
    q = ii()
    for _ in range(q):
        s = li()
        t = li()
        print(lcs(s, t))

def EDPC_F():
    s = li()
    t = li()
    print(lcs(s,t))


if __name__ == '__main__':
    # ALDS1_10_C()
    EDPC_F()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template

# BEGIN CUT HERE
def lcs(s, t):
    '''s,tは文字列をリスト化したもの'''
    n = len(s)
    m = len(t)
    s.append('$')
    t.append('%')
    dp = [[0 for _j in range(m + 2)] for _i in range(n + 2)]
    dp[0][0] = 0
    for i in range(n+1):
        for j in range(m+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])
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + (s[i] == t[j]))
    # return dp[n][m]
    '''復元する'''
    length = dp[n][m]
    ans = ['']*(length+1)
    while(length > 0):
        if(s[n] == t[m]):
            ans[length] = s[n];
            n-=1
            m-=1
            length-=1
        elif(dp[n][m] == dp[n - 1][m]):
            n-=1
        else:
            m-=1
    return ''.join(ans)
# END CUT HERE

def ALDS1_10_C():
    q = ii()
    for _ in range(q):
        s = li()
        t = li()
        print(lcs(s, t))

def EDPC_F():
    s = li()
    t = li()
    print(lcs(s,t))


if __name__ == '__main__':
    # ALDS1_10_C()
    EDPC_F()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template

# BEGIN CUT HERE
def lcs(s, t):
    '''s,tは文字列をリスト化したもの'''
    n = len(s)
    m = len(t)
    s.append('$')
    t.append('%')
    dp = [[-(n + m) for _j in range(m + 2)] for _i in range(n + 2)]
    dp[0][0] = 0
    for i in range(n+1):
        for j in range(m+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])
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + (s[i] == t[j]))
    # return dp[n][m]
    '''復元する'''
    length = dp[n][m]
    ans = ['']*(length+1)
    while(length > 0):
        if(s[n] == t[m]):
            ans[length] = s[n];
            n-=1
            m-=1
            length-=1
        elif(dp[n][m] == dp[n - 1][m]):
            n-=1
        else:
            m-=1
    return ''.join(ans)
# END CUT HERE

def ALDS1_10_C():
    q = ii()
    for _ in range(q):
        s = li()
        t = li()
        print(lcs(s, t))

def EDPC_F():
    s = li()
    t = li()
    print(lcs(s,t))


if __name__ == '__main__':
    # ALDS1_10_C()
    EDPC_F()

Submission status: Wrong Answer

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


dp = [[0] * (len(T) + 1) for i in range(len(S) + 1)]
dp2 = [[(-1, -1)] * (len(T) + 1) for i in range(len(S) + 1)]
for i, s in enumerate(S, start=1):
    for j, t in enumerate(T, start=1):
        if s == t:
            dp[i][j] = dp[i - 1][j - 1] + 1
            dp2[i][j] = (i - 1, j - 1)
        elif dp[i - 1][j] > dp[i][j - 1]:
            dp[i][j] = dp[i - 1][j]
            dp2[i][j] = (i - 1, j)
        else:
            dp[i][j] = dp[i][j - 1]
            dp2[i][j] = (i, j - 1)

ans = ''
s, t = len(S), len(T)
while (s > 0) or (t > 0):
    if S[s - 1] == T[t - 1]:
        ans += S[s - 1]
    ns, nt = dp2[s][t]
    s, t = ns, nt

print(ans[::-1])

Submission status: Wrong Answer

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


dp = [[0] * (len(T) + 1) for i in range(len(S) + 1)]
dp2 = [[(0, 0)] * (len(T) + 1) for i in range(len(S) + 1)]
for i, s in enumerate(S, start=1):
    for j, t in enumerate(T, start=1):
        if s == t:
            dp[i][j] = dp[i - 1][j - 1] + 1
            dp2[i][j] = (i - 1, j - 1)
        elif dp[i - 1][j] > dp[i][j - 1]:
            dp[i][j] = dp[i - 1][j]
            dp2[i][j] = (i - 1, j)
        else:
            dp[i][j] = dp[i][j - 1]
            dp2[i][j] = (i, j - 1)

ans = ''
s, t = len(S), len(T)
while (s > 0) or (t > 0):
    if S[s - 1] == T[t - 1]:
        ans += S[s - 1]
    ns, nt = dp2[s][t]
    s, t = ns, nt

print(ans[::-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

def get_inputs():
    S = input()
    T = input()
    return S, T


def dpcalc(S, T):
    #動的計画法のテーブルを用意する　初期値は全て0
    dp = np.zeros((len(T) + 1, len(S) + 1), dtype = int)
    
    for j in range(1, len(T) + 1):
        for i in range(1, len(S) + 1):
            if S[i - 1] == T[j - 1]:
                dp[j][i] = max(dp[j - 1][i - 1] + 1, dp[j - 1][i], dp[j][i - 1])
            else:
                dp[j][i] = max(dp[j - 1][i], dp[j][i - 1])
    
    return dp[len(T)][len(S)]


S, T = get_inputs()
print(dpcalc(S, T))

Submission status: Wrong Answer

Solution code:
def task_E(s, t):
    # form table
    length = [[0]*(len(s)) for x in range(len(t))]
    for i in range(1, len(t)):
        for j in range(1, len(s)):
            if t[i] == s[j]:
                length[i][j] = length[i-1][j-1] + 1
    
    # find max substr
    i_max, j_max, length_max = 0, 0, 0
    for i in range(1, len(t)):
        for j in range(1, len(s)):
            if length[i][j] > length_max:
                length_max = length[i][j]
                i_max, j_max = i, j
    return s[j_max - length_max + 1: j_max + 1]
  
s, t = input(), input()
substr = task_E(s, t)
print(substr)

Submission status: Wrong Answer

Solution code:
def f(s,t):
    sn = len(s)
    tn = len(t)
    dp = [[[]] * (tn + 1) for _ in range(sn + 1)]
    print(dp)
    dpi1 = dp[0]
    for i in range(1, sn + 1):
        dpi = dp[i]
        for j in range(1, tn + 1):
            if s[i - 1] == t[j - 1]:
                dpi[j] = dpi1[j - 1] + [s[i - 1]]
            else:
                if len(dpi1[j]) > len(dpi[j - 1]):
                    dpi[j] = dpi1[j]
                else:
                    dpi[j] = dpi[j - 1]
        dpi1 = dpi
    print(*dp[-1][-1],sep="")

s = input()
t = input()
f(s,t)

Submission status: Wrong Answer

Solution code:
#import numpy as np
a = input()
b = input()
dp = [[0] * (len(b) + 1)  for i in range(len(a) + 1)]

for x in range(len(a)):
	for y in range(len(b)):
		if a[x] == b[y]:
			dp[x + 1][y + 1] = max(dp[x + 1][y + 1], dp[x][y] + 1)
		else:
			dp[x + 1][y] = max(dp[x + 1][y], dp[x][y])
			dp[x][y + 1] = max(dp[x][y + 1], dp[x][y])
		

maxi = -1
pos = (-1 , -1)
for x in range(len(a) + 1):
	for y in range(len(b) + 1):
		if maxi < dp[x][y]:
			maxi = dp[x][y]
			pos = (x, y)

x, y = pos
s = ''
while (x > 0 and y > 0):
	if a[x - 1] == b[y - 1]:
		s = a[x - 1] + s
		x -= 1
		y -= 1
	elif dp[x][y - 1] > dp[x - 1][y]:
		y -= 1
	else:
		x -= 1
		
print(s)

Submission status: Wrong Answer

Solution code:
#import numpy as np
a = input()
b = input()
dp = [[0] * (len(b) + 1)  for i in range(len(a) + 1)]

for x in range(len(a)):
	for y in range(len(b)):
		if a[x] == b[y]:
			dp[x + 1][y + 1] = dp[x][y] + 1
		else:
			dp[x + 1][y + 1] = max(dp[x + 1][y], dp[x][y + 1])
		

maxi = -1
pos = (-1 , -1)
for x in range(len(a) + 1):
	for y in range(len(b) + 1):
		if maxi < dp[x][y]:
			maxi = dp[x][y]
			pos = (x, y)

x, y = pos
s = ''
while (x > 0 and y > 0):
	if (dp[x - 1][y - 1] + 1 == dp[x][y]):
		s = a[x - 1] + s
		x -= 1
		y -= 1
	elif (dp[x - 1][y] == dp[x][y]):
		x -= 1
	elif (dp[x][y - 1] == dp[x][y]):
		y -= 1
		
		
print(s)

Submission status: Wrong Answer

Solution code:
#import numpy as np
a = input()
b = input()
dp = [[0] * (len(b) + 1)  for i in range(len(a) + 1)]

for x in range(len(a)):
	for y in range(len(b)):
		if a[x] == b[y]:
			dp[x + 1][y + 1] = max(dp[x + 1][y + 1], dp[x][y] + 1)
		else:
			dp[x + 1][y] = max(dp[x + 1][y], dp[x][y])
			dp[x][y + 1] = max(dp[x][y + 1], dp[x][y])
		

maxi = -1
pos = (-1 , -1)
for x in range(len(a) + 1):
	for y in range(len(b) + 1):
		if maxi < dp[x][y]:
			maxi = dp[x][y]
			pos = (x, y)

x, y = pos
s = ''
while (x > 0 and y > 0):
	if (dp[x - 1][y - 1] + 1 == dp[x][y]):
		s = a[x - 1] + s
		x -= 1
		y -= 1
	elif (dp[x - 1][y] == dp[x][y]):
		x -= 1
	elif (dp[x][y - 1] == dp[x][y]):
		y -= 1
		
		
print(s)

Submission status: Wrong Answer

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

s = input()
t = input()

lens = len(s)
lent = len(t)

dp = [[{'str': '', 'len': 0} for _ in range(lent+1)] for _ in range(lens+1)]

for i in range(1, lens+1):
    for j in range(1, lent+1):
        if s[i-1] == t[j-1]:
            candidate = max(dp[i-1][j-1]['len']+1, dp[i-1][j]['len'], dp[i][j-1]['len'])
            if candidate == dp[i-1][j-1]['len']+1:
                dp[i][j] = {'str': dp[i-1][j-1]['str'] + s[i-1], 'len': candidate}
                continue
            elif candidate == dp[i-1][j]['len']:
                dp[i][j] = {'str': dp[i-1][j]['str'], 'len': candidate}
                continue
            else:
                dp[i][j] = {'str': dp[i][j-1]['str'], 'len': candidate}
        else:
            candidate = max(dp[i-1][j]['len'], dp[i][j-1]['len'])
            if candidate == dp[i-1][j]['len']:
                dp[i][j] = {'str': dp[i-1][j]['str'], 'len': candidate}
                continue
            else:
                dp[i][j] = {'str': dp[i][j-1]['str'], 'len': candidate}

print(dp[lens][lent]['str'])
for i in range(lens+1):
    print(dp[i])

Submission status: Wrong Answer

Solution code:
s=' '+input()
t=' '+input()
dp=[]
dp_l=[]
for i in range(len(s)):
    sub_list=[]
    l_list=[]
    for j in range(len(t)):
        sub_list.append('')
        l_list.append(0)
    dp.append(sub_list)
    dp_l.append(l_list)
for i in range(1,len(s)):
    for j in range(1,len(t)):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]+s[i]
            dp_l[i][j]=dp_l[i-1][j-1]+1
        else:
            if dp_l[i-1][j]>dp_l[i][j-1]:
                dp[i][j]=dp[i-1][j]
                dp_l[i][j]=dp_l[i-1][j-1]
            else:
                dp[i][j]=dp[i][j-1]
                dp_l[i][j]=dp_l[i-1][j-1]
print(dp[len(s)-1][len(t)-1])

Submission status: Wrong Answer

Solution code:
x = input()
y = input()

lcs = [[''] * (len(y) + 1) for _ in range(len(x) + 1)]
for i_x in range(len(x)):
    for i_y in range(len(y)):
        if x[i_x] == y[i_y]:
            lcs[i_x+1][i_y+1] = lcs[i_x][i_y] + x[i_x]
        elif lcs[i_x+1][i_y] > lcs[i_x][i_y+1]:
            lcs[i_x+1][i_y+1] = lcs[i_x+1][i_y]
        else:
            lcs[i_x+1][i_y+1] = lcs[i_x][i_y+1]

print(lcs[-1][-1])

Submission status: Wrong Answer

Solution code:
sList, tList = map(list, sorted([input(), input()], key=lambda x: len(x)))
 
dp = [[""] * (len(tList) + 1) for _ in range(2)]
index = 0
for i, s in enumerate(sList, start=1):
    index = i % 2
    for j, t in enumerate(tList, start=1):
        sameStr = dp[index-1][j-1] + s if s == t else ""
        dp[index][j] = sameStr if len(sameStr) > len(dp[index-1][j]) else dp[index-1][j]

print(dp[index][-1])

Submission status: Wrong Answer

Solution code:
sList, tList = map(list, sorted([input(), input()], key=lambda x: len(x)))
#sList, tList = map(list, sorted(["sd;fnas;ncnlaubsukefbcasjbdlcbaslidoc;ulabnuebchasvdbcnuayrfivoasdbfkasvludfhwialunejcbasdnbciluahweflicbja",
#                                 "sjdnlifvbasublchawubeyfcainwbidcnbasvebhfcjhbwavendjkcahbsjdbcbasuibefcasjhdvcanwukehfucanbshdbc"], key=lambda x: len(x)))

dp = [[["", 0]] * (len(tList) + 1) for _ in range(2)]
index = 0
for i, s in enumerate(sList, start=1):
    index = i % 2
    sameStr, sameStrLen = "", 0
    for j, t in enumerate(tList, start=1):
        aboveStr, aboveStrLen = dp[index-1][j]
        if s[0] == t[0]:
            sameStr = dp[index - 1][j - 1][0] + s[0]
            sameStrLen = dp[index - 1][j - 1][1] + 1

        if sameStrLen > aboveStrLen:
            dp[index][j] = sameStr, sameStrLen
        else:
            dp[index][j] = aboveStr, aboveStrLen

print(dp[index][-1])

Submission status: Wrong Answer

Solution code:
sList, tList = map(list, sorted([input(), input()], key=lambda x: len(x)))

dp = [[""] * len(tList) for _ in range(2)]
index = 0
for i, s in enumerate(sList):
    index = i % 2
    sameStr = ""
    for j, t in enumerate(tList):
        aboveStr = dp[index-1][j]
        if s == t:
            sameStr = aboveStr + s
        dp[index][j] = sameStr if len(sameStr) >= len(aboveStr) else aboveStr

print(dp[index][-1])

Submission status: Wrong Answer

Solution code:
s, t = sorted([input(), input()], key=lambda x: len(x))
len_s, len_t = len(s), len(t)

dp = [[""] * len_t for _ in range(2)]
index = 0
for i in range(len_s):
    index = i % 2
    sameStr = ""
    for j in range(len_t):
        aboveStr = dp[index-1][j]
        if s[i] == t[j]:
            sameStr = aboveStr + s[i]
        dp[index][j] = sameStr if len(sameStr) >= len(aboveStr) else aboveStr

print(dp[index][-1])

Submission status: Wrong Answer

Solution code:
from heapq import heappush
import functools
S = input()
T = input()
@functools.lru_cache(maxsize=None)
def lcs(s1, s2):
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if not chr_idx:
                break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if chr_idx:
                heappush(dp,chr_idx)
    return dp
print("".join(S[i-1] for i in lcs(S, T)))

Submission status: Wrong Answer

Solution code:
from heapq import heappush
import sys;sys.stdin.readline
import functools
@functools.lru_cache(maxsize=None)
def lcs(s1, s2):
    dp = []
    dp2=""
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if not chr_idx:break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if chr_idx:heappush(dp,chr_idx)
    return dp
S = input()
T = input()
print("".join([S[i-1] for i in lcs(S, T)]))

Submission status: Wrong Answer

Solution code:
from heapq import*
import sys;sys.setrecursionlimit(10**9);sys.stdin.readline
import functools
S = input()
T = input()
@functools.lru_cache(maxsize=None)
def lcs(s1, s2):
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if not chr_idx:
                break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if chr_idx:
                heappush(dp,chr_idx)
    return len(dp)


print(lcs(S, T) + 1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding: utf-8

def rev_enumerate(sequence, start=0):
    n = start
    for elem in sequence:
        yield n, elem
        n -= 1

def main():
    #raw = ["axyb",
    #       "abyxb"]
    #ss, ts = raw
    import sys
    ss = sys.stdin.readline()[:-1]
    ts = sys.stdin.readline()[:-1]
    slen = len(ss)
    tlen = len(ts)
    dp = [[0] * (tlen + 1) for _ in range(slen + 1)]
    for i, s in rev_enumerate(ss, slen - 1):
        for j, t in rev_enumerate(ts, tlen - 1):
            if s == t:
                dp[i][j] = max(dp[i+1][j], dp[i][j+1], dp[i+1][j+1] + 1)
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j+1])
    i, j = 0, 0
    ans = ""
    #print(dp)
    while i < slen and j < tlen:
        if dp[i][j] == dp[i+1][j]:
            i += 1
        elif dp[i][j] == dp[i][j+1]:
            j += 1
        else:
            ans += ss[i]
            i += 1
            j += 1
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding: utf-8

def rev_enumerate(sequence, start=0):
    n = start
    for elem in sequence:
        yield n, elem
        n -= 1

def main():
    #raw = ["axyb",
    #       "abyxb"]
    #ss, ts = raw
    import sys
    ss = sys.stdin.readline()[:-1]
    ts = sys.stdin.readline()[:-1]
    slen = len(ss)
    tlen = len(ts)
    dp = [[0] * (tlen + 1) for _ in range(slen + 1)]
    for i, s in rev_enumerate(ss, slen - 1):
        for j, t in rev_enumerate(ts, tlen - 1):
            if s == t:
                dp[i][j] = max(dp[i+1][j], dp[i][j+1], dp[i+1][j+1] + 1)
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j+1])
    i, j = 0, 0
    ans = ""
    print(dp)
    while i < slen and j < tlen:
        if dp[i][j] == dp[i+1][j]:
            i += 1
        elif dp[i][j] == dp[i][j+1]:
            j += 1
        else:
            ans += ss[i]
            i += 1
            j += 1
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
if __name__=="__main__":
    s = input()
    len_s = len(s)
    t = input()
    len_t = len(t)
    f = [[0 for i in range(len_t + 1)] for i in range(len_s + 1)]
    back = [[[0, 0] for i in range(len_t + 1)] for i in range(len_s + 1)]
    for i in range(len_s):
        for j in range(len_t):
            if f[i + 1][j] <= f[i][j]:
                back[i + 1][j] = i, j
                f[i + 1][j] = f[i][j]
            if f[i][j + 1] <= f[i][j]:
                back[i][j + 1] = i, j
                f[i][j + 1] = f[i][j]
            if f[i + 1][j + 1] <= f[i][j]:
                back[i + 1][j + 1] = i, j
                f[i + 1][j + 1] = f[i][j]
            if (s[i] == t[j] and f[i + 1][j + 1] <= f[i][j] + 1):
                back[i + 1][j + 1] = i, j
                f[i + 1][j + 1] = f[i][j] + 1
    ans = ''
    x = len_s
    y = len_t
    while x > 0 or y > 0:
        if (back[x][y][0] != x and back[x][y][1] != y and s[back[x][y][0]] == t[back[x][y][1]]):
            ans = ans + s[back[x][y][0]]
        x, y = back[x][y]
    ans = ans[-1::-1]
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

s = input()
t = input()

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

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

ansl = []
cnt = dp[-1][-1]
def tami(i,j):
  global cnt
  if cnt == 0:
    return
  if s[i-1] == t[j-1]:
    cnt -= 1
    ansl.append(i-1)
  if dp[i-1][j-1]==cnt:
    tami(i-1,j-1)
  elif dp[i][j-1]==cnt:
    tami(i,j-1)

tami(len(s),len(t))

ans = ""
for i in ansl:
  ans += s[i]
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

s = input()
t = input()

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

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

ansl = []
cnt = dp[-1][-1]
def tami(i,j):
  global cnt
  if cnt == 0:
    return
  if s[i-1] == t[j-1]:
    cnt -= 1
    ansl.append(i-1)
  if dp[i-1][j-1]==cnt:
    tami(i-1,j-1)
  if dp[i][j-1]==cnt:
    tami(i,j-1)

tami(len(s),len(t))

ans = ""
for i in ansl:
  ans += s[i]
print(ans[::-1])

Submission status: Wrong Answer

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

ls,lt = len(s),len(t)
dp = [[(0,"")]*(lt+1) for _ in [0]*(ls+1)]
for i,cs in enumerate(s,1):
    for j,ct in enumerate(t,1):
        tmp_i1 = dp[i-1][j]
        tmp_j1 = dp[i][j-1]
        tmp_i1_0 = tmp_i1[0]
        if cs == ct:
            dp[i][j] = (tmp_i1_0+1,tmp_i1[1]+cs)
        elif tmp_i1_0 >= tmp_j1[0]:
            dp[i][j] = tmp_i1
        else:
            dp[i][j] = tmp_j1
print(dp[-1][-1][1])

Submission status: Wrong Answer

Solution code:
a=input()
b=input()

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

max_len = dp[-1][-1]
#print(max_len)

prev = max_len

ans = ""

i = ls
j = lt

for l in range(max_len):
    while dp[i-1][j] == max_len - l:
        i -= 1
    while dp[i][j-1] == max_len - l:
        j -= 1
    ans += s[i-1]
print(ans[::-1])

Submission status: Wrong Answer

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

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

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

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

max_len = dp[-1][-1]
#print(max_len)

prev = max_len

ans = ""

i = ls
j = lt

for l in range(max_len):
    while dp[i-1][j] == max_len - l:
        i -= 1
    while dp[i][j-1] == max_len - l:
        j -= 1
    ans += s[i-1]
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
s = input()
s = [ord(i) - 97 for i in s]
t = input()
t = [ord(i) -97 for i in t]

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

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

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

max_len = dp[-1][-1]
ans = []

i = ls
j = lt

for l in range(max_len):
    while dp[i-1][j] == max_len - l:
        i -= 1
    while dp[i][j-1] == max_len - l:
        j -= 1
    ans.append(s[i-1])

alphabet = [chr(97+i) for i in range(27)]
a = ""
for i in ans:
    a += alphabet[i]
print(a[::-1])

Submission status: Wrong Answer

Solution code:
s=list(input())
t=list(input())
dp=[[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j+1])
        dp[i][j+1]=max(dp[i][j],dp[i][j+1])
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])
ans=[]
i=len(s)
j=len(t)
while(i>0 and j>0):
    if dp[i][j]==dp[i-1][j]:
        i-=1
        continue
    if dp[i][j]==dp[i][j-1]:
        j-=1
        continue
    ans.append(s[i-1])
    i-=1
    j-=1
print("".join(ans[::-1]))

Submission status: Wrong Answer

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

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+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 = n
j = m
ans = ''
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
        continue
    if dp[i][j] == dp[i][j-1]:
        j -= 1
        continue
    i -= 1
    j -= 1
    ans += s[i]

print(ans[::-1])