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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import deque
s1=input()
s2=input()
n=len(s1)
m=len(s2)
dp=[[0]*(m) for i in range(n)]
for i in range(n):
    for j in range(m):
        if(i==0 or j==0):
            if(s1[i]==s2[j]):
                dp[i][j]=1
            else:
                dp[i][j]=0
        else:
            if(s1[i]==s2[j]):
                dp[i][j]=1+dp[i-1][j-1]
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
x=n-1
y=m-1
ans=""
while x>0 and y>0:
    if(dp[x][y]==dp[x-1][y-1]+1):
        ans+=s1[x]
        x-=1
        y-=1
    elif(dp[x][y]==dp[x-1][y]):
        x-=1
    else:
        y-=1

if(x==0):
    for i in range(y,-1,-1):
        if(s1[x]==s2[i]):
            ans+=s1[x]
            break
elif(y==0):
    for i in range(x,0,-1):
        if(s1[i]==s2[y]):
            ans+=s1[i]
            break
'''
aabaaa
ababba
'''
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
s1=input()
s2=input()
n=len(s1)
m=len(s2)
dp=[[0]*(m+1) for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        if(s1[i-1]==s2[j-1]):
            dp[i][j]=1+dp[i-1][j-1]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
x=n
y=m
ans=""

while x>0 and y>0:
    if(dp[x][y]==dp[x-1][y-1]+1):
        ans+=s1[x-1]
        x-=1
        y-=1
    elif(dp[x][y]==dp[x-1][y]):
        x-=1
    else:
        y-=1

if(y==m):
    y-=1
if(x==n):
    x-=1
if(x==0):
    for i in range(y,-1,-1):
        if(s1[x]==s2[i]):
            ans+=s1[x]
            break
elif(y==0):
    for i in range(x,0,-1):
        if(s1[i-1]==s2[y]):
            ans+=s1[i-1]
            break

print(ans[::-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
s1=input()
s2=input()
n=len(s1)
m=len(s2)
dp=[[0]*(m+1) for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        if(s1[i-1]==s2[j-1]):
            dp[i][j]=1+dp[i-1][j-1]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
x=n
y=m
ans=""

while x>0 and y>0:
    if(dp[x][y]==dp[x-1][y-1]+1):
        ans+=s1[x-1]
        x-=1
        y-=1
    elif(dp[x][y]==dp[x-1][y]):
        x-=1
    else:
        y-=1

if(x==0):
    for i in range(y,0,-1):
        if(s1[x]==s2[i-1]):
            ans+=s1[x-1]
            break
elif(y==0):
    for i in range(x,0,-1):
        if(s1[i-1]==s2[y]):
            ans+=s1[i-1]
            break

print(ans[::-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
s1=input()
s2=input()
n=len(s1)
m=len(s2)
dp=[[0]*(m+1) for i in range(n+1)]
for i in range(1,n):
    for j in range(1,m):
        if(s1[i-1]==s2[j-1]):
            dp[i][j]=1+dp[i-1][j-1]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
x=n-1
y=m-1
ans=""

while x>0 and y>0:
    if(dp[x][y]==dp[x-1][y-1]+1):
        ans+=s1[x]
        x-=1
        y-=1
    elif(dp[x][y]==dp[x-1][y]):
        x-=1
    else:
        y-=1

if(x==0):
    for i in range(y,-1,-1):
        if(s1[x]==s2[i]):
            ans+=s1[x]
            break
elif(y==0):
    for i in range(x,-1,-1):
        if(s1[i]==s2[y]):
            ans+=s1[i]
            break

print(ans[::-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
s1=input()
s2=input()
n=len(s1)
m=len(s2)
dp=[[0]*m for i in range(n)]
for i in range(n):
    for j in range(m):
        if(s1[i]==s2[j]):
            dp[i][j]=1+dp[i-1][j-1]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
x=n-1
y=m-1
ans=""
while x>0 and y>0:
    if(dp[x][y]==dp[x-1][y-1]+1):
        ans+=s1[x]
        x-=1
        y-=1
    elif(dp[x][y]==dp[x-1][y]):
        x-=1
    else:
        y-=1
if(x==0):
    for i in range(y,-1,-1):
        
        if(s1[x]==s2[i]):
            ans+=s1[x]
            break
elif(y==0):
    for i in range(x,-1,-1):
        
        if(s1[i]==s2[y]):
            ans+=s1[i]
            break
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
lenS = len(S)
lenT = len(T)
"""
dp[i][j] -> Sのi文字目までみる、Tのj文字目まで見るときの最長共通部分列の長さ
if S[i] == T[i]:
    dp[i][j] = dp[i-1][j-1]+1
else:
    dp[i][j] = max(dp[i-1][j],dp[i][j-1])

で最長もとめて、最後に復元していく。
"""
dp = [[0]*(lenT) for _ in range(lenS)]
for i in range(lenS):
    for j in range(lenT):
        if S[i]==T[j]:
            if i==0 or j == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

m = lenS-1
n = lenT-1
ans = []
while n!=-1 and m!=-1:
    if m == 0 and dp[m][n] == 1:
        ans.append(S[m])
        m -= 1
        continue
    if n == 0 and dp[m][n] == 1:
        ans.append(T[n])
        n -= 1
        continue
    if dp[m][n] == dp[m-1][n]:
        m -= 1
        continue
    if dp[m][n] == dp[m][n-1]:
        n -= 1
        continue
    ans.append(S[m])
    m-=1
    n-=1

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

Submission status: Wrong Answer

Solution code:
s1 = input()
s2 = input()
n, m = len(s1), len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
prev = dp[0]
for i in range(1,n+1):
    for j in range(1, m+1):
        dpi = dp[i]
        if s1[i-1] == s2[j-1]:
            dpi[j] = 1 + prev[j-1]
        else:
            dpi[j] = max(prev[j], dpi[j-1])
        prev = dpi
res = ''
i, j = n, m
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 = s1[i-1] + res
        i -= 1
        j -= 1
print(res)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout

int_in = lambda: int(stdin.readline())
arr_in = lambda: [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for y in range(rows)]
str_in = lambda: stdin.readline().strip()
out = lambda o: stdout.write("{}\n".format(o))
arr_out = lambda o: out(" ".join(map(str, o)))
bool_out = lambda o: out("YES" if o else "NO")

if __name__ == "__main__":
    s1 = str_in()
    s2 = str_in()
    dp = [[""]*len(s2) for y in range(len(s1))]
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i] == s2[j]:
                dp[i][j] = dp[i-1][j-1] + s1[i]
            elif 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]

    out(dp[-1][-1])

Submission status: Wrong Answer

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

    S = list(input().rsplit()[0])
    T = list(input().rsplit()[0])

    NS = len(S)
    NT = len(T)

    # dp[i+1][j+1]: Sのi文字目と，Tのj文字目までのLCS
    dp = [[0]*(NT+1) for _ in range(NS+1)]

    for i in range(NS):
        for j in range(NT):
            if S[i] == T[j]:
                # dp[i+1][j+1] = max(dp[i][j] + 1, dp[i+1][j], dp[i][j+1])
                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 = NS
    j = NT
    j_tail = NT
    while True:
        j = j_tail
        while True:
            if dp[i][j] == dp[i-1][j-1]+1 and S[i-1] == T[j-1]:
                ans = T[j-1]+ans
                j_tail = j-1
                break
            j -= 1
            if j == 0:
                break
        if dp[i][j] == 1:
            break
        i -= 1
        if i == 0:
            break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#longest common sequence

s = input()
t = input()

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

ans = []
ans_len = 0

for i in range(1, len_s+1):
    flag = True
    for j in range(1, len_t+1):
        if s[i-1] == t[j-1] and flag:
            if DP[i-1][j] >= DP[i][j-1]+1:
                DP[i][j] = DP[i-1][j]
            else:
                DP[i][j] = DP[i][j-1]+1
                flag = False
                ans.append(s[i-1])
                ans_len += 1
        else:
            DP[i][j] = DP[i][j-1]

print("".join(ans))

Submission status: Wrong Answer

Solution code:
#longest common sequence

s = input()
t = input()

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

ans = []
ans_len = 0

for i in range(1, len_s+1):
    flag = True
    for j in range(1, len_t+1):
        if s[i-1] == t[j-1] and flag:
            if DP[i-1][j] >= DP[i][-j]+1:
                DP[i][j] = DP[i-1][j]
            else:
                DP[i][j] = DP[i][j-1]+1
                flag = False
                ans.append(s[i-1])
                ans_len += 1
        else:
            DP[i][j] = DP[i][j-1]

print("".join(ans))

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
n = len(s)
m = len(t)
dp = [[""] * (m + 5) for _ in range(n + 5)]
for i in range(n):
    for j in range(m):
        tn, tm = len(dp[i + 1][j]), len(dp[i][j])
        if tn < tm:
            dp[i + 1][j] = dp[i][j]
        if tn < tm:
            dp[i][j + 1] = dp[i][j]
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + s[i]
# print(dp)
ans = ""
for i in range(n + 1):
    for j in range(m + 1):
        if len(ans) < len(dp[i][j]):
            ans = dp[i][j]
print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
n = len(s)
m = len(t)
dp = [[""] * (m + 5) for _ in range(n + 5)]
for i in range(n):
    for j in range(m):
        if len(dp[i + 1][j]) < len(dp[i][j]):
            dp[i + 1][j] = dp[i][j]
        if len(dp[i][j + 1]) < len(dp[i][j]):
            dp[i][j + 1] = dp[i][j]
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + s[i]
print(dp)
ans = ""
for i in range(n + 1):
    for j in range(m + 1):
        if len(ans) < len(dp[i][j]):
            ans = dp[i][j]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007


#+++++

def main():
	sa = input()[:-1]
	#sa=sa[:-1]
	sb = input()[:-1]
	#sb=sb[:-1]
	
	#lcb = ['']*len(sb)#[[] for i in range(len(sb))]
	lcb_l = [0]*len(sb)
	lcb_pi = [0]*len(sb)
	for ac in sa:
		ll_l = 0
		ll_i = -1
		for i, bc in enumerate(sb):
			if bc == ac:
				#nlcb[i] = lcb[ll_i]+ac
				t = ll_l + 1
				ti = ll_i
				if ll_l < lcb_l[i]:
					ll_l = lcb_l[i]
					ll_i = i
					#print('ccc', ll_i)
				if lcb_l[i] < t:
					lcb_l[i] = t
					lcb_pi[i] = ti
			elif ll_l < lcb_l[i]:
				ll_l = lcb_l[i]
				ll_i = i
				#print('fff', ll_i)
		#print(lcb_l,lcb_pi)
	
	ml=-1
	pre_i=-1
	ret = []
	tl=len(sb)
	#print(lcb_l,lcb_pi)
	for i, (l, pi, c) in enumerate(zip(lcb_l[::-1], lcb_pi[::-1],sb[::-1])):
		#print(l,i,c)
		if l > ml:
			ml = l
			pre_i = tl - pi - 1
			ret=[c]
			#print(ret)
		elif i == pre_i:
			ret.append(c)
			pre_i = tl - pi - 1
			#print(ret)
	r = ''.join(ret[::-1])
	print(r)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007


#+++++

def main():
	sa = input()[:-1]
	#sa=sa[:-1]
	sb = input()[:-1]
	#sb=sb[:-1]
	
	#lcb = ['']*len(sb)#[[] for i in range(len(sb))]
	lcb_l = [0]*len(sb)
	lcb_pi = [0]*len(sb)
	for ac in sa:
		ll_l = 0
		ll_i = -1
		for i, bc in enumerate(sb):
			if bc == ac:
				#nlcb[i] = lcb[ll_i]+ac
				t = lcb_l[i] + 1
				ti = ll_i
				if ll_l < lcb_l[i]:
					ll_l = lcb_l[i]
					ll_l = i
				lcb_l[i] = t
				lcb_pi[i] = ti
			elif ll_l < lcb_l[i]:
				ll_l = lcb_l[i]
				ll_i = i
	ml=-1
	pre_i=-1
	ret = []
	for l, i, c in zip(lcb_l[::-1], lcb_pi[::-1],sb[::-1]):
		if l > ml:
			ml = l
			pre_i = i
			ret=[c]
		elif i == pre_i:
			ret.append(c)
			pre_i = i
	r = ''.join(ret[::-1])
		
	print(r)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007


#+++++

def main():
	sa = input()[:-1]
	#sa=sa[:-1]
	sb = input()[:-1]
	#sb=sb[:-1]
	
	#lcb = ['']*len(sb)#[[] for i in range(len(sb))]
	lcb_l = [0]*len(sb)
	for ac in sa:
		ll_l = 0
		for i, bc in enumerate(sb):
			if bc == ac:
				#nlcb[i] = lcb[ll_i]+ac
				t=lcb_l[i] + 1
				if ll_l < lcb_l[i]:
					ll_l = lcb_l[i]
				lcb_l[i] = t
			elif ll_l < lcb_l[i]:
				ll_l = lcb_l[i]
	
	ret = max(lcb_l)
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007


#+++++

def main():
	#a = int(input())
	#b , c = IN()
	sa = input()
	sa=sa[:-1]
	sb = input()
	sb=sb[:-1]
	lcb = ['']*len(sb)
	lcb_l = [0]*len(sb)
	for ac in sa:
		ll_i = 0
		lll = lcb_l[0]
		is_update=True
		for i, bc in enumerate(sb):
			if bc == ac and is_update:
				tll_i=ll_i
				tlll = lll
				if lll < lcb_l[i]:
					ll_i = i
					lll = lcb_l[i]
					is_update = True
				pre_len = lcb_l[i]
				post_len = tlll + 1
				if pre_len < post_len:
					lcb[i] = lcb[tll_i]+ac
					lcb_l[i] = tlll + 1
					is_update = False
			elif lll < lcb_l[i]:
					ll_i = i
					lll = lcb_l[i]
					is_update = True
	
	ret = max(lcb, key=lambda s:len(s))
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

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

"""
dp[i][j] = 長さ
i : sのi文字目まで見た状態
j : tのj文字目まで見た状態

遷移
dp[i+1][j+1] = max(dp[i-1][j-1],dp[i][j])
if s[i] == t[j]:
    dp[i+1][j+1] = max(dp[i-1][j-1]+1,dp[i][j])
dp[i][j+1] = max(dp[i][j+1],dp[i][j])
dp[i+1][j] = max(dp[i+1][j],dp[i][j])
"""

dp = [[0]*3001 for i in range(3001)]
res = ""
for i in range(len(s)):
    for j in range(len(t)):
        dp[i][j+1] = max(dp[i][j],dp[i][j+1])
        dp[i+1][j] = max(dp[i][j],dp[i+1][j])
        if 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)
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:
        res = s[i-1] + res
        i -= 1
        j -= 1

print(res)

Submission status: Wrong Answer

Solution code:
x=input()
y=input()
x_part=[[]]*len(x)
y_part=[[]]*len(y)
x_part[0]=['',x[0]]
y_part[0]=['',y[0]]
x_part1=['',x[0]]
for i in range(1,len(x)) :
  part=[]
  for item  in x_part1 :
    part.append(item+x[i])
  x_part1.extend(part)


y_part1=['',y[0]]
for i in range(1,len(y)) :
  part=[]
  for item  in y_part1 :
    part.append(item + y[i])
  y_part1.extend(part)



common=list(set(x_part1)& set(y_part1))
print(common)

current_length=0
current_word=''
for item in common :
  if len(item)>current_length :
    current_length=len(item)
    current_word=item
print(current_word)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

s = input()
t = input()

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

for i in range(1,len(t)+1):
    for j in range(1,len(s)+1):
        if s[j-1] == t[i-1]:
            dp[i][j] = dp[i-1][j-1] + (s[j-1]==t[i-1])
        else:
            dp[i][j] = max(dp[i][j-1],dp[i-1][j])
i = len(t)
j = len(s)
x = dp[i][j]
ans = ''
while i > 0 and j > 0:
    if dp[i][j-1] < x:
        ans = ''.join([s[j-1],ans])
        x = dp[i][j-1]
        i -= 1
    j -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

s = input()
t = input()

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

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

i = len(t)
j = len(s)
x = dp[i][j]
ans = ''
while i > 0 and j > 0:
    if dp[i][j-1] < x:
        ans = ''.join([s[j-1],ans])
        x = dp[i][j-1]
        i -= 1
    j -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

s = ns()
t = ns()
lenS = len(s)
lenT = len(t)

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

rest = []
m = 0
for i in range(1, len(s) + 1):
    for j in range(1, len(t) + 1):
        if dp[i][j] > max(dp[i - 1][j], dp[i][j - 1]) and dp[i][j] > m:
            rest.append(s[i - 1])
            m = dp[i][j]

print(*rest, sep="")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def inp_str():
    '''
    一行の文字をlistで取得
    '''
    return list(input())[:-1]

s = inp_str()
t = inp_str()
n = len(s)
m = len(t)
value = [[0]*(m+1) for i in range(n+1)]
ans = [[""]*(m+1) for i in range(n+1)]

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
        elif value[i][j + 1] > value[i + 1][j]: #UP
            ans[i + 1][j + 1] = ans[i][j + 1]
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            ans[i + 1][j + 1] = ans[i + 1][j]
            value[i + 1][j + 1] = value[i + 1][j]


print(ans[n][m])

Submission status: Wrong Answer

Solution code:
s,t = input(),input()
n,m=len(s),len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m):
  for j in range(n):
    if t[i] == s[j]:
      dp[i+1][j+1] = max(dp[i][j]+1,dp[i+1][j+1])
    dp[i+1][j+1] = max(dp[i+1][j+1],dp[i+1][j],dp[i][j+1])
ans = ""
cnt = 0
i,j = m,n
while cnt != dp[-1][-1]:
  if dp[i][j] == dp[i][j-1]:
    j -= 1
    continue
  else:
    ans += s[j-1]
    cnt += 1
    i,j = i-1,j-1

print(ans[::-1])

Submission status: Wrong Answer

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

out = []
for j in range(1,LS+1):
    if dp[-1][j] > dp[-1][j-1]:
        out.append(s[j-1])
print("".join(out))

Submission status: Wrong Answer

Solution code:
# python3だとTLE,pypy3だとAC
def main():
    s = input()
    t = input()
    dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
    for i, cs in enumerate(s, start=1):
        for j, ct in enumerate(t, start=1):
            if cs == ct:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    ans = ""
    i = len(s)
    j = len(t)
    while i > 0 and j > 0:
        if dp[i-1][j] > dp[i][j-1]:
            i -= 1
        elif dp[i-1][j] < dp[i][j-1]:
            j -= 1
        else:
            if dp[i-1][j-1]+1 == dp[i][j]:
                i -= 1
                j -= 1
                ans += s[i]
            else:
                i -= 1

    print(ans[::-1])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# python3だとTLE,pypy3だとAC
def main():
    s = input()
    t = input()
    dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
    for i, cs in enumerate(s, start=1):
        for j, ct in enumerate(t, start=1):
            if cs == ct:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    ans = ""
    i = len(s)
    j = len(t)
    while i > 0 and j > 0:
        if i > 0 and j > 0:
            if dp[i-1][j] > dp[i][j-1]:
                i -= 1
            elif dp[i-1][j] < dp[i][j-1]:
                j -= 1
            else:
                if dp[i-1][j-1]+1 == dp[i][j]:
                    i -= 1
                    j -= 1
                    ans += s[i]
                else:
                    i -= 1

    print(ans[::-1])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
s,t=input(),input()
S,T=len(s),len(t)

DP=[[0 for _ in range(T+1)] for _ in range(S+1)]
for i in range(1,S+1):
    for j in range(1,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])

ans=""
x,y=S,T
while 1:
    if DP[x][y]==0:break
    if DP[x-1][y-1]==DP[x][y]-1:
        ans +=s[x-1]
        x -=1
        y -=1
    elif DP[x][y]==DP[x-1][y]:
        x -=1
    elif DP[x][y]==DP[x][y-1]:
        y -=1

print(ans[::-1])

Submission status: Wrong Answer

Solution code:
s,t=input(),input()
S,T=len(s),len(t)

DP=[[0 for _ in range(T+1)] for _ in range(S+1)]
for i in range(1,S+1):
    for j in range(1,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])

ans=""
x,y=S,T
while 1:
    if x==0 or y==0:break
    if DP[x-1][y-1]==DP[x][y]-1:
        ans +=s[x-1]
        x -=1
        y -=1
    elif DP[x][y]==DP[x-1][y]:
        x -=1
    elif DP[x][y]==DP[x][y-1]:
        y -=1

print(ans[::-1])

Submission status: Wrong Answer

Solution code:
s,t=input(),input()
S,T=len(s),len(t)

DP=[[0 for _ in range(T+1)] for _ in range(S+1)]
for i in range(1,S+1):
    for j in range(1,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])

ans=""
x,y=S,T
while 1:
    if x==0 or y==0:break
    if DP[x-1][y-1]==DP[x][y]-1:
        ans +=s[x-1]
        x -=1
        y -=1
    else:
        x -=1
print(ans[::-1])

Submission status: Wrong Answer

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

dp = [['']*(len(t)+1)]*(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] = ''.join([dp[i+1][j+1], s[i]])
        else:
            if len(dp[i+1][j]) >= len(dp[i][j+1]):
                dp[i+1][j+1] = dp[i+1][j]
            else:
                dp[i+1][j+1] = dp[i][j+1]

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

Submission status: Wrong Answer

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

dp = [['']*(len(t)+1)]*(len(s)+1)

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

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

Submission status: Wrong Answer

Solution code:
s=list(input())
t=list(input())
dp=[[0]*(3030) for j in range(3030)]
ans=[]
memo=-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
             if memo < i:
                 ans.append(t[j])
                 memo = i

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

#print(dp[len(s)][len(t)])
answer=[]
i,j=len(s),len(t)
d=dp[i-1][j-1]
while i>=0 and j>=0:
    if dp[i-1][j-1]!=dp[i][j]:
        answer.append(s[i-1])
        i-=1
        j-=1
        continue
    elif dp[i-1][j]==dp[i][j]:
        i-=1
    elif dp[i][j-1]==dp[i][j]:
        j-=1
print("".join(reversed(answer)))

Submission status: Wrong Answer

Solution code:
s=list(input())
t=list(input())
dp=[[0]*(3030) for j in range(3030)]
ans=[]
memo=-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
             if memo < i:
                 ans.append(t[j])
                 memo = i

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

#print(dp[len(s)][len(t)])
answer=[]
i,j=len(s),len(t)
d=dp[i-1][j-1]
while i>0 and j>0:
    if dp[i-1][j-1]!=dp[i][j]:
        answer.append(s[i-1])
        i-=1
        j-=1
        continue
    elif dp[i-1][j]==dp[i][j]:
        i-=1
    elif dp[i][j-1]==dp[i][j]:
        j-=1
print("".join(reversed(answer)))