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:
def main(): 
  s = input()
  t = input()

  LS = len(s)
  LT = len(t)
      
  DP = ["" for i in range(LT)]
  T = [0 for i in range(LT)]
  
  start = ""
  
  for i in range(LS):
    flag = False
    if DP[0] == "":
      if s[i] == t[0]:
        DP[0] = s[i]
        start = DP[0]
        T[0] = 1
        flag = True
    k = start
    for j in range(1, LT):
      if s[i] == t[j] and T[j] == 0:
        if not flag:
          T[j] = 1
          flag = True
        if len(k) < len(DP[j]) + 1:
          k = DP[j] + s[i]
        DP[j] = k     
      else:
        flag = False
        if len(k) < len(DP[j]):
          k = DP[j]
        else:
          DP[j] = k
          T[j] = 0
          
  print(DP[-1])
  
main()

Submission status: Wrong Answer

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

  LS = len(s)
  LT = len(t)
      
  DP = ["" for i in range(LT)]
  T = [0 for i in range(LT)]
  
  start = ""
  
  for i in range(LS):
    flag = False
    if DP[0] == "":
      if s[i] == t[0]:
        DP[0] = s[i]
        start = DP[0]
        T[0] = 1
        flag = True
    k = start
    for j in range(1, LT):
      if flag:
        T[j] = 0
      if s[i] == t[j] and T[j] == 0:
        if not flag:
          T[j] = 1
          flag = True
        if len(k) < len(DP[j]) + 1:
          k = DP[j] + s[i]
        DP[j] = k
           
      else:
        if len(k) < len(DP[j]):
          k = DP[j]
        else:
          DP[j] = k
          
  print(DP[-1])
  
main()

Submission status: Wrong Answer

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

  LS = len(s)
  LT = len(t)
      
  DP = ["" for i in range(LT)]

  for i in range(LS):
    if s[i] == t[0]:
      DP[0] = s[i]
    k = DP[0]
    for j in range(1, LT):
      if s[i] == t[j]:
        if len(k + s[i]) > len(DP[j]):
          DP[j] = k + s[i]
      if DP[j] != "":
        k = DP[j]

  Ans = ""
  for i in DP:
    if len(Ans) < len(i):
      Ans = i
  print(Ans)
  
main()

Submission status: Wrong Answer

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

LS = len(s)
LT = len(t)
    
DP = ["" for i in range(LT)]

for i in range(LS):
  if s[i] == t[0]:
    DP[0] = s[i]
  k = DP[0]
  for j in range(1, LT):
    if s[i] == t[j]:
      if len(k + s[i]) > len(DP[j]):
        DP[j] = k + s[i]
    if DP[j] != "":
      k = DP[j]

Ans = ""
for i in DP[::-1]:
  if i != "":
    Ans = i
    break
print(Ans)

Submission status: Wrong Answer

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

LS = len(s)
LT = len(t)

num = LT
for i in range(LT):
  if s[0] == t[i]:
    num = i
    break

if LS == 1:
  if num == LT:
    print("")
  else:
    print (s)
  exit()
    
DP = [[0 if i < num or j != 0 else 1 for i in range(LT)] for j in range(LS)]
T = [1 if i == num else 0 for i in range(LT)]
if num != LT:
  L = ["", s[0]]
else:
  L = [""]
for i in range(1, LS):
  ma = DP[i-1][0]
  flag = 0
  for j in range(LT):
    if flag == 1:
      T[j] = 0
    if s[i] == t[j] and T[j] == 0:
      if flag == 0:
        T[j] = 1
        flag = 1
      Lt = DP[i-1][j]
      if len(L[ma]) <= len(L[Lt]):
        L.append(L[Lt] + s[i])
        ma = len(L) - 1
    elif len(L[ma]) < len(L[DP[i-1][j]]):
      ma = DP[i-1][j]
    DP[i][j] = ma

print(L[ma])

Submission status: Wrong Answer

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

LS = len(s)
LT = len(t)

num = LT
for i in range(LT):
  if s[0] == t[i]:
    num = i
    break

if LS == 1:
  if num == LT:
    print("")
  else:
    print (s)
  exit()
    
DP = [[0 if i < num or j != 0 else 1 for i in range(LT)] for j in range(LS)]
T = [1 if i == num else 0 for i in range(LT)]
if num != LT:
  L = ["", s[0]]
else:
  L = [""]
for i in range(1, LS):
  ma = DP[i-1][0]
  flag = 0
  for j in range(LT):
    if flag == 1:
      T[j] = 0
    if s[i] == t[j] and T[j] == 0:
      if flag == 0:
        T[j] = 1
        flag = 1
      Lt = DP[i-1][j]
      if len(L[ma]) <= len(L[Lt]):
        L.append(L[Lt] + s[i])
        ma = len(L) - 1
    elif ma < DP[i-1][j]:
      ma = DP[i-1][j]
    DP[i][j] = ma
print(L[ma])

Submission status: Wrong Answer

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

LS = len(s)
LT = len(t)

num = LT
for i in range(LT):
  if s[0] == t[i]:
    num = i
    break

if LS == 1:
  if num == LT:
    print("")
  else:
    print (s)
  exit()
    
DP = [[0 if i < num or j != 0 else 1 for i in range(LT)] for j in range(LS)]
T = [1 if i == num else 0 for i in range(LT)]
for i in range(1, LS):
  ma = DP[i-1][0]
  flag = 0
  for j in range(LT):
    if flag == 1:
      T[j] = 0
    if s[i] == t[j] and T[j] == 0:
      if flag == 0:
        T[j] = 1
        flag = 1
      ma = min(ma + 1, DP[i-1][j] + 1)
    elif ma < DP[i-1][j]:
      ma = DP[i-1][j]
    DP[i][j] = ma

Ans = ""
cnt = ma
j = LS - 1
k = LT - 1

while True:
  for i in range(j, -1, -1):
    if DP[i][k] != cnt:
      j = i + 1
      break
    if i == 0:
      Ans += s[0]
      cnt = 0
      break
  if cnt == 0:
    break
  for i in range(k, -1, -1):
    if DP[j][i] != cnt:
      k = i
      cnt -= 1
      break
    if i == 0:
      Ans += t[0]
      cnt = 0
      break
  if cnt == 0:
    break
  Ans += s[j]
  
print(Ans[::-1])

Submission status: Wrong Answer

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

LS = len(s)
LT = len(t)

num = LT
for i in range(LT):
  if s[0] == t[i]:
    num = i
    break

if LS == 1:
  if num == LT:
    print("")
  else:
    print (s)
  exit()
    
DP = [[0 if i < num or j != 0 else 1 for i in range(LT)] for j in range(LS)]
T = [1 if i == num else 0 for i in range(LT)]
for i in range(1, LS):
  ma = DP[i-1][0]
  flag = 0
  for j in range(LT):
    if flag == 1:
      T[j] = 0
    if s[i] == t[j] and T[j] == 0:
      if flag == 0:
        T[j] = 1
        flag = 1
      ma = min(ma + 1, DP[i-1][j] + 1)
    elif ma < DP[i-1][j]:
      ma = DP[i-1][j]
    DP[i][j] = ma

DP = list(zip(*DP))

Ans = ""
cnt = ma
k = LS-1
for i in range(LT-1, -1, -1):
  for j in range(k, -1, -1):
    if cnt > DP[i][j]:
      if j != k:
        Ans += s[j+1]
      else:
        Ans += s[0]
      k = j
      cnt -= 1
      break
if cnt == 1:
  Ans += s[0]

print(Ans[::-1])

Submission status: Wrong Answer

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

LS = len(s)
LT = len(t)

num = LT
for i in range(LT):
  if s[0] == t[i]:
    num = i
    break

if LS == 1:
  if num == LT:
    print("")
  else:
    print (s)
  exit()
    
DP = [[0 if i < num or j != 0 else 1 for i in range(LT)] for j in range(LS)]

for i in range(1, LS):
  ma = DP[i-1][0]
  for j in range(LT):
    if s[i] == t[j]:
      ma = min(ma + 1, DP[i-1][j] + 1)
    elif ma < DP[i-1][j]:
      ma = DP[i-1][j]
    DP[i][j] = ma
DP = list(zip(*DP))

Ans = ""
cnt = ma
k = LS-1
for i in range(LT-1, -1, -1):
  for j in range(k, -1, -1):
    if cnt > DP[i][j]:
      if j != k:
        Ans += s[j+1]
      else:
        Ans += s[0]
      k = j
      cnt -= 1
      break
if cnt == 1:
  Ans += s[0]

print(Ans[::-1])

Submission status: Wrong Answer

Solution code:
import sys
s = input()
t = input()
dp = [[0 for i in range(len(t) + 1)] for j in range(len(s) + 1)]
for i in range(len(s) + 1):
    for j in range(len(t) + 1):
        if i < len(s) and j < len(t) and s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
        if i < len(s):
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        if j < len(t):
            dp[i][j + 1] = max(dp[i][j + 1], dp[i][j])
ret = dp[len(s)][len(t)]
# reverse
res = ""
y = len(t)
x = len(s)
while dp[x][y] > 0:
    # can be shorten
    if x > 0 and y > 0 and dp[x-1][y-1] + 1 == dp[x][y]:
        res = s[x-1] + res
        x -= 1
        y -= 1
    elif x > 0 and dp[x-1][y] == dp[x][y]:
        x -= 1
    elif y > 0 and dp[x][y-1] == dp[x][y]:
        y -= 1
print(res)

Submission status: Wrong Answer

Solution code:
import itertools as itr

s = input()
t = input()

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

dp = [['']*(lt+1) for _ in range(ls+1)]

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

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

Submission status: Wrong Answer

Solution code:
import itertools as itr

s = input()
t = input()

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

dp = [['']*(lt+1) for _ in range(ls+1)]

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

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

Submission status: Wrong Answer

Solution code:
import itertools as itr

s = input()
t = input()

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

dp = [['']*(lt+1) for _ in range(ls+1)]

for i, j in itr.product(range(1, ls+1), range(1, lt+1)):
    if s[i-1] == t[j-1]:
        if len(dp[i][j-1]) > len(dp[i-1][j]):
            dp[i][j] = dp[i][j-1]+s[i-1]
        else:
            dp[i][j] = dp[i-1][j]+s[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((i,j), dp[i][j])

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

Submission status: Wrong Answer

Solution code:
import itertools as itr

s = input()
t = input()

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

dp = [['']*(lt) for _ in range(ls)]

for i, j in itr.product(range(ls), range(lt)):
    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((i,j), dp[i][j])

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

Submission status: Wrong Answer

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_f
#2019-01-14
s = input()
t = input()

def LCS(S,T):
  #初期化
  dp = [["0"*(3000) for i in range(len(T)+1)] for j in range(len(S)+1)]
  dp[0][0], dp[0][1], dp[1][0] = "", "", ""

  #DP
  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], dp[i][j] + S[i], key=len)
      else:
        dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j], key=len)
  return dp[len(S)][len(T)]

print(LCS(s,t))

Submission status: Wrong Answer

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_f
#2019-01-14
s = input()
t = input()

def LCS(S,T):
  #初期化
  dp = [["" for i in range(len(T)+1)] for j in range(len(S)+1)]

  #DP
  for i in range(len(S)):
    for j in range(len(T)):
      dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
      if S[i]==T[j]:
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+S[i])
  return dp[len(S)][len(T)]

print(LCS(s,t))

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
a = len(s) + 1
b = len(t) + 1

X = [[0] * b for _ in range(a)]
for i in range(1, a):
    for j in range(1, b):
        X[i][j] = max(X[i-1][j], X[i][j-1])
        if s[i-1] == t[j-1]:
            X[i][j] = max(X[i-1][j-1]+1, X[i][j])
        
        
print(X[-1][-1])

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys

INF = float('inf')
MOD = 10 ** 9 + 7

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


s = [ord(n) for n in S()]
t = [ord(n) for n in S()]

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

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

# print('-----', ', '.join([chr(tt) for tt in t]))
# for i, d in enumerate(dp):
#     if i == 0:
#         continue
#     else:
#         print(chr(s[i - 1]), d)

ans = ''
i = len(s) - 1
for j in range(len(t))[::-1]:
    if i == 1:
        if dp[1][j] != dp[1][j + 1]:
            ans += chr(t[j])
    else:
        if dp[i][j] != dp[i + 1][j + 1]:
            ans += chr(t[j])
        i -= 1

print(ans[::-1])

Submission status: Wrong Answer

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

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

DP=[[0 for j in range(len_t+1)] for i in range(len_s+1)]
DICT=dict()

for i in range(1,len_s+1):
    for j in range(1,len_t+1):
        if s[i-1]==t[j-1]:
            if DP[i-1][j]==DP[i][j-1]:
                DP[i][j]=DP[i-1][j]+1
                DICT[(i,j)]=s[i-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])
            
        
x,y=len_s,len_t
ANS=""

while x>0 and y>0:
    if x>0 and DP[x-1][y]==DP[x][y]:
        x-=1
    elif y>0 and DP[x][y-1]==DP[x][y]:
        y-=1
    else:
        ANS+=DICT[(x,y)]
        x-=1
        y-=1

print(ANS[::-1])

Submission status: Wrong Answer

Solution code:
import sys
raw_input = sys.stdin.readline
s = list(raw_input().strip('\n'))
t = list(raw_input().strip('\n'))
N,M = len(s),len(t)
dp = [[0 for x in range(M+1)] for x in range(N+1)]
lst = [[[] for x in range(M+1)] for x in range(N+1)]
for i in range(N):
    for j in range(M):
        if s[i]==t[j]:
            if (dp[i][j]+1)>dp[i+1][j+1]:
                lst[i+1][j+1] = [i,j]
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1)
        if dp[i][j]>dp[i+1][j]:
            lst[i+1][j] = [i,j]
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if dp[i][j]>dp[i][j+1]:
            lst[i][j+1] = [i,j]
        dp[i][j+1] = max(dp[i][j+1],dp[i][j])
        if dp[i][j]>dp[i+1][j+1]:
            lst[i+1][j+1] = [i,j]
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j])
a,b = N,M
ans = ['']
while lst[a][b]:
    a,b = lst[a][b]
    if s[a]==t[b]:
        ans.append(s[a])
print "".join(ans[::-1])

'''
abcdefghijklmnop
jlmopabcdef
'''

Submission status: Wrong Answer

Solution code:
import sys
raw_input = sys.stdin.readline
s = list(raw_input().strip('\n'))
t = list(raw_input().strip('\n'))
N,M = len(s),len(t)
dp = [[0 for x in range(M+1)] for x in range(N+1)]
lst = [[[] for x in range(M+1)] for x in range(N+1)]
for i in range(N):
    for j in range(M):
        if s[i]==t[j]:
            if (dp[i][j]+1)>dp[i+1][j+1]:
                lst[i+1][j+1] = [i,j]
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1)
        if dp[i][j]>dp[i+1][j]:
            lst[i+1][j] = [i,j]
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if dp[i][j]>dp[i][j+1]:
            lst[i][j+1] = [i,j]
        dp[i][j+1] = max(dp[i][j+1],dp[i][j])
a,b = N,M
ans = ['']
while lst[a][b]:
    a,b = lst[a][b]
    if s[a]==t[b]:
        ans.append(s[a])
print "".join(ans[::-1])

Submission status: Wrong Answer

Solution code:
s = input();t = input()
l = len(s);r = len(t)
dp = [["" for i in range(r + 1)] for j in range(l + 1)]

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

print(dp[l][r])

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
ls,lt=len(s),len(t)
dp=[['']*(ls+1) for i in range(lt+1)]
for i in range(lt):
    for j in range(ls):
        if t[i]==s[j]:dp[i+1][j+1]=dp[i][j]+s[j]
        else:dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
print(dp[-1][-1])

Submission status: Wrong Answer

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

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

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


ans = " "
j = len(t) - 1 
i = len(s) - 1 

while True:
    if j == 0:
        if dp[0][i] == 1:
            ans += t[0]
        break
        
    else:
        if dp[j][i] == dp[j-1][i]:
            j -= 1
        else:
            ans += t[j]
            j -= 1
            i -= 1

#for i in range(len(t)):
#    print(dp[i])
print(ans[::-1])

Submission status: Wrong Answer

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

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

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


ans = ""
j = len(t) - 1 
i = len(s) - 1 

while True:
    if j == 0:
        if dp[0][i] == 1:
            ans += t[0]
        break
        
    else:
        if dp[j][i] == dp[j-1][i]:
            j -= 1
        else:
            ans += t[j]
            j -= 1
            i -= 1

#for i in range(len(t)):
#    print(dp[i])
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(lt):
    for j in range(ls):
        if t[i]==s[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
ans=''
for i in range(lt+1):
    if (len(ans)+1) in dp[i]:ans+=str(s[dp[i].index(len(ans)+1)-1])
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def lcs(X, Y):
    m = len(X)
    n = len(Y)

    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])

    lcs_str = ''
    i, j = m, n
    while i > 0 and j > 0:
        if c[i][j] == c[i-1][j-1] + 1:
            lcs_str += Y[j-1]
            i -= 1
            j -= 1
        else:
            if c[i-1][j] < c[i][j-1]:
                i -= 1
            else:
                j -= 1

    return lcs_str[::-1]


s = input()
t = input()
print(lcs(s, t))

Submission status: Wrong Answer

Solution code:
def lcs(X, Y):
    m = len(X)
    n = len(Y)

    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])

    lcs_str = ''
    i, j = m, n
    while i >= 0 and j >= 0:
        if c[i][j] == c[i-1][j-1] + 1:
            lcs_str += Y[j-1]
            i -= 1
            j -= 1
        else:
            if c[i-1][j] < c[i][j-1]:
                i -= 1
            else:
                j -= 1

    return lcs_str[::-1]


s = input()
t = input()
print(lcs(s, t))

Submission status: Wrong Answer

Solution code:
def lcs(X, Y):
    m = len(X)
    n = len(Y)

    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])

    lcs_str = ''
    i, j = m, n
    while i >= 0 and j >= 0:
        if c[i][j] == c[i-1][j-1] + 1:
            lcs_str += X[i-1]
            i -= 1
            j -= 1
        else:
            if c[i-1][j] >= c[i][j-1]:
                i -= 1
            else:
                j -= 1

    return lcs_str[::-1]


s = input()
t = input()
print(lcs(s, t))

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
dp = [0]
lcs = ['']
for b in t:
    search_idx = 0
    for i, curr_idx in enumerate(dp):
        char_idx = s.find(b, search_idx)
        if char_idx == -1:
            break
        next_idx = char_idx + 1
        if next_idx < curr_idx:
            dp[i] = next_idx
            lcs[i] = lcs[i - 1] + b
        search_idx = curr_idx
    else:
        char_idx = s.find(b, search_idx)
        if char_idx > -1:
            dp.append(char_idx + 1)
            lcs.append(lcs[-1] + b)
print(lcs[-1])

Submission status: Wrong Answer

Solution code:
def lcs(X, Y):
    m = len(X)
    n = len(Y)

    c = [[0 for _ in range(n+1)] for _ in range(m+1)]
    s = set()
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                c[i][j] = c[i-1][j-1] + 1
                if n >= m and j >= i:
                    s.add(j-1)
                if m > n and i >= j:
                    s.add(i-1)
            else:
                c[i][j] = max(c[i-1][j], c[i][j-1])

    return s

s = input()
t = input()

x = lcs(s, t)
ans = ""
for i in x:
    if len(t) >= len(s):
        ans += t[i]
    else:
        ans += s[i]
print(ans)

Submission status: Wrong Answer

Solution code:
def lcs(X, Y):
    m = len(X)
    n = len(Y)

    c = [[0 for _ in range(n+1)] for _ in range(m+1)]
    s = set()
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                c[i][j] = c[i-1][j-1] + 1
                if j >= i:
                    s.add(j-1)
            else:
                c[i][j] = max(c[i-1][j], c[i][j-1])

    return s

s = input()
t = input()

x = lcs(s, t)
ans = ""
for i in x:
    ans += t[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():

    s = str(input())
    t = str(input())

    dp = [[0]*3100 for _ in range(3100)]

    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]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans.append(s[i-1])
            i -= 1
            j -= 1
    ans.reverse()
    print(''.join(ans))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# ライブラリのインポート
import numpy as np


# メイン関数
def main():
    # 入力データ
    s = input()
    t = input()

    # dpテーブルの作成
    dp = np.zeros((len(s) + 1, len(t) + 1), dtype='int')
    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])

    # 部分列の復元
    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:
            i -= 1
            j -= 1
            ans = s[i] + ans

    # 解答の出力
    print(ans)
    return


# 実行
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# ライブラリのインポート
import numpy as np


# メイン関数
def main():
    # 入力データ
    s = np.array(list(input()))
    t = np.array(list(input()))

    # dpテーブルの作成
    dp = np.zeros((len(s) + 1, len(t) + 1), dtype='int')
    for i in range(1, len(s) + 1):
        for j in range(1, len(t) + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # 部分列の復元
    length = dp[len(s)][len(t)]
    ans = ''
    i = len(s)
    j = len(t)
    while length > 0:
        if s[i - 1] == t[j - 1]:
            ans = s[i - 1] + ans
            i -= 1
            j -= 1
            length -= 1
        elif dp[i][j] == dp[i - 1][j]:
            i -= 1
        else:
            j -= 1

    # 解答の出力
    print(ans)
    return


# 実行
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():


    s = "#" + S()
    t = "#" + S()

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

    for i in range(len(t)-1):
        for j in range(len(s)-1):
            if t[i+1] == s[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 = ""
    now = dp[len(t)-1][len(s)-1]
    zahyo = [len(t)-1, len(s)-1]
    while now != 0:
        while dp[zahyo[0]][zahyo[1]-1]==now:
            zahyo[1]-=1
        while dp[zahyo[0]-1][zahyo[1]]==now:
            zahyo[0]-=1

        ans += t[zahyo[0]]

        now -= 1
        zahyo = [zahyo[0]-1, zahyo[1]-1]

    ans = ans[::-1]

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


#sys.setrecursionlimit(10 ** 6)


s = st()
t = st()


n1 = len(s)
n2 = len(t)


dp = [[(-1, -1, 0) for i in range(n2 + 1)] for j in range(n1 + 1)]


for i in range(n1 -1, -1, -1):
    for j in range(n2 - 1, -1, -1):
        if s[i] == t[j]:dp[i][j] = (i + 1, j + 1, dp[i + 1][j + 1][-1] + 1)
        elif dp[i + 1][j][-1] > dp[i][j + 1][-1]:dp[i][j] = (i + 1, j, dp[i + 1][j][-1])
        else:dp[i][j] = (i, j + 1, dp[i][j + 1][-1])

ans = ''

x, y = 0, 0

while x < n1 and y < n2 and x != -1 and y != -1:
    # print(x, y)
    if s[x] == t[y]:
        ans += s[x]
    x, y = dp[x][y][0], dp[x][y][1]
    

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


sys.setrecursionlimit(10 ** 6)


s = st()
t = st()


n1 = len(s)
n2 = len(t)

@lru_cache(None)
def dp(i, j):
    if i == n1 or j == n2:return (-1, -1, 0)
    ans = (-1, -1, 0)
    if s[i] == t[j]:return (i + 1, j + 1, dp(i + 1, j + 1)[-1] + 1)
    

    if dp(i + 1, j)[-1] > ans[-1]:ans = (i + 1, j, dp(i + 1, j)[-1])
    if dp(i, j + 1)[-1] > ans[-1]:ans = (i, j + 1, dp(i, j + 1)[-1])
    
    # print(i, j, ans)

    return ans


dp(0, 0)
ans = ''

x, y = 0, 0

while x < n1 and y < n2 and x != -1 and y != -1:
    # print(x, y)
    if s[x] == t[y]:
        ans += s[x]
    x = dp(x, y)[0]
    y = dp(x, y)[1]
    

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


sys.setrecursionlimit(10 ** 6 + 10)

s = st()
t = st()


n1 = len(s)
n2 = len(t)

@lru_cache(None)
def dp(i, j):
    if i == n1 or j == n2:return ''
    ans = ''

    curr = s[i]
    ind = j
    while j < n2 and t[j] != curr:
        j += 1
    if j != n2:
        temp = curr + dp(i + 1, j + 1)
        if len(temp) > len(ans):ans = temp
    
    j = ind
    ind = i
    curr = t[j]
    while i < n1 and s[i] != curr:
        i += 1
    if i != n1:
        temp = curr + dp(i + 1, j + 1)
        if len(temp) > len(ans):ans = temp
    
    i = ind

    if len(dp(i + 1, j)) > len(ans):ans = dp(i + 1, j)
    if len(dp(i, j + 1)) > len(ans):ans = dp(i, j + 1)
    

    return ans


print(dp(0, 0))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


sys.setrecursionlimit(10 ** 6)

s = st()
t = st()


n1 = len(s)
n2 = len(t)

@lru_cache(None)
def dp(i, j):
    if i == n1 or j == n2:return ''
    ans = ''

    curr = s[i]
    ind = j
    while j < n2 and t[j] != curr:
        j += 1
    if j != n2:
        temp = curr + dp(i + 1, j + 1)
        if len(temp) > len(ans):ans = temp
    
    j = ind
    ind = i
    curr = t[j]
    while i < n1 and s[i] != curr:
        i += 1
    if i != n1:
        temp = curr + dp(i + 1, j + 1)
        if len(temp) > len(ans):ans = temp
    
    i = ind

    if len(dp(i + 1, j)) > len(ans):ans = dp(i + 1, j)
    if len(dp(i, j + 1)) > len(ans):ans = dp(i, j + 1)
    

    return ans


print(dp(0, 0))