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 sys
input = sys.stdin.readline

def main():
    s=input()
    t=input()
    sl,tl=len(s),len(t)
    lcs=[[0]*(tl+1) for _ in range(sl+1)]
    for i in range(1,sl+1):
        for j in range(1,tl+1):
            if s[i-1]==t[j-1]:
                lcs[i][j]=lcs[i-1][j-1]+1
            else:
                lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1])
    k = lcs[i][j]
    r = ''
    while k:
        if lcs[i - 1][j] == k:
            i -= 1
        elif lcs[i][j - 1] == k:
            j -= 1
        else:
            k -= 1
            i -= 1
            j -= 1
            r += s[i]
    print(r[::-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

ans = ""
n = dp[-1][-1]
i = len(s)
j = len(t)
while n > 0:
    if dp[i][j] == dp[i-1][j]:
        i -=1
    elif dp[i][j] == dp[i][j-1]:
        j -=1
    elif dp[i][j] == dp[i-1][j-1] + 1:
        ans = s[i-1] + ans
        n -= 1
        i -= 1
        j -= 1

print(ans)

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_f
s = str(input())
t = str(input())
dp = [[0 for _ in range(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
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j], 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] + ans
        i -= 1
        j -= 1

print(ans)

Submission status: Accepted

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


def lcs(s, t)->list:
    sn = len(s)
    tn = len(t)
    dp = [[0 for _ in range(tn+1)] for _ in range(sn+1)]
    for i in range(sn):
        for j in range(tn):
            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], dp[i][j+1])
    #[print(val) for val in dp]
    return dp


def restore_str(lcs_dp)->str:
    restore = str()
    i = len(s)
    j = len(t)

    while i > 0 and j > 0:
        #print(i, j, restore, lcs_dp[i])
        if lcs_dp[i][j] == lcs_dp[i-1][j]: i -= 1
        elif lcs_dp[i][j] == lcs_dp[i][j-1]: j -= 1
        else: 
            restore = s[i-1] + restore
            i -= 1
            j -= 1

    return restore


def main():
    lcs_dp = lcs(s, t)
    ans = restore_str(lcs_dp)
    return print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def lcs(s, t)->list:
    sn = len(s)
    tn = len(t)
    dp = [[0 for _ in range(tn+1)] for _ in range(sn+1)]
    for i in range(sn):
        for j in range(tn):
            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+1][j], dp[i][j+1])
    #print(dp)
    return dp


def restore_str(lcs_dp)->str:
    restore = str()
    i = len(s)
    j = len(t)

    while i > 0 and j > 0:
        #print(i, j)
        if lcs_dp[i][j] == lcs_dp[i-1][j]: i -= 1
        elif lcs_dp[i][j] == lcs_dp[i][j-1]: j -= 1
        else: 
            restore = s[i-1] + restore
            i -= 1
            j -= 1

    return restore


def main():
    lcs_dp = lcs(s, t)
    ans = restore_str(lcs_dp)
    return print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# DP
dp = [[0] * (len(t) + 1) for i 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], dp[i][j + 1], dp[i][j] + 1)
    else:
      dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
      
#lcs = dp[len(s)][len(t)]

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

  if dp[i][j] > dp[i - 1][j] and dp[i][j] > dp[i][j - 1]:
    ans += s[i - 1]
    i -= 1
    j -= 1

ans = ''.join(list(reversed(ans)))
print(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(len(s)):
    dp[i][0] = 0
for j in range(len(t)):
    dp[0][j] = 0
for i in range(0, len(s)):
    for j in range(0, 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 + 1][j], dp[i][j + 1])
i = len(s)
j = len(t)
ans = ''
while True:
    if s[i - 1] == t[j - 1]:
        ans = s[i - 1] + ans
        i -= 1
        j -= 1
    if dp[i][j] == dp[i][j - 1]:
        j -= 1
    elif dp[i][j] == dp[i - 1][j]:
        i -= 1
    if i <= 0 or j <= 0:
        break
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def main():
    s = np.array([str(i) for i in input()], dtype=np.unicode)
    t = np.array([str(i) for i in input()], dtype=np.unicode)

    num_s = int(s.shape[0])
    num_t = int(t.shape[0])


    dp = np.zeros((num_s +1, num_t +1), dtype='int64')

    eq = s[:,None] == t[None,:]
    # print(len(eq[0]))

    for i in range(num_s):
        np.maximum(dp[i, 1:], dp[i, :-1] + eq[i], out=dp[i+1, 1:])
        np.maximum.accumulate(dp[i+1], out=dp[i+1])
    # print(dp)

    res=''
    pos_s = num_s
    pos_t = num_t


    while len(res) < np.max(dp[num_s]):
        temp = dp[pos_s, pos_t]
        # print(temp)
        if dp[pos_s-1, pos_t] == temp:
            pos_s -= 1

        if dp[pos_s, pos_t-1] == temp:
            pos_t -= 1

        if s[pos_s - 1] == t[pos_t - 1]:
            res += s[pos_s-1]
            pos_s -= 1
            pos_t -= 1

        # print(res, pos_s-1)
        
    print(res[::-1])

main()

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

# @profile
def calc_lcs(s, t):
  dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
  # dp = numpy.zeros((len(s)+1, len(t)+1))
  for i, si in enumerate(s, 1):
    for j, tj in enumerate(t, 1):
      dp[i][j] = max((dp[i-1][j-1] + 1) if si==tj else 0, dp[i-1][j], dp[i][j-1])

  lcs = ''
  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:
      lcs = s[i-1] + lcs
      i -= 1
      j -= 1
  return lcs

def main():
  s = input().strip()
  t = input().strip()
  print(calc_lcs(s, t))


if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
a = input()
b = input()
dp = [[0]*(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] = 1 + dp[i-1][j-1]
    else:
      dp[i][j] = max(dp[i][j-1], dp[i-1][j])
#print(dp)
ans = []
p = len(a)
t = len(b)
while p>0 and t>0:
  if a[p-1] == b[t-1]:
    ans.insert(0, a[p-1])
    p = p-1
    t = t-1
  else:
    if dp[p][t-1] > dp[p-1][t]:
      t = t-1
    else:
      p = p-1
print("%s" % ''.join(ans))

Submission status: Accepted

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

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

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

i = lt
j = ls
while i-1>=0 and j-1>=0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
        continue
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
        continue
    else:

        i -= 1
        j -= 1
        ans = s[j] + ans

print(ans)

Submission status: Accepted

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

    s = readline().rstrip()
    t = readline().rstrip()

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

    for i, si in enumerate(s, 1):
        for j, tj in enumerate(t, 1):
            if si == tj:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    rest = dp[len(s)][len(t)]

    ret = ''
    i, j = len(s), len(t)

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

        # dp[i][j] == dp[i - 1][j - 1] + 1
        # かどうかを先に調べると、dp[i-1]/dp[j-1]のいずれかで既に+1になっているケースで間違う？

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
mem_i = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]
mem_j = [[0 for _ in range(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
            mem_i[i][j] = i - 1
            mem_j[i][j] = j - 1
        else:
            dp[i][j] = max(
                dp[i - 1][j],
                dp[i][j-1]
            )

            if dp[i - 1][j] < dp[i][j - 1]:
                mem_i[i][j] = i
                mem_j[i][j] = j - 1
            else:
                mem_i[i][j] = i - 1
                mem_j[i][j] = j

i = len(s)
j = len(t)

result = []
while (i > 0 and j > 0):
    prev_i = mem_i[i][j] 
    prev_j = mem_j[i][j]
    if prev_i == i - 1 and prev_j == j - 1:
        _s = s[prev_i]
        result.append(_s)
    i = prev_i
    j = prev_j

print("".join(result[::-1]))

Submission status: Accepted

Solution code:
import sys

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


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

def main():
	s=input().rstrip().decode('utf-8')
	t=input().rstrip().decode('utf-8')
	slen=len(s)
	tlen=len(t)
	
	dp=[[0]*(slen+1) for _ in range(tlen+1)]
	pr=[[0]*(slen+1) for _ in range(tlen+1)]
	
	
	for i in range(tlen):
		for j in range(slen):
			if s[j]==t[i]:
				dp[i+1][j+1]=dp[i][j]+1
				pr[i+1][j+1]=1
			elif dp[i][j+1]<dp[i+1][j]:
				dp[i+1][j+1]=dp[i+1][j]
				pr[i + 1][j + 1] = 2
			else:
				dp[i+1][j+1]=dp[i][j+1]
				pr[i + 1][j + 1] = 3
	
	ss=slen
	tt=tlen
	ans=""
	while ss>0 and tt>0:
		if pr[tt][ss]==1:
			ans+=s[ss-1]
			tt-=1
			ss-=1
		elif pr[tt][ss]==2:
			ss-=1
		else:
			tt-=1
	print(ans[::-1])
	
	
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

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

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

for i in range(0,S):
    for j in range(0,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])
#print(dp)
i, j = S, T
ans = ""
while i > 0 and j > 0:
    if dp[i][j] ==dp[i-1][j]:
        # (i-1, j) -> (i, j)
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        # (i, j-1) -> (i, j)
        j -= 1
    else:
        # (i-1, j-1) -> (i, j)
        ans = s[i-1] + ans
        i -= 1; j -= 1

print(ans)

Submission status: Accepted

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

t_len = len(t)
s_len = len(s)

dp = [[0]*(t_len+1) for _ in range(s_len+1)]

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

#print(dp[s_len][t_len])

s_len_tmp = s_len
t_len_tmp = t_len
ans = ''

while s_len_tmp > 0 and t_len_tmp > 0:
    if dp[s_len_tmp][t_len_tmp] == dp[s_len_tmp-1][t_len_tmp]:
        s_len_tmp -= 1
    elif dp[s_len_tmp][t_len_tmp] == dp[s_len_tmp][t_len_tmp-1]:
        t_len_tmp -= 1
    else:
        ans += s[s_len_tmp-1]
        s_len_tmp -= 1
        t_len_tmp -= 1
   
print(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:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

ans = ""

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:
        ans = s[i-1] + ans
        i -= 1
        j -= 1

print(ans)

Submission status: Accepted

Solution code:
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)):
    for j in range(len(t)):
        dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j],dp[i][j]+(s[i]==t[j]))
        
st=[]
x=len(s)
y=len(t)
while x>0 and y>0:
    if dp[x][y] == dp[x-1][y]:
        x-=1
    elif dp[x][y] ==dp[x][y-1]:
        y-=1
    else:
        x-=1
        y-=1
        st += s[x]
print(''.join(reversed(st)))

Submission status: Accepted

Solution code:
S = input()
T = input()
#dp[i][j]をs,tをそれぞれ右からi,j番目まで見た時の最大の部分列の長さとする。
lenS = len(S)
lenT = len(T) 
memo = []
dp = [[0]*(lenS+1) for _ in range(lenT+1)]
for i in range(1,lenT+1):
    for j in range(1,lenS+1):
        if S[j-1] == T[i-1]:
            dp[i][j] = max(dp[i-1][j-1]+1,dp[i][j-1],dp[i-1][j])
        else:
            dp[i][j] = max(dp[i][j-1],dp[i-1][j])
 
#dpから最澄列を復元する。
ans = ""
s = lenS
t = lenT
while s>0 and t>0:
    if S[s-1] == T[t-1]:
        ans += S[s-1]
        s -= 1
        t -= 1
    else:
        if dp[t][s-1] > dp[t-1][s]:
            s -= 1
        else:
            t -= 1
print(ans[::-1])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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

def main():
  s=S()
  t=S()

  lns=len(s)
  lnt=len(t)

  dp=[[0 for _ in range(lns+1)]for _ in range(lnt+1)]
  for i in range(lnt):
    for j in range(lns):
      if t[i]==s[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=lnt
  j=lns
  while dp[i][j]!=0:
    if dp[i][j]==dp[i-1][j]:
      i-=1
    elif dp[i][j]==dp[i][j-1]:
      j-=1
    elif dp[i][j]==dp[i-1][j-1]:
      i-=1
      j-=1
    elif dp[i][j]==dp[i-1][j-1]+1:
      ans=t[i-1]+ans
      i-=1
      j-=1

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    S=input()
    T=input()
    dp=[[0]*(len(T)+1) for _ in range(len(S)+1)]
    dp2=[[()]*(len(T)+1) for _ in range(len(S)+1)]
    for s in range(len(S)):
        for t in range(len(T)):
            if S[s]==T[t]:
                dp[s+1][t+1]=dp[s][t]+1
                dp2[s+1][t+1]=(s,t)
            else:
                if dp[s+1][t]>dp[s][t+1]:
                    dp[s+1][t+1]=dp[s+1][t]
                    dp2[s+1][t+1]=dp2[s+1][t]
                else:
                    dp[s+1][t+1]=dp[s][t+1]
                    dp2[s+1][t+1]=dp2[s][t+1]
    tmp=dp2[len(S)][len(T)]
    if tmp:
        ans=deque()
        ans.appendleft(S[tmp[0]])
        for _ in range(dp[len(S)][len(T)]-1):
            tmp=dp2[tmp[0]][tmp[1]]
            ans.appendleft(S[tmp[0]])
        print(''.join(ans))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

for i in range(n):
 for j in range(m):

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

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

ans=''
while n>0 and m>0:
 if dp[n][m]==dp[n-1][m]:
  n-=1
 elif dp[n][m]==dp[n][m-1]:
  m-=1
 else:
  m-=1
  n-=1
  ans=s[n]+ans

print(ans)

Submission status: Accepted

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

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

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

for i in range(n-1):
 for j in range(m-1):

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

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

n-=1
m-=1

ans=''
while n>0 and m>0:
 if dp[n][m]==dp[n-1][m]:
  n-=1
 elif dp[n][m]==dp[n][m-1]:
  m-=1
 else:
  m-=1
  n-=1
  ans=s[n]+ans

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    S = Scanner.string()
    T = Scanner.string()
    dp = [[0 for _ in range(3100)] for _ in range(3100)]
    for i in range(len(S)):
        for j in range(len(T)):
            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])
            if S[i] == T[j]:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
    ans = ""
    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:
            ans = S[i-1] + ans
            i -= 1
            j -= 1
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
s = input()
t = input()
S = len(s)
T = len(t)
dp=[[-1]*(T+1) for _ in range(S+1)]

for i in range(S+1):
    for j in range(T+1):
        if i==0 or j==0:
            dp[i][j] = 0

#まずは求める部分文字列の長さを求める
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])

#print(dp[-1][-1])
ans=""
i=S
j=T
while  dp[i][j]!=0:
    if 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
        else:
            j-=1

print(ans)

Submission status: Accepted

Solution code:
s = input()
t = input()
LENs = len(s)
LENt = len(t)
dp = [[0 for i in range(LENt+1)] for j in range(LENs+1)]
for i in range(LENs+1):
    for j in range(LENt+1):
        if i+1 <= LENs:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if j+1 <= LENt:
            dp[i][j+1] = max(dp[i][j+1],dp[i][j])
        if i+1 <= LENs and j+1<=LENt:
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+1

ans = ''
x = LENs
y = LENt
while True:
    if len(ans)==dp[-1][-1]:
        break
    if dp[x-1][y] ==dp[x][y]:
        x = x-1
    elif dp[x][y] == dp[x][y-1]:
        y = y-1
    elif dp[x-1][y-1]+1== dp[x][y]:
        ans =s[x-1] + ans
        x = x-1
        y = y-1
        continue
#     elif dp[x-1][y] == dp[x][y-1]:
#         x = x-1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
s = input()
t = input()
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

def backtrack(dp, s, t, i, j):
    if i == 0 or j == 0:
        return ''
    if s[i-1] == t[j-1]:
        return backtrack(dp, s, t, i-1, j-1) + s[i-1]
    if dp[i][j-1] > dp[i-1][j]:
        return backtrack(dp, s, t, i, j-1)
    return backtrack(dp, s, t, i-1, j)

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

Submission status: Accepted

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

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

for i, si in enumerate(s):
    table_pre = table[i]
    table_cur = table[i + 1]
    for j, tj in enumerate(t):
        if si == tj:
            table_cur[j + 1] = table_pre[j] + 1
        else:
            table_cur[j + 1] = max(table_cur[j], table_pre[j + 1])

ls, lt = len(s), len(t)
ans = ''
while ls and lt:
    if table[ls][lt] == table[ls][lt - 1]:
        lt -= 1
    elif table[ls][lt] == table[ls - 1][lt]:
        ls -= 1
    else:
        ans = s[ls - 1] + ans
        ls -= 1
        lt -= 1
print(ans)

Submission status: Accepted

Solution code:
INF = 10**10 - 1 #無限大
SMAX = 3000 + 10

# 文字列入力
s1 = input()
s2 = input()

'''
dpの初期化
s1の文字列位置を一次軸、s2の文字列位置を二次軸に取り
その値として：LCSの最長値として更新していく
　　　　　　　初期値はすべて０
'''
dp = [ [0] * (SMAX) for i in range(SMAX)]

for s1pos in range(1,len(s1)+1):
    s1s = s1[s1pos-1:s1pos]
    for s2pos in range(1,len(s2)+1):
        s2s = s2[s2pos-1:s2pos]
        if s1s == s2s:
            dp[s1pos][s2pos] = dp[s1pos-1][s2pos-1] + 1
        dp[s1pos][s2pos] = max(dp[s1pos][s2pos],dp[s1pos][s2pos-1],dp[s1pos-1][s2pos])
    #print("s1pos=",s1pos,"dp=",dp[s1pos])

#print("LCS_len",dp[len(s1)][len(s2)])

res = ""
s1pos = len(s1)
s2pos = len(s2)
while (s1pos > 0 and s2pos > 0):
    # (s1pos-1, s2pos) -> (s1pos, s2pos) と更新されていた場合
    if (dp[s1pos][s2pos] == dp[s1pos-1][s2pos]):
        s1pos -= 1 # DP の遷移を遡る
    # (s1pos, s2pos-1) -> (s1pos, s2pos) と更新されていた場合
    elif (dp[s1pos][s2pos] == dp[s1pos][s2pos-1]):
        s2pos -= 1 # DP の遷移を遡る
    # (s1pos-1, s2pos-1) -> (s1pos, s2pos) と更新されていた場合
    else:
        res = s1[s1pos-1:s1pos] + res # 該当文字を取得
        s1pos -= 1 # DP の遷移を遡る
        s2pos -= 1 # DP の遷移を遡る

print(res)

Submission status: Accepted

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

def solve(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

    # 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(solve(s,t))

Submission status: Accepted

Solution code:
# LCSとその復元
S = input()
T = input()

# 最長共通部分列の長さを求める
dp = [[0] * (len(T)+1) for _ in range(len(S)+1)]

for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:  # 今見ている文字が等しいのであれば斜めに移動する
            dp[i+1][j+1] = dp[i][j]+1
        else:  # 異なるのであれば、上または左の値の大きい方をコピーする
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
# print(dp)
ans = ''
n = len(S)
m = len(T)
while n != 0 and m != 0:  # どちらかが先頭まで来たら終わり
    if dp[n][m] == dp[n-1][m]:  # Sのn文字目が関係ない文字ならn-1文字目を見にいく
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    else:
        # 斜めから移動されているところに注目する
        n -= 1
        m -= 1
        # 前に追加していくからこう書く
        ans = S[n] + ans
print(ans)

Submission status: Accepted

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

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

print(ans[::-1])

Submission status: Accepted

Solution code:
def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            if dp[i+k]>dp[i]+abs(H[i+k]-H[i]):
                dp[i+k] = dp[i]+abs(H[i+k]-H[i])
    ans = dp[-1]
    print(ans)
    return

def examC():
    N = I()
    A = [0]*N; B = [0]*N; C = [0]*N
    for i in range(N):
        A[i],B[i],C[i] = LI()
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + A[i]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
    ans = max(dp[N])
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    # https://mzp.hatenadiary.org/entry/20100623/lcs
    # LCS
    def maxBy(f, x, y):
        if f(x) > f(y):
            return x
        else:
            return y
    def lcs(xs, ys, table):
        if (xs, ys) in table:
            return table[(xs, ys)]
        ret = ""
        if xs == "" or ys == "":
            ret = ""
        elif xs[-1] == ys[-1]:
            ret = lcs(xs[:-1], ys[:-1], table) + xs[-1]
        else:
            ret = maxBy(len,
                        lcs(xs[:-1], ys, table),
                        lcs(xs, ys[:-1], table))
        table[(xs, ys)] = ret
        return ret

    S = SI(); N = len(S)
    T = SI(); M = len(T)

    dp = [[0] * (M + 1) for _ in range(N + 1)]
    ans = []

    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    i = N; j = M
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans.append(S[i-1])
            i -= 1
            j -= 1
    print("".join(ans[::-1]))
    return

def examG():

    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""

"""

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


def main():
    s = S()
    t = S()
    s_len = len(s)
    t_len = len(t)
    dp = [[0] * (t_len+1) for i in range(s_len+1)]
    ans = []

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

    # print(*dp)
    i = s_len
    j = t_len
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans.append(s[i-1])
            i -= 1
            j -= 1

    print(''.join(ans[::-1]))

if __name__ == '__main__':
    main()