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:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[i][j] - length of the longest common subsequence
    OPT[i][j] = max(OPT[i-1][j-1]+(1 if s[i] == t[j] else 0),
                    OPT[i-1][j],
                    OPT[i][j-1])
    """
    s = input().strip()
    t = input().strip()
    OPT = [[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):
            OPT[i][j] = max(OPT[i-1][j-1]+(1 if s[i-1] == t[j-1] else 0),
                            OPT[i-1][j],
                            OPT[i][j-1])
    i, j = len(s), len(t)
    ans = []
    while i != 0 and j != 0:
        if OPT[i][j] == OPT[i-1][j]:
            i -= 1
        elif OPT[i][j] == OPT[i][j-1]:
            j -= 1
        else:
            ans.append(s[i-1])
            i -= 1
            j -= 1
    return ''.join(ans[::-1])


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

S = input().rstrip()
T = input().rstrip()

Ns = len(S)
Nt = len(T)

dp = [[0]*(Nt+1) for _ in range(Ns+1)]
path = [[None for _ in range(Nt+1)] for _ in range(Ns+1)]

for i in range(Ns):
    for j in range(Nt):
        if S[i]==T[j]:
            if dp[i+1][j+1] < dp[i][j]+1:
                dp[i+1][j+1] = dp[i][j]+1
                path[i+1][j+1] = (i,j)
        else:
            if dp[i][j+1] < dp[i+1][j]:
                dp[i+1][j+1] = dp[i+1][j]
                path[i+1][j+1] = (i+1,j)
            else:
                dp[i+1][j+1] = dp[i][j+1]
                path[i+1][j+1] = (i,j+1)


ans = []
cur = [Ns, Nt]
while cur[0] != 0 and cur[1] != 0:
    nxt = path[cur[0]][cur[1]]
    if cur[0]-1 == nxt[0] and cur[1]-1==nxt[1]:
        ans.append(S[cur[0]-1])
    cur[0] = nxt[0]
    cur[1] = nxt[1]
answer = ''.join(reversed(ans))
print(answer)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    S = list(input())
    T = list(input())

    LCS = [[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):
            x = 1 if S[i - 1] == T[j - 1] else 0
            LCS[i][j] = max(LCS[i - 1][j - 1] + x, LCS[i - 1][j], LCS[i][j - 1])

    res = []
    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if LCS[i][j] == LCS[i - 1][j]:
            i -= 1
        elif LCS[i][j] == LCS[i][j - 1]:
            j -= 1
        else:
            res.append(S[i - 1])
            i -= 1
            j -= 1

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def main():
    s = input()
    t = input()
    lens = len(s)
    lent = len(t)
    # dp[i][j] := s,tをそれぞれi,j文字目まででの最長一致部分列の長さ
    dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
    for i in range(lens):
        for j in range(lent):
            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])

    # dpの終点から文字列を復元していく
    ans = ""
    i,j = lens,lent
    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)

main()

Submission status: Accepted

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

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
# dp[i][j]: s[:i], t[:j] における最長共通部分列の長さ

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
#文字列をASCII codeのリストで管理
S = np.array([ord(i) - 97 for i in input()], dtype=int)
T = np.array([ord(i) - 97 for i in input()], dtype=int)
ls = len(S)
lt = len(T)
#S[i] == T[j]であれば、i * j行列の[i,j]成分が1となる行列
equal = np.equal.outer(S,T).astype(int)
#print(equal)
 
dp = [np.zeros(lt + 1,dtype = int)]
#print(dp)
for i in range(ls):
  #追加された最後のdp列をx,newDPとする
  x = dp[-1].copy()
  newDP = x.copy()
  #一致しているところで1を足し、そうでないところはそのまま
  newDP[1:] = np.maximum(x[:-1] + equal[i],newDP[1:])
  #dp[i] = i以前のdpの最大値に更新
  np.maximum.accumulate(newDP, out = newDP)
  #最大共通部分を計算するだけなら一列のdp列を使い回せば良いが
  #文字列の復元のために、dp列を追加する
  dp.append(newDP)
  #print(dp)
 
 
ans = ""
i, j = ls, lt
#数列の復元と文字列への復元
while i > 0 and j > 0:
  if S[i - 1] == T[j - 1]:
    ans += chr(S[i - 1] + 97)
    i -= 1
    j -= 1
    continue
  if dp[i][j] == dp[i - 1][j]:
    i -= 1
  else:
    j -= 1

#リバース
print(ans[::-1])

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

ci, cj = len(s), len(t)
ans = []

while ci!=0 and cj!=0:
    if s[ci-1]==t[cj-1]:
        ci -= 1
        cj -= 1
        ans.append(s[ci])
    else:
        if dp[ci][cj]==dp[ci-1][cj]:
            ci -= 1
        else:
            cj -= 1

ans.reverse()
print(''.join(ans))

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

ci, cj = len(s), len(t)
ans = []

while ci!=0 and cj!=0:
    ni, nj = track[ci][cj]
    
    if ci-ni==1 and cj-nj==1:
        ans.append(s[ni])
    
    ci, cj = ni, nj

ans.reverse()
print(''.join(ans))

Submission status: Accepted

Solution code:
def solve():
    s = input()
    t = input()
    s_size = len(s)
    t_size = len(t)
    dp = [[0 for i in range(s_size+1)] for j in range(t_size+1)]
    for i in range(1, t_size+1):
        for j in range(1, s_size+1):
            if t[i-1] == s[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
    ans = ""
    i, j = t_size, s_size
    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 = t[i-1] + ans
            i -= 1
            j -= 1
    print(ans)
solve()

Submission status: Accepted

Solution code:
s=input()
t=input()
S=len(s)
T=len(t)
ans=[[0 for e in range(S+1)] for f in range(T+1)]
chk=[]
for a in range(1,T+1):
 for b in range(1,S+1):
  if t[a-1]==s[b-1]:
   ans[a][b]=ans[a-1][b-1]+1
  else:
   if ans[a-1][b]>ans[a][b-1]:
    ans[a][b]=ans[a-1][b]
   else:
    ans[a][b]=ans[a][b-1]
x,y=T,S
while x>0 and y>0:
 if ans[x][y]==ans[x-1][y]:
  x-=1
 elif ans[x][y]==ans[x][y-1]:
  y-=1
 else:
  x-=1
  y-=1
  chk.append(s[y])
chk.reverse()
print("".join(chk))

Submission status: Accepted

Solution code:
def lcs(s1,s2,m,n,t):
    l=[]
    for i in range(0,m+1):
        t[i][0]=0
    for i in range(1,n+1):
        t[0][i]=0
    for i in range(1,m+1):
        for j in range(1,n+1):
            if s1[i-1]==s2[j-1]:
                t[i][j]=t[i-1][j-1]+1
            else:
                t[i][j]=max(t[i-1][j],t[i][j-1])
    i=m
    j=n
    while(i>0 and j>0):
        if s1[i-1]==s2[j-1]:
            l.append(s1[i-1])
            i-=1
            j-=1
        else:
            if t[i-1][j]>t[i][j-1]:
                i-=1
            else:
                j-=1
    l.reverse()  
    if len(l)==0:b=""
    else:b="".join(str(a) for a in l)
    return b
s1=input()
s2=input()
m=len(s1)
n=len(s2)
t=[[0 for x in range(n+1)] for x in range(m+1)] 
d=lcs(s1,s2,m,n,t)
print(d)

Submission status: Accepted

Solution code:
s = input()
t = input()
S = len(s)
T = len(t)
dp = [[0 for j in range(T+1)] for i in range(S+1)]
for i in range(S):
    for j in range(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])
a = ""
i += 1
j += 1
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        i -= 1
        j -= 1
        a = s[i] + a

print(a)

Submission status: Accepted

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

def LCS(X,Y):
    XL = len(X)
    YL = len(Y)
    dp = [[0 for j in range(YL+1)] for i in range(XL+1)]
    for i in range(XL):
        for j in range(YL):
            if X[i] == Y[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])
    # 以下復元
    S = ''
    i,j = i+1,j+1
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            i,j = i-1,j-1
            S += X[i]
    S = S[::-1]
    return S

print(LCS(s,t))

Submission status: Accepted

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

def LCS(X,Y):
    XL = len(X)
    YL = len(Y)
    dp = [[0 for j in range(YL+1)] for i in range(XL+1)]
    for i in range(XL):
        for j in range(YL):
            if X[i] == Y[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])
    # 以下復元
    idx = dp[XL][YL]-1
    S = [0]*(idx+1)
    i,j = i+1,j+1
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            i,j = i-1,j-1
            S[idx] = X[i]
            idx -= 1
    return S

print(''.join(LCS(s,t)))

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

S = list(ST())
T = list(ST())
dp = FILL2(0,len(S)+1,len(T)+1)
for i in range(len(S)+1):
    for j in range(len(T)+1):
        if i+1<=len(S) and j+1<=len(T):
            if S[i]==T[j]:
                dp[i+1][j+1] = dp[i][j] + 1
        if i+1<=len(S):
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if j+1 <= len(T):
            dp[i][j+1] = max(dp[i][j+1],dp[i][j])

l = dp[len(S)][len(T)]
i = len(S)
j = len(T)
ans = ''
while l > 0:
    if S[i-1]==T[j-1]:
        i -= 1
        j -= 1
        l -= 1
        ans = S[i]+ans
    else:
        if dp[i][j-1]==dp[i][j]:
            j -= 1
        else:
            i -= 1
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(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)
f = ""

while((i>0) & (j>0)):
  if dp[i][j] == dp[i-1][j]: i -= 1
  elif dp[i][j] == dp[i][j-1]: j -= 1
  else :
    f += s[i-1]
    i -= 1
    j -= 1
  
print(f[::-1])

Submission status: Accepted

Solution code:
from sys import stdin, stdout
from collections import deque, defaultdict
import math as m

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

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

def main():
	s = rll()[0]
	t = rll()[0]
	m, n = len(s), len(t)
	dp = [[0 for __ in range(n)] for _ in range(m)]

	#dp[i][j] = LCs of s0,...,si and t0,...,tj

	def pprint(M):
		for row in M:
			print(row)
		print("~~~")
	
	dp[0][0] = 1 if s[0] == 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):
		dp[r][0] = max(dp[r-1][0], 1 if s[r] == t[0] else 0)

	for r in range(1, m):
		for c in range(1, n):
			dp[r][c] = max(dp[r][c], 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()
	i, j = m - 1, n - 1
	while i >= 0 and j >= 0:
		if s[i] == t[j]:
			ans.appendleft(s[i])
			i -= 1
			j -= 1
		else:
			up, left = NINF, NINF
			if i - 1 >= 0:
				up = dp[i-1][j]
			if j - 1 >= 0:
				left = dp[i][j-1]
			if up >= left:
				i -= 1
			else:
				j -= 1
	print("".join(x for x in ans))
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
s = input()
t = input()
lenS = len(s)
lenT = len(t)
dp = []
for i in range(lenS+1):
    dp.append([0]*(lenT+1))
for i in range(1,lenS+1):
    for j in range(1,lenT+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=""
i=lenS
j=lenT
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:
import numpy as np
S = np.array([ord(i)-97 for i in input()], dtype=int)
T = np.array([ord(i)-97 for i in input()], dtype=int)
Ns = len(S)
Nt = len(T)
equal = np.equal.outer(S, T).astype(int)
 
dp = [np.zeros(Nt + 1, dtype=int)]
for i in range(Ns):
    x = dp[-1].copy()
    newDP = x.copy()
    newDP[1:] = np.maximum(x[:-1] + equal[i], newDP[1:])
    np.maximum.accumulate(newDP, out=newDP)
    dp.append(newDP)
 
 
ans = ""
i, j = Ns, Nt
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans += chr(S[i-1]+97)
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1
 
print(ans[::-1])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
s=input()
t=input()
l1=len(s)
l2=len(t)
dp=[[-1]*(l2+1) for i in range(l1+1)]   

for i in range(l1+1):
    for j in range(l2+1):
        if i==0 or j==0:
            dp[i][j]=0
            
        elif 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])
            

size=dp[l1][l2]
i,j=l1,l2
ans=[0]*size
while i>0 and j>0:
    if s[i-1]==t[j-1]:
        ans[size-1]=(s[i-1])
        i-=1
        j-=1
        size-=1
    elif dp[i-1][j]>dp[i][j-1]:
        i-=1
    else:
        j-=1
        
    
print(''.join(ans))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    s=input()
    len_s=len(s)
    t=input()
    len_t=len(t)
    dp=[[0]*(len_t+1) for _ in range(len_s+1)] # sのi文字目までについて，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]=dp[i-1][j-1]+1
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    len_ans=dp[len_s][len_t]
    i,j=len_s,len_t
    ans=""
    while len_ans:
        if s[i-1]==t[j-1]:
            ans+=s[i-1]
            i-=1
            j-=1
            len_ans-=1
        elif dp[i][j]==dp[i-1][j]:
            i-=1
        else:
            j-=1
    print(ans[::-1])
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
s,t=input(),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])

i,j=S,T
ans=''
while min(i,j)>0:
        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]
            i-=1 ; j-=1
print(ans[::-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s1 = list(input())
s2 = list(input())
n = len(s1)
m = len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
dp=[[0]*(m+1) for i in range(n+1)]

for i in range(1,n+1):
    for j in range(1,m+1):
        if s1[i-1]==s2[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
res=[]
i,j=n,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:
        res.append(s1[i-1])
        i-=1
        j-=1
print("".join(res[::-1]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    S = input().rstrip()
    T = input().rstrip()

    # dp[i][j] = sのi番目とtのj番目まででえられる最長部分列の長さ
    dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

    # 最長部分列の長さを探索
    for i, s in enumerate(S, 1):
        for j, t in enumerate(T, 1):
            # 一致するとき
            if s == t:
                # 一致する文字の一つ左側までの最大部分列に一致した文字を加える
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)
            # 一致しない場合も、一つ手前の文字までの最大文字列を引き継ぐ
            dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1])

    # 最長だった場合の具体例を復元する
    i, j = len(S), len(T)
    ans = ""
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans = S[i-1] + ans
            i -= 1
            j -= 1
    print(ans)

if __name__ == '__main__':
    main()

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

nums = len(s)
numt = len(t)
d = dp[nums][numt]
ans = ""

while True:
    if d == 0:
        break
    if dp[nums][numt - 1] == d:
        numt -= 1
    elif dp[nums - 1][numt] == d:
        nums -= 1
    else:
        ans += s[nums - 1]
        nums -= 1
        numt -= 1
        d -= 1

print(ans[::-1])

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

nums = len(s)
numt = len(t)
d = dp[nums][numt]
ans = ""

while True:
    if d == 0:
        break
    if dp[nums - 1][numt] == d:
        nums -= 1
    elif dp[nums][numt - 1] == d:
        numt -= 1
    else:
        ans += s[nums - 1]
        nums -= 1
        numt -= 1
        d -= 1

print(ans[::-1])

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.buffer.readline
    s=b' '+input()[:-1]
    t=b' '+input()[:-1]
    n,m=len(s),len(t)
    dp=[[0]*m for _ in range(n)]
    b=dp[0]
    for i,x in enumerate(s[1:],1):
        dpi=dp[i]
        for j,y in enumerate(t[1:],1):
            if x==y:
                dpi[j]=b[j-1]+1
            else:
                v,w=b[j],dpi[j-1]
                dpi[j]=v if v>w else w
        b=dpi
    ans=[]
    i,j=n-1,m-1
    while dp[i][j]:
        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])
            i-=1
            j-=1
    print(''.join(map(chr,ans))[::-1])
main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    s = gete()
    t = gete()
    ans = ""

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

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

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

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

    print(ans_r[::-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline

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

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

    # 最長共通部分列の長さを求めるDP配列を作る
    for i1 in range(1, s_len + 1):
        for i2 in range(1, t_len + 1):
            if s[i1 - 1] == t[i2 - 1]:
                dp[i1][i2] = dp[i1-1][i2-1] + 1
            else:
                dp[i1][i2] = max(dp[i1-1][i2], dp[i1][i2-1])
    #for k in range(s_len):
    #    print(dp[k])
    #print("--")
    # DP配列から最長共通部分列をもとめる。
    j1 = s_len
    j2 = t_len
    r = ""
    while j1 > 0 and j2 > 0:
        #print(j1, j2)
        if s[j1-1] == t[j2-1]:
            r += s[j1-1]
            j1 -= 1
            j2 -= 1
        elif dp[j1 - 1][j2] == dp[j1][j2]:
            j1 -= 1
        else:
            j2 -= 1
    print(r[::-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
s = np.array(list(input()))
t = np.array(list(input()))
n = len(s)
m = len(t)
match = s.reshape(-1,1) == t.reshape(1,-1)
lcs = np.zeros((n+1, m+1), dtype='int32')
for i in range(n):
    lcs[i+1,1:] = np.fmax(lcs[i,:-1]+match[i],lcs[i,1:])
    lcs[i+1] = np.maximum.accumulate(lcs[i+1])
l = []
while n > 0 and m > 0:
    if lcs[n, m] == lcs[n-1, m]:
        n-=1
    elif lcs[n, m] == lcs[n, m-1]:
        m-=1
    else:
        l.append(s[n-1])
        n-=1
        m-=1
print(''.join(l[::-1]))

Submission status: Accepted

Solution code:
s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for x in range(n+1)] for y in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        if(s[j-1]==t[i-1]):
            dp[i][j]=1+dp[i-1][j-1]
        else:
            temp=max(dp[i-1][j],dp[i][j-1])
            dp[i][j]=temp
i,j=m,n
ans=''
while (i>0 and j>0):
    if(s[j-1]==t[i-1]):
        ans+=s[j-1]
        i-=1
        j-=1
    else:
        if(dp[i-1][j]>dp[i][j-1]):
            i-=1
        else:
            j-=1
print(ans[::-1])

Submission status: Accepted

Solution code:
s,t='0'+input(),'0'+input()
ns,nt=len(s)+1,len(t)+1
dp=[[0 for i in range(nt)] for i in range(ns)]
for i in range(1,ns):
	for j in range(1,nt):
		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=ns-1,nt-1
ans=''
while i>0 or j>0:
	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[1:])

Submission status: Accepted

Solution code:
import numpy as np


def main():
    S = np.array(list(input()))
    LS = len(S)
    T = np.array(list(input()))
    LT = len(T)
    # LCS
    dp = np.zeros((LS + 1, LT + 1))
    match = S.reshape(-1, 1) == T.reshape(1, -1)
    for s in range(LS):
        dp[s + 1, 1:] = np.fmax(dp[s, :(-1)] + match[s], dp[s, 1:])
        dp[s + 1] = np.maximum.accumulate(dp[s + 1])
    # recover
    s, t = LS, LT
    ans = ''
    while s > 0 and t > 0:
        if dp[s, t] == dp[s - 1, t]:
            s -= 1
        elif dp[s, t] == dp[s, t - 1]:
            t -= 1
        else:
            ans = S[s - 1] + ans
            s -= 1
            t -= 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon May 11 20:44:38 2020

@author: adarsh
"""


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

Submission status: Accepted

Solution code:


def main():
    s = input()
    t = input()
    n, m = len(s), len(t)
    LCS = [[0]*(m+1) for i in range(n+1)]
    # LCS[i][j] is the longest common subsequence of strings s[0...i] and t[0...j]
    for i in range(1, n+1):
        for j in range(1, m+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])
    ans = ""
    i, j = n, m
    while i > 0 and j > 0:
        if s[i-1] == t[j-1]:
            ans += s[i-1]
            i -= 1
            j -= 1
        elif LCS[i][j-1] > LCS[i-1][j]:
            j -= 1
        else:
            i -= 1
    print(ans[::-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

    for i in range(NS):
        for j in range(NT):
            if S[i] == T[j]:
                # dp[i+1][j+1] = max(dp[i][j] + 1, dp[i+1][j], dp[i][j+1])
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

    ans = ''
    i = NS
    j = NT
    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 = S[i-1]+ans
            j -= 1
            i -= 1

    print(ans)


if __name__ == "__main__":
    main()