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: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


s = S()
t = S()
S,T = len(s),len(t)
dp = [[0]*(T+1) for _ in range(S+1)]
for i in range(S):
    for j in range(T):
        if s[i]==t[j]:
            dp[i+1][j+1] = 1 + dp[i][j]
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])



ans = ""
while dp[S][T]:
    if dp[S - 1][T] == dp[S][T]:
        S -= 1
    elif dp[S][T - 1] == dp[S][T]:
        T -= 1
    else:
        S -= 1
        T -= 1
        ans = s[S] + ans


if len(ans) == 0:
    print("")
else:
    print(ans)

Submission status: Accepted

Solution code:
s = input()
t = input()
mx = 0
mxp = [-1, -1]
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] = 1 + dp[i][j]
		else:
			dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
		if dp[i + 1][j + 1] > mx:
			mx = dp[i + 1][j + 1]
			mxp = [i + 1, j + 1]
if mx == 0:
	print()
else:
	ans = ''
	x = mxp[0]
	y = mxp[1]
	while dp[x][y]:
		if s[x - 1] == t[y - 1]:
			ans += s[x - 1]
			x -= 1
			y -= 1
		else:
			if dp[x - 1][y] > dp[x][y - 1]:
				x -= 1
			else:
				y -= 1
	print(ans[::-1])

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

A = S()
B = S()

def lcs(S, T):
  L1 = len(S)
  L2 = len(T)
  dp = [[0]*(L2+1) for i in range(L1+1)]

  for i in range(L1-1, -1, -1):
    for j in range(L2-1, -1, -1):
      r = max(dp[i+1][j], dp[i][j+1])
      if S[i] == T[j]:
        r = max(r, dp[i+1][j+1] + 1)
      dp[i][j] = r

  #return dp[0][0]
  # dp[0][0] が長さの解

  # ここからは復元処理
  res = []
  i = 0; j = 0
  while i < L1 and j < L2:
    if S[i] == T[j]:
      res.append(S[i])
      i += 1; j += 1
    elif dp[i][j] == dp[i+1][j]: i += 1
    elif dp[i][j] == dp[i][j+1]: j += 1
  return "".join(res)

print(lcs(A,B))

Submission status: Accepted

Solution code:
import sys
import numpy as np
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def longest_common_subsequence(S, T):
    LS, LT = len(S), len(T)
    dp = np.zeros((LS + 1, LT + 1), np.int32)
    for n in range(1, LS + 1):
        dp[n, 1:] = dp[n - 1, :-1] + (S[n - 1] == T)  # 左上から
        np.maximum(dp[n], dp[n - 1], out=dp[n])  # 上から
        np.maximum.accumulate(dp[n], out=dp[n])  # 左から
    return dp
 
def reconstruct_LCS(S, T, dp):
    tmp = []
    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if S[i - 1] == T[j - 1]:
            i, j = i - 1, j - 1
            tmp.append(S[i])
        elif dp[i, j] == dp[i - 1, j]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(tmp))
 
S = np.array(list(readline().decode()), 'U1')[:-1]
T = np.array(list(readline().decode()), 'U1')[:-1]
 
dp = longest_common_subsequence(S, T)
 
print(reconstruct_LCS(S, T, dp))

Submission status: Accepted

Solution code:
def LCS_iter(s1, s2):
	dp = [[-10000 for i in range(len(s2) + 1)] for i in range(len(s1) + 1)]
	ans = [['' for i in range(len(s2) + 1)] for i in range(len(s1) + 1)]
	for i in range(len(s2) + 1):
		dp[0][i] = 0
	for i in range(len(s1) + 1):
		dp[i][0] = 0
	i = 1
	j = 1
	while i <= len(s1):
		while j <= len(s2):
			if s1[i - 1] == s2[j - 1]:
				dp[i][j] = 1 + dp[i - 1][j - 1]
				ans[i][j] = 'cross'
			else:
				if dp[i - 1][j] > dp[i][j - 1]:
					dp[i][j] = dp[i - 1][j]
					ans[i][j] = 'up'
				else:
					dp[i][j] = dp[i][j - 1]
					ans[i][j] = 'left'
			j += 1
		i += 1
		j = 1
	i = len(s1)
	j = len(s2)
	s = ''
	while i >= 0 and j >= 0:
		if ans[i][j] == 'cross':
			s += s1[i - 1]
			i -= 1
			j -= 1
		elif ans[i][j] == 'up':
			i -= 1
		else:
			j -= 1
	return s[::-1]
 
 
s1 = input()
s2 = input()
 
print(LCS_iter(s1, s2))

Submission status: Accepted

Solution code:
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])
      
def fun(A,B,m,n,dp):
    for i in range(1,m+1):
        for j in range(1,n+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i][j-1],dp[i-1][j])
    return dp
                
def longestsub(A,B):
    m = len(A)
    n = len(B)
    if m==0 or n==0:
        return ""
    temp = [0]*(n+1)
    dp = [temp.copy() for i in range(m+1)]
    d = fun(A,B,m,n,dp)
    i= m;j = n;Ans = ""
    while i>0 and j>0:
        if A[i-1] == B[j-1]:
            Ans += A[i-1]
            i-=1;j-=1
        else:
            a = d[i][j-1] ; b =d[i-1][j]
            if a > b:
                j-=1
            else:
                i-=1
    return Ans[::-1]

A = input()
B = input()
print(longestsub(A,B))

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq

s = "0" + input()
t = "1" + input()

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

dp = [[0]*(m) for i in range(n)]

for i in range(n):
    dp[i][0] = 0
for j in range(m):
    dp[0][j] = 0

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

ans = ""
i = n-1
j = m-1
len = dp[n-1][m-1]

while len > 0:
    if s[i] == t[j]:
        ans += s[i]
        i -= 1
        j -= 1
        len -= 1
    elif dp[i][j-1] == dp[i][j]:
        j -= 1
    else:
        i -= 1

print(ans[::-1])

Submission status: Accepted

Solution code:
import sys
# input処理を高速化する
input = sys.stdin.readline
# 入力
S = input()
T = input()


def chmax(a, b):
    if a >= b:
        return a
    else:
        return b


def lcs(s, t):
    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] = chmax(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = chmax(dp[i + 1][j + 1], dp[i + 1][j])
            dp[i + 1][j + 1] = chmax(dp[i + 1][j + 1], dp[i][j + 1])
    ans = ''
    i = len(S)
    j = len(T)
    while (i > 0 and j > 0):
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            ans += s[i - 1]
            i -= 1
            j -= 1

    print(ans[::-1])


lcs(S, T)

Submission status: Accepted

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

for i in range(x):
	for j in range(y):
		if s[i]==t[j]:
			dp[i+1][j+1] = 1+dp[i][j]
		else:
			dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
i = x
j = y
ans = ''
while i*j!=0:
	if (dp[i][j] == 1 + dp[i-1][j-1]) and (s[i-1]==t[j-1]):
		ans = s[i-1] + ans
		i-=1
		j-=1
			
	else:	
		if dp[i][j] == dp[i-1][j]:
			i-=1
		elif dp[i][j] == dp[i][j-1]:
			j-=1

print(ans)

Submission status: Accepted

Solution code:
s = input()
t = input()
length_s = len(s)
length_t = len(t)

# dp[i+1][j+1] --> sのi文字目までとtのj文字までのLCSの長さ
dp = [[0] * 3005 for _ in range(3005)]

# DPループ
# LCSの長さを記録
for i in range(length_s):
    for j in range(length_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])

# DPテーブルからLCSの文字列を復元
res = ""
i = length_s
j = length_t
while i > 0 and j > 0:
    # (i-1, j) -> (i, j)と更新されていた場合
    if dp[i][j] == dp[i-1][j]:
        i -= 1 # DPの遷移を遡る
    
    # (i, j-1) -> (i, j)と更新されていた場合
    elif dp[i][j] == dp[i][j-1]:
        j -= 1 # DPの遷移を遡る

    # (i-1, j-) -> (i, j)と更新されていた場合
    else:
        # この時s[i-1] == t[j-1]なのでt[i-1] + resでも可
        res = s[i-1] + res
        i -= 1
        j -= 1

print(res)

Submission status: Accepted

Solution code:
# Author: S Mahesh Raju
# Username: maheshraju2020
# Date: 31/07/2020

from sys import stdin,stdout
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
mod = 1000000007

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

i, j = len(t), len(s)
res = ""
while i > 0 and j > 0:
    if s[j - 1] == t[i - 1]:
        res += s[j - 1]
        i -= 1
        j -= 1
    else:
        if dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:   
            j -= 1
print(res[::-1])

Submission status: Accepted

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	s, t = rll()[0], rll()[0]
	m, n = len(s), len(t)
	dp = [[0 for __ in range(n)] for _ in range(m)]
	dp[0][0] = 1 if s[0] == t[0] else 0
	for r in range(1, m):
		dp[r][0] = max(dp[r-1][0], 1 if s[r] == t[0] else 0)
	for c in range(1, n):
		dp[0][c] = max(dp[0][c-1], 1 if s[0] == t[c] else 0)
	for r in range(1, m):
		for c in range(1, n):
			dp[r][c] = max(dp[r-1][c], dp[r][c-1])
			if s[r] == t[c]:
				dp[r][c] = max(dp[r][c], 1 + dp[r-1][c-1])
	ans = deque()
	r, c = m-1, n-1
	while r >= 0 and c >= 0:
		if s[r] == t[c]:
			ans.appendleft(s[r])
			r -= 1
			c -= 1
		else:
			U = dp[r-1][c] if r > 0 else NINF
			L = dp[r][c-1] if c > 0 else NINF
			if L >= U:
				c -= 1
			else:
				r -= 1
	print("".join(x for x in ans))
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
def solve():
  ans = ''
  S = input()
  T = input()
  n,m = len(S),len(T)
  dp = [[0]*(m+1) for _ in range(n+1)]
  for i in range(1,n+1):
    for j in range(1,m+1):
      if S[i-1]==T[j-1]:
        dp[i][j] = dp[i-1][j-1]+1
      else:
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])
  i,j = n,m
  while i>0 and j>0:
    if dp[i-1][j]==dp[i][j]:
      i -= 1
    elif dp[i][j-1]==dp[i][j]:
      j -= 1
    else:
      ans = S[i-1]+ans
      i -= 1
      j -= 1
  return ans
print(solve())

Submission status: Accepted

Solution code:
def solve():
  ans = ''
  S = input()
  T = input()
  n,m = len(S),len(T)
  dp = [[0]*(m+1) for _ in range(n+1)]
  for i in range(1,n+1):
    for j in range(1,m+1):
      if S[i-1]==T[j-1]:
        dp[i][j] = dp[i-1][j-1]+1
      else:
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])
  i,j = n,m
  while i>0 and j>0:
    M = max([dp[i-1][j-1],dp[i][j-1],dp[i-1][j]])
    if dp[i-1][j-1]==M and M<dp[i][j]:
      ans = S[i-1]+ans
      i -= 1
      j -= 1
    elif dp[i-1][j]>=dp[i][j-1]:
      i -= 1
    else:
      j -= 1
  return ans
print(solve())

Submission status: Accepted

Solution code:
a=input()
b=input()
dp=[[0 for j in range(len(b)+1)] for i in range(len(a)+1)]
for i in range(len(a)):
    for j in range(len(b)):
        if a[i]==b[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])
s1=a
s2=b

# print(dp[len(s1)][len(s2)])
x=len(a)
y=len(b)
res=''
# print(dp[len(a)][len(b)])
while x>0 and y>0:
    if a[x-1]==b[y-1]:
        res+=a[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(res[::-1])

Submission status: Accepted

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(1,n+1):
    for j in range(1,m+1):
        if s[i-1]==t[j-1]:
            if i>0 and j>0:
                dp[i][j]=dp[i-1][j-1]+1
        else:
            if i>0:
                dp[i][j]=max(dp[i][j],dp[i-1][j])
            if j>0:
                dp[i][j]=max(dp[i][j],dp[i][j-1])
leng=dp[n][m]
i,j=n,m
ans=""
while leng>0:
    if s[i-1]==t[j-1]:
        ans+=s[i-1]
        i-=1
        j-=1
        leng-=1
    else:
        if dp[i-1][j]==dp[i][j]:
            i-=1
        elif dp[i][j-1]==dp[i][j]:
            j-=1
print(ans[::-1])

Submission status: Accepted

Solution code:
s=list(input())
t=list(input())
dp=[[0]*(len(s)+1) for i 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] + 1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# print(dp[len(t)][len(s)])
ans=""
i=len(t)
j=len(s)
while(i!=0 and j!=0):
    if(dp[i][j-1]<dp[i][j]>dp[i-1][j]):
        i-=1
        j-=1
        ans+=t[i]
    elif(dp[i][j]==dp[i-1][j]):
        i-=1
    elif(dp[i][j-1]==dp[i][j]):
        j-=1
print(ans[::-1])

Submission status: Accepted

Solution code:
from sys import stdin
s,t = stdin.readline().strip(),stdin.readline().strip()
dp = [[0]*len(s) for _ in range(len(t))]
maxi = [0]*len(s)
for i,val in enumerate(t):
    maxi1 = []
    for x in range(len(s)):
        if s[x] == val:
            dp[i][x] = (0 if x==0 else maxi[x-1])+1
        maxi1.append(max((0 if x==0 else maxi1[x-1]),dp[i][x]))
    for j in range(len(maxi)):
        maxi[j] = max(maxi[j],maxi1[j])
n = max(map(max,dp))
ans,i,j = [],len(t)-1,len(s)-1
while n:
    fl = 0
    for x in range(i,-1,-1):
        for y in range(j,-1,-1):
            if dp[x][y] == n:
                ans.append(s[y])
                fl = 1
                i,j = x-1,y-1
                break
        if fl:
            break
    n -= 1
print(''.join(ans[::-1]))

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

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

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

    dp = [[0 for _ in range(tl + 1)] for __ in range(sl + 1)]

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

    ans = ""
    x = sl
    y = tl
    while x > 0 and y > 0:
        if s[x - 1] == t[y - 1]:
            ans = s[x - 1] + ans
            x -= 1
            y -= 1
        elif dp[x][y] == dp[x][y - 1]:
            y -= 1
        elif dp[x][y] == dp[x - 1][y]:
            x -= 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

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

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

    dp = [[0 for _ in range(tl + 1)] for __ in range(sl + 1)]

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

    ans = ""
    x = sl
    y = tl
    while x > 0 and y > 0:
        if s[x - 1] == t[y - 1]:
            ans = s[x - 1] + ans
            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)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def resolve():
    import sys
    def max2(a: int, b: int):
        """
        入力された2つの整数a,bの大きいほうを返す
        Parameters
        ----------
        a, b : int
            比較したい整数
        Returns
        -------
        a or b : int
            大きいほうの整数
        """
        if a >= b:
            return a
        else:
            return b
    
    readline = sys.stdin.readline
 
    s = readline()
    t = readline()
 
    # 配るDP
    # dp[i + 1][j + 1]はsのi文字目までとtのj文字目までのLCSの長さ
    # LCS=最長共通部分列問題
    dp = [[0] * (len(t) + 1) for _ in [0] * (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] = max2(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i + 1][j])
            dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i][j + 1])
 
    # LCSを求めたDPから部分文字列を復元
    res = []
    i, j = len(s), len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res.append(s[i - 1])
            i -= 1
            j -= 1
    print(''.join(res[::-1]))
 
 
resolve()

Submission status: Accepted

Solution code:
s = input()
t = input()
S,T = len(s),len(t)
dp = [[0]*(T+1) for _ in range(S+1)]
for i in range(S):
    for j in range(T):
        if s[i]==t[j]:
            dp[i+1][j+1] = 1 + dp[i][j]
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
ans = ''
i,j = S,T
while dp[i][j]:
    if dp[i][j] ==dp[i][j-1]:
        j-=1
    elif dp[i][j] == dp[i-1][j]:
        i-=1
    else:
        ans = s[i-1] + ans
        i-=1
        j-=1
print(ans)

Submission status: Accepted

Solution code:
s1=input()
s2=input()
n1=len(s1)
n2=len(s2)
dp=[[0 for i in range(n2+1)] for j in range(n1+1)] 
for i in range(1,n1+1):
    for j in range(1,n2+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]) 
s=""
i,j=n1,n2
while dp[i][j]:
    if dp[i][j]==dp[i][j-1]:
        j-=1 
    elif dp[i][j]==dp[i-1][j]:
        i-=1 
    else:
        s=s1[i-1]+s
        i-=1 
        j-=1 
print(s)

Submission status: Accepted

Solution code:
import numpy as np
s = np.array(list(input().rstrip()))
t = np.array(list(input().rstrip()))
ls, lt = len(s), len(t)
dp = np.zeros((ls+1, lt+1), dtype=np.int64)

for i in range(1, ls+1):
  dp[i, 1:] = dp[i-1, :-1] + (s[i-1] == t)
  dp[i] = np.maximum(dp[i], dp[i-1])
  # print(dp[i])
  dp[i] = np.maximum.accumulate(dp[i])
  # print(dp[i])
answer = ''
x, y = lt, ls
while x > 0 and y > 0:
  # print(answer, x, y)
  if s[y-1] == t[x-1]:
    answer = s[y-1] + answer
    x, y = x-1, y-1
  elif dp[y, x] == dp[y, x-1]:
    x -= 1
  else:
    y -= 1
print(answer)

Submission status: Accepted

Solution code:
s = input()
t = input()
s_length = len(s)
t_length = len(t)

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

ans=""
i = s_length
j = t_length
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i-=1
    elif dp[i][j] == dp[i][j-1]:
        j-=1
    else:
        ans = s[i-1] + ans
        i-=1
        j-=1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)
    txt=""
    dp = [[0] * (lt + 1) for _ 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 - 1][j], dp[i][j - 1])

    while lt != 0 and ls != 0:
        if dp[ls][lt] == dp[ls - 1][lt]:
            ls -= 1
        elif dp[ls][lt] == dp[ls][lt - 1]:
            lt -= 1
        else:
            ls -= 1
            lt -= 1
            txt = txt +s[ls]

    print(txt[::-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

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(1,n+1):
    for j in range(1,m+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])
sna=[]
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
        sna.append(s[n])
ans=list(reversed(sna))
print("".join(ans))

Submission status: Accepted

Solution code:
# import sys
# input = sys.stdin.readline
s = input()
t = input()
m = len(s)
n = len(t)

D = [[0] * n for i in range(m)]
D[0][0] = int(s[0] == t[0])

for i in range(1, m):
    D[i][0] = D[i-1][0] | int(s[i] == t[0])
for i in range(1, n):
    D[0][i] = D[0][i-1] | int(s[0] == t[i])

for i in range(1, m):
    for j in range(1, n):
        mx = max(D[i-1][j-1],D[i-1][j],D[i][j-1])
        D[i][j] = max(mx, D[i-1][j-1]+1) if s[i] == t[j] else mx
# print(D)

maxl = max([max(D[i]) for i in range(m)])
# print(maxl)

ans = []
for i in range(m):
    for j in range(n):
        if D[i][j] == maxl:
            r = i
            c = j
            break

while maxl > 0:
    while c >= 1 and D[r][c-1] == maxl:
        c -= 1
    while r >= 1 and D[r-1][c] == maxl:
        r -= 1
    # print(r,c,maxl)
    ans.append(t[c])
    c -= 1
    r -= 1
    maxl -= 1
print("".join(ans[::-1]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
import sys
sys.setrecursionlimit(10**6)

s = input()
t = input()
N = len(s)
M = len(t)
ans = []

def print_lcs(dp,i,j):
    global ans
    if i == 0 or j == 0:
        return
    if s[i-1] == t[j-1]:
        print_lcs(dp,i-1,j-1)
        ans.append(s[i-1])
    else:
        if dp[i-1][j] >= dp[i][j-1]:
            print_lcs(dp,i-1,j)
        else:
            print_lcs(dp,i,j-1)


def main():
    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] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    
    print_lcs(dp,N,M)
    print(''.join(ans))

if __name__ == "__main__":
    main()