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:
import numpy as np
s = np.array(list(input()))
t = np.array(list(input()))
slen = len(s)
tlen = len(t)

dp = np.zeros((slen+1,tlen+1),dtype=int)

equal = (s[:,None] == t[None,:])
for i in range(slen):
    dp[i+1][1:] = np.maximum(dp[i][1:], dp[i][:-1] + equal[i])
    dp[i+1] = np.maximum.accumulate(dp[i+1])

ans = []
while dp[slen,tlen] != 0:
    if s[slen-1] == t[tlen-1]:
        ans.append(s[slen-1])
        slen -= 1
        tlen -= 1
    elif dp[slen,tlen] == dp[slen-1,tlen]:
        slen -= 1
    else:
        tlen -= 1
print("".join(ans[::-1]))

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] = dp[i][j]+1
        else:
            if dp[i+1][j] < dp[i][j+1]:
                dp[i+1][j+1] = dp[i][j+1]
            else:
                dp[i+1][j+1] = dp[i+1][j]

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

Submission status: Accepted

Solution code:
import numpy as np
def LCS(s,t,rec=False):
  S=np.array(list(s))
  T=np.array(list(t))
  LS,LT=len(S),len(T)
  dp=np.zeros((LS+1,LT+1))
  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])
  if rec:
    tmp=[]
    while LS>0 and LT>0:
      if S[LS-1]==T[LT-1]:
        LS,LT=LS-1,LT-1
        tmp.append(S[LS])
      elif dp[LS,LT]==dp[LS-1,LT]:
        LS-=1
      else:
        LT-=1
    return ''.join(reversed(tmp))
  else:
    return dp[LS][LT]
s=input()
t=input()
print(LCS(s,t,True))

Submission status: Accepted

Solution code:
s=input()
t=input()
ls=len(s)
lt=len(t)
INF=float('inf')

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

l=dp[ls][lt]
ans=''
i=ls
j=lt
while l>0:
  if s[i-1]==t[j-1]:
    ans=str(s[i-1])+ans
    l-=1
    i-=1
    j-=1
  elif dp[i][j]==dp[i-1][j]:
    i-=1
  else:
    j-=1
  
print(ans)

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):
    """compute table dp satisfying: 
    dp[i,j] = LCS(S[:i], T[:j])"""
    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:
from collections import deque

def mymax(a:int, b:int, c:int):
    if a > b:
        if c > a:
            return c
        else:
            return a
    else:
        if c > b:
            return c
        else:
            return b


def main():
    s = input()
    t = input()
    lens = len(s)
    lent = len(t)
    dp = [[0] * (lent+1) for _ in range(lens+1)]


    for i in range(1, lens + 1):
        for j in range(1, lent + 1):
            dp[i][j] = mymax(
                dp[i-1][j-1] + (s[i-1] == t[j-1]),
                dp[i-1][j],
                dp[i][j-1]
            )
    
    string = deque([])
    i = lens; j = lent
    for _ in range(lens+lent+1):
        if s[i-1] == t[j-1]:
            string.appendleft(s[i-1])
            i -= 1
            j -= 1
        else:
            if dp[i-1][j] > dp[i][j-1]:
                i -= 1
            else:
                j -= 1
        if i <= 0 or j <= 0:
            break
    print(''.join(string))

if __name__ == "__main__":
    main()

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(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 = ''
n,m = s,t
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:
    ans = S[n-1] + ans
    n -= 1
    m -= 1
print(ans)

Submission status: Accepted

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count


def ifvalid(i):
    if i < 0:
        return False
    return True


def solve():
    s = inp()
    t = inp()
    a = len(s)
    b = len(t)
    dp = [[0 for _ in range(b + 5)] for i in range(a + 5)]
    for i in range(1, a + 1):
        for j in range(1, b + 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 = a
    j = b
    ans = ""
    while (i > 0 and j > 0):
        if s[i - 1] == t[j - 1]:
            ans += s[i - 1]
            i -= 1
            j -= 1
        else:
            if dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1
    print(ans[::-1])


solve()

Submission status: Accepted

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

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

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

while i>0 and j>0:
    if s[i-1]==t[j-1]:
        ans.append(s[i-1])
        i -= 1
        j -= 1
    else:
        if dp[i-1][j]>dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    
ans.reverse()
print(''.join(ans))

Submission status: Accepted

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

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

for i in range(1, len(s) + 1):
    for j in range(1, len(t) + 1):
        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 = [0] * length
i = len(s)
j = len(t)
while length > 0:
    if s[i - 1] == t[j - 1]:
        ans[length - 1] = s[i - 1]
        length -= 1
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1

print(''.join(ans))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10**7)
s,t=input(),input()
dp=[[0]*(len(t)+1) for i in range(len(s)+1)]
for i in range(len(s)+1):
    for j in range(len(t)+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])
        if i<len(s) and j<len(t):
            dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+(s[i]==t[j]))
ans=""
def move(i,j):
    global dp,ans
    if i==0 or j==0:
        return
    elif dp[i][j]>dp[i-1][j-1] and s[i-1]==t[j-1]:
        ans=s[i-1]+ans
        move(i-1,j-1)
    else:
        if dp[i][j]==dp[i][j-1]:
            move(i,j-1)
        else:
            move(i-1,j)
move(len(s),len(t))
print(ans)

Submission status: Accepted

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


dp=[[0 for i in range(a+1)] for j in range(b+1)]
for i in range(b+1):
	for j in range(a+1):
		if(i==0 or j==0):
			continue
		if(t[i-1]==s[j-1]):
			dp[i][j]=1+dp[i-1][j-1]
		else:
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])
i=b
j=a
l=[]
while(i>0 and j>0):
	if(t[i-1]==s[j-1]):
		l.append(t[i-1])
		i=i-1
		j=j-1
	else:
		if(dp[i-1][j]>dp[i][j-1]):
			i=i-1
		else:
			j=j-1
for i in reversed(l):
    print(i,end='')

Submission status: Accepted

Solution code:
s1 = input()
s2 = input()
arra = ["-"]
arrb = ["-"]
for i in s1:
    arra.append(i)
for i in s2:
    arrb.append(i)
n1 = len(s1)
n2 = len(s2)
temparr = [0 for i in range(n2 + 1)]
dp = [temparr[::] for i in range(n1 + 1)]

for i in range(1, n1 + 1):
    for j in range(1 , n2 + 1):
        if arra[i] != arrb[j]:
            dig = dp[i -1][j-1]
            upp = dp[i - 1][j]
            left = dp[i][j - 1]
            dign = dig
            uppn = upp
            leftn = left
            if dign >= uppn and dign >= leftn:
                dp[i][j] = dig
            elif uppn >= dign and uppn >= leftn:
                dp[i][j] = upp
            else:
                dp[i][j] = left
        else:
            dig = dp[i -1][j-1]
            upp = dp[i - 1][j]
            left = dp[i][j - 1]
            dig = dig + 1
            #print(dig)
            
            dign = dig
            uppn = upp
            leftn = left
            if dign >= uppn and dign >= leftn:
                dp[i][j] = dig
            elif uppn >= dign and uppn >= leftn:
                dp[i][j] = upp
            else:
                dp[i][j] = left

# for i in dp:
#     print(i) 
ans = ""

while n2 != 0 and n1 != 0 :
    
    if arra[n1] == arrb[n2]:
        ans += arra[n1]
        n2 -= 1 
        n1 -= 1 
        continue 
    else:
        if dp[n1 - 1][n2] >= dp[n1][n2 - 1]:
            n1 -= 1 
        else:
            n2 -=1 
print(ans[::-1])

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(1, len(a)+1):
    for j in range(1, len(b)+1):
        if a[i-1] == b[j-1] :
            dp[i][j] = dp[i-1][j-1] + 1
            continue
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
m = dp[-1][-1]
ans = ''
i,j=-1,-1
while(len(ans)<m):
    if a[i] == b[j]:
        ans = a[i] + ans
        i-=1
        j-=1
    elif dp[i-1][j] > dp[i][j-1]:
        i-=1
    else:
        j-=1
print(ans)

Submission status: Accepted

Solution code:
'''
from sys import stdin, setrecursionlimit as srl
from threading import stack_size, Thread
srl(int(1e9)+7)
stack_size(int(1e8))

def solve():
    t = int ( input () )
    for _ in range ( t ) :
        


Thread(target=solve).start()
solve()
'''

a = input()
b = input()
dp = [[0 for j in range(len(b)+1)] for i in range(len(a)+1)]
for i in range(1, len(a)+1):
    for j in range(1, len(b)+1):
        if a[i-1] == b[j-1] :
            dp[i][j] = dp[i-1][j-1] + 1
            continue
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
m = dp[-1][-1]
ans = ''
i,j=-1,-1
while(len(ans)<m):
    if a[i] == b[j]:
        ans = a[i] + ans
        i-=1
        j-=1
    elif dp[i-1][j] > dp[i][j-1]:
        i-=1
    else:
        j-=1
print(ans)

Submission status: Accepted

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

l1,l2 = len(s),len(t)

dp = [[0]*(l2+1) for _ in range(l1+1)]
memo = [['']*(l2+1) for _ in range(l1+1)]

for i in range(1,l1+1):
  for j in range(1,l2+1):
    if s[i-1]==t[j-1]:
      dp[i][j] = dp[i-1][j-1] + 1
      memo[i][j] = s[i-1]
    else:
      if dp[i-1][j] >= dp[i][j-1]:
        dp[i][j] = dp[i-1][j]
        memo[i][j] = (i-1,j)
      else:
        dp[i][j] = dp[i][j-1]
        memo[i][j] = (i,j-1)
      
i,j = l1,l2
ans = []
while i > 0 and j > 0:
  if len(memo[i][j]) == 2:
    i, j = memo[i][j]
  else:
    ans.append(memo[i][j])
    i, j = i-1, j-1
    
print(''.join(ans[::-1]))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
def main():
    s=tuple(input())
    t=tuple(input())
    n=len(s)
    m=len(t)
    dp=[[0 for i in range(m+1)] for j 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:
                if dp[i+1][j]>dp[i][j+1]:
                    dp[i+1][j+1]=dp[i+1][j]
                else:
                    dp[i+1][j+1]=dp[i][j+1]
    p=dp[n][m]
    ans=['' for _ in range(p)]
    n-=1
    m-=1
    while p>0:
        if s[n]==t[m]:
            ans[p-1]=s[n]
            n-=1
            m-=1
            p-=1
        elif dp[n+1][m+1]==dp[n][m+1]:
            n-=1
        else:
            m-=1
    print(''.join(ans)) 
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from subprocess import*
call(('pypy3','-c',"""
s=input()
t=input()
a=len(s)
b=len(t)
dp=[[0]*(b+1) for i in range(a+1)]
for i in range(a):
  for j in range(b):
    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])
res=''
while a!=0 and b!=0:
  if dp[a][b]==dp[a-1][b]:
    a-=1
  elif dp[a][b]==dp[a][b-1]:
    b-=1
  else:
    a-=1
    b-=1
    res=s[a]+res
print(res)
"""))
"""
from subprocess import*
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
# import numpy as np
starttime = time.time()
# import numpy as np
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    # sys.setrecursionlimit(int(pow(10,6)))
    # sys.stdin = open("input.txt", "r")
    # sys.stdout = open("../output.txt", "w")
except:
    pass

"""

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.buffer.readline

'''
dp[i,j]=部分文字列が一致する最長 s[:i],t[:j]文字目まで考慮したとき

chmax(dp[i+1,j],dp[i,j])
chmax(dp[i,j+1],dp[i,j])
if s[i]==t[j]:
    chmax(dp[i+1,j+1],dp[i,j]+1)

完成したdpテーブルの終端からからやればおk
s[i]とv[j]が同じ文字だったら斜め上(i-1,j-1)にもどってそれ以外はdp[i-1,j]ordp[i,j-1]のうちにdp[i,j]と値が同じ方に戻ることにする
'''

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)

S = array(list(read()[:-1]))
T = array(list(read()[:-1]))

from numba import njit


@njit('(i8[:],i8[:],)', cache=True)
def solve(S, T):
    s = len(S)
    t = len(T)
    dp = np.zeros((len(S) + 1, len(T) + 1))
    for i in range(1, s + 1):
        for j in range(1, t + 1):
            dp[i, j] = max(dp[i, j], dp[i - 1, j])
            dp[i, j] = max(dp[i, j], dp[i, j - 1])
            if S[i - 1] == T[j - 1]:
                dp[i, j] = max(dp[i, j], dp[i - 1, j - 1] + 1)
    # 以下復元
    i, j = s, t
    ans = []
    while dp[i, j] != 0:
        if S[i - 1] == T[j - 1]:
            ans.append(S[i - 1])
            i -= 1
            j -= 1
            continue
        if dp[i, j] == dp[i - 1, j]:
            i -= 1
        else:
            j -= 1
    return ans


ret = solve(S, T)
print(''.join(map(chr, ret[::-1])))

Submission status: Accepted

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

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

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

ans = ''

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

print(ans[::-1])

Submission status: Accepted

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

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

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

x_index=len(t)-1
y_index=len(s)-1

if  dp[y_index][x_index]==0:
    print()
    exit()

while True:
    if t[x_index]==s[y_index]:
        ans.append(t[x_index])
        if dp[y_index][x_index]==1:
            break
        else:
            x_index-=1
            y_index-=1
            continue

    else:
        if dp[y_index][x_index]==dp[y_index][x_index-1]:
            x_index-=1
        else:
            y_index-=1


X=reversed(ans)
print(''.join(X))

Submission status: Accepted

Solution code:
import sys


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


S = input()
T = input()
dp = [[0]*(len(T)+1) for j in range(len(S)+1)]
# dp[i][j] := i,j までの最大のもの。(length)
for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            dp[i+1][j+1] = dp[i][j]+1
        else:
            if dp[i+1][j] >= dp[i][j+1]:
                dp[i+1][j+1] = dp[i+1][j]

            elif dp[i+1][j] < dp[i][j+1]:
                dp[i+1][j+1] = dp[i][j+1]
X, Y = len(S), len(T)
ans = []
while dp[X][Y]:
    if S[X-1] == T[Y-1]:
        ans.append(S[X-1])
        X -= 1
        Y -= 1
    else:
        if dp[X-1][Y] >= dp[X][Y-1]:
            X -= 1
        else:
            Y -= 1
            continue
ans.reverse()
print("".join(ans))

Submission status: Accepted

Solution code:
s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for j in range(m+1)] for i 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=n
j=m
st=""
while dp[i][j]:
	while dp[i-1][j]==dp[i][j]:
		i-=1
	while dp[i][j-1]==dp[i][j]:
		j=j-1
	j-=1
	st+=s[i-1]
	i-=1
print(st[::-1])

Submission status: Accepted

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

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

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

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

ans=''

i=m
j=n
while i>0 and j>0:
    if s[i-1]==t[j-1]:
        ans=str(s[i-1])+ans
    i,j=trans[i][j]

print(ans)

Submission status: Accepted

Solution code:
s = input()
t = input()
ns = len(s)
nt = len(t)

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

ans = []
i, j = ns, nt
while dp[i][j]:
    while dp[i - 1][j] == dp[i][j]:
        i -= 1
    while dp[i][j - 1] == dp[i][j]:
        j -= 1
    ans.append(s[i - 1])
    i -= 1
    j -= 1
ans.reverse()
print("".join(ans))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:


INF = float('inf')


def tc():
    s = input()
    t = input()
    n, m = len(s), len(t)

    # dp[i][j] = LCS so far up to pos i in s and pos j in 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 chars are the same, use them both
                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
    ans = ''
    while dp[i][j]:
        me = dp[i][j]
        l = dp[i][j - 1]
        u = dp[i - 1][j]
        d = dp[i - 1][j - 1]
        if d > l and d > u:
            ans += s[i - 1]
            i -= 1
            j -= 1
        elif d == l and d == u:
            if d < me:
                ans += s[i - 1]
                i -= 1
                j -= 1
            else:
                i -= 1
        elif l >= u:
            j -= 1
        elif u > l:
            i -= 1

    print(''.join(reversed(ans)))


tc()

Submission status: Accepted

Solution code:
def lcs(S, T):
    dp = [[0]*(len(T)+1) for _ in range(len(S)+1)]
    for i in range(1,len(S)+1):
        for j in range(1,len(T)+1):
            dp[i][j] = max(dp[i][j-1], dp[i-1][j], dp[i-1][j-1] + (S[i-1]==T[j-1]))

    res = []
    x,y = len(S),len(T)
    v = dp[x][y]
    while v > 0:
        if dp[x-1][y] == v:
            x -= 1
        elif dp[x][y-1] == v:
            y -= 1
        else:
            res.append(S[x-1])
            x -= 1
            y -= 1
        v = dp[x][y]
    return ''.join(reversed(res))

####################################################################################################################
import sys
input = sys.stdin.readline

S,T = input(),input()
print(lcs(S,T))

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def LCS(S, T, f=False):

    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

    if not f:
        return 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 (dp[0][0], ''.join(res))


def main():

    s = in_s()
    t = in_s()

    _, ans = LCS(s, t, True)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

def longest_common_subsequence(S, T):
    """compute table dp satisfying: 
    dp[i,j] = LCS(S[:i], T[:j])"""
    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 and j:
        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, t = np.array(list(input())), np.array(list(input()))

print(reconstruct_LCS(s, t, longest_common_subsequence(s, t)))

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
s=SI()
t=SI()
a=len(s)
b=len(t)
dp=[[0]*(a+1) for i in range(b+1)]
for i in range(1,b+1):
    for j in range(1,a+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])
ans=[]
i,j=b,a
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:
        ans.append(s[j-1])
        i -= 1
        j -= 1
#print(ans)
for x in list(reversed(ans)):
    print(x,end="")

Submission status: Accepted

Solution code:
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

ans = []

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:
        ans.append(s[i-1])
        i -= 1
        j -= 1

print("".join(reversed(ans)))