Problem:


Score : 100 points

Problem Statement

You are given strings s and t.
Find one longest string that is a subsequence of both s and t.

Notes

A subsequence of a string x is the string obtained by removing zero or more characters from x and concatenating the remaining characters without changing the order.

Constraints

s and t are strings consisting of lowercase English letters.

1 \leq |s|, |t| \leq 3000

Input

Input is given from Standard Input in the following format:

s
t

Output

Print one longest string that is a subsequence of both s and t.
If there are multiple such strings, any of them will be accepted.

Sample Input 1

axyb
abyxb

Sample Output 1

axb

The answer is axb or ayb; either will be accepted.

Sample Input 2

aa
xayaz

Sample Output 2

aa

Sample Input 3

a
z

Sample Output 3

The answer is  (an empty string).

Sample Input 4

abracadabra
avadakedavra

Sample Output 4

aaadara



Sample input:
axyb
abyxb


Sample output:
axb

Submission status: Accepted

Solution code:
S = input()
T = input()

ls = len(S)
lt = len(T)

DP = [[0] * (ls+1) for _ in range(lt+1)]

for i in range(lt):
    for j in range(ls):
        if T[i] == S[j]:
            DP[i+1][j+1] = DP[i][j] + 1
        else:
            DP[i+1][j+1] = max(DP[i+1][j], DP[i][j+1])

ans = ''
while ls * lt > 0:
    if DP[lt][ls] == DP[lt-1][ls]:
        lt -= 1
    elif DP[lt][ls] == DP[lt][ls-1]:
        ls -= 1
    elif DP[lt][ls] == DP[lt-1][ls-1] + 1:
        lt -= 1
        ls -= 1
        ans += S[ls]
print(ans[::-1])

Submission status: Accepted

Solution code:
s1 = list(input())
s2 = list(input())

dp = [[0] * (len(s2) + 1) for i in range(len(s1) + 1)]

s1.insert(0, ' ')
s2.insert(0, ' ')

# 長さ計算
max_len = 0
for i in range(1, len(s1)):
    for j in range(1, len(s2)):
        if s1[i] == s2[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        max_len = max(max_len, dp[i][j])

# 復元
ans = []
i = len(s1)-1
j = len(s2)-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:
        ans.insert(0, s1[i])
        i -= 1
        j -= 1
print(''.join(ans))

Submission status: Accepted

Solution code:
s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
for i in range(slen):
  for j in range(tlen):
    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])
result = ''
i = slen
j = tlen
while i > 0 and j > 0:
  if dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)

Submission status: Accepted

Solution code:
def solve():
    s, t = read()
    result = think(s, t)
    write(result)


def read():
    return read_line(), read_line()


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(s, t):
    # create dp table
    local_s = ' ' + s  # for convenience
    local_t = ' ' + t
    dp = [[0 for x in range(len(local_s))] for y in range(len(local_t))]

    for y, ct in enumerate(local_t):
        for x, cs in enumerate(local_s):
            if x == 0 or y == 0:
                dp[y][x] = 0
            else:
                if local_s[x] == local_t[y]:
                    dp[y][x] = dp[y - 1][x - 1] + 1
                else:
                    dp[y][x] = max(dp[y - 1][x], dp[y][x - 1], dp[y - 1][x - 1])

    # scan dp table backward
    x = len(dp[0]) - 1
    y = len(dp) - 1
    buf = ''

    while x > 0 and y > 0:
        if local_s[x] == local_t[y]:
            buf += local_s[x]
            x -= 1
            y -= 1
        else:
            if dp[y][x] == dp[y - 1][x]:
                y -= 1
            else:
                x -= 1

    buf = list(buf)
    buf.reverse()
    return ''.join(buf)


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

S = input().rstrip()
T = input().rstrip()
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] = DP[i][j]+1
        else:
            DP[i+1][j+1] = max(DP[i+1][j],DP[i][j+1])

m,n = len(S),len(T)
ans = ''
while m>0 and n>0:
    if DP[m][n] == DP[m][n-1]:
        n-=1
    elif DP[m][n] == DP[m-1][n]:
        m -= 1
    else:
        m,n = m-1,n-1
        ans = T[n]+ans
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
s=' '+input().rstrip()
t=' '+input().rstrip()
m=len(s)-1
n=len(t)-1
dp=[[0]*(n+1) for i in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
ans=''
while m>0 and n>0:
    if dp[m][n]==dp[m][n-1]:
        n-=1
    elif dp[m][n]==dp[m-1][n]:
        m-=1
    elif dp[m][n]==dp[m-1][n-1]+1:
        ans=s[m]+ans
        m-=1
        n-=1
print(ans)

Submission status: Accepted

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

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

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

i = len(s) - 1
j = len(t) - 1
c = 0
ans = []
ansl = dp[-1][-1]
while (c < ansl):
    if s[i] == t[j]:
        ans.append(s[i])
        i -= 1
        j -= 1
        c += 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:
import math
import sys

S = sys.stdin.readline()[:-1]
T = sys.stdin.readline()[:-1]
sl = len(S)
tl = len(T)
dp = [[0 for _ in range(tl + 1)] for _ in range(sl + 1)]

#dp[ s_ind][t_ind] → S の  s_ind文字目、Tの t_ind文字目までのLCS
ans = ""
for s_ind in range(sl):
    for t_ind in range(tl ):
        if S[s_ind]  == T[t_ind]:
            dp[s_ind + 1][t_ind + 1] = dp[s_ind ][t_ind ] + 1   # AB "C"    と DQ "C" → AB まで とDQまでが dp[s_ind - 1][t_ind -1] 、それに各+1文字してdp[s_ind ][t_ind ] 、共通列の長さも+1

        dp[s_ind + 1][t_ind + 1]  = max(dp[s_ind + 1][t_ind + 1],dp[s_ind + 1][t_ind  ],dp[s_ind][t_ind+ 1])

i = sl
j = tl
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
        i -=1
        j -=1


print(ans)

Submission status: Accepted

Solution code:
s,t=input(),input()
ls,lt=len(s),len(t)
dp=[[0]*(lt+1) for _ in range(ls+1)]
for i in range(1,ls+1):
  for j in range(1,lt+1):
    if s[i-1]==t[j-1]:dp[i][j]=dp[i-1][j-1]+1
    else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])
l=dp[-1][-1]
i,j,a=ls,lt,""
while l!=0:
  if dp[i][j]==dp[i][j-1]:j-=1
  elif dp[i][j]==dp[i-1][j]:i-=1
  else:a=s[i-1]+a;i-=1;j-=1;l-=1
print(a)

Submission status: Accepted

Solution code:
s=input()
t=input()
n=len(s)
m=len(t)
s1=''
dp=[[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(n+1):
  for j in range(m+1):
    if i==0 or j==0:
      continue
    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])
l=dp[n][m]#ans
i=n#s
j=m#t
while(i>=0 and j>=0):
    if s[i-1]==t[j-1]:
      s1+=s[i-1]
      i-=1
      j-=1
    elif dp[i][j-1]>dp[i-1][j]:
      j-=1
    else:
      i-=1
s2=''
for u in range(dp[n][m]-1,-1,-1):
  s2+=s1[u]
print(s2)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    s = input()
    t = input()

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

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

    r = []

    li, lj = len(t), len(s)

    while li != 0 and lj != 0:
        if t[li - 1] == s[lj - 1]:
            r.append(t[li - 1])
            li -= 1
            lj -= 1
        elif dp[li][lj - 1] > dp[li - 1][lj]:
            lj -= 1
        else:
            li -= 1

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

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

ans = ''

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

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

print(ans[::-1])

Submission status: Accepted

Solution code:
def lcs(s,t):
    n=len(s)
    m=len(t)
    dp=[[0 for i in range(n+1)]for j in range(m+1)]
    st=""
    for i in range(m+1):
        for j in range(n+1):
            if(i==0 or j==0):
                dp[i][j]=0
            elif(t[i-1]==s[j-1]):
                dp[i][j]=max(1+dp[i-1][j-1],dp[i][j])
            elif(t[i-1]!=s[j-1]):
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    # print(dp)
    x=dp[m][n]
    lcs=[""]*(x+1)
    lcs[x]=""
    i=m
    j=n
    tmp=x
    while(i>0 and j>0):
        if(t[i-1]==s[j-1]):
            lcs[x-1]=t[i-1]
            i-=1
            j-=1
            x-=1
        elif(dp[i-1][j]>=dp[i][j-1]):
            i-=1
        else:
            j-=1
    # print(lcs)
    for i in range(tmp+1):
        st=st+lcs[i]
    return st      


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

Submission status: Accepted

Solution code:
# Educational DP Contest F-LCS

def f():
    s = input()
    t = input()
    ls, lt = len(s), len(t)
    dp = [[0]*(ls+1) for _ in range(lt+1)]
    for i in range(lt):
        for j in range(ls):
            if t[i] == s[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
                
    ans = ""
    while lt > 0 and ls > 0:
        if dp[lt][ls] == dp[lt-1][ls]:
            lt -= 1
        elif dp[lt][ls] == dp[lt][ls-1]:
            ls -= 1
        elif dp[lt][ls] == dp[lt-1][ls-1] + 1:
            ans += t[lt-1]
            lt -= 1
            ls -= 1
    print(ans[::-1])
    
if __name__ == "__main__":
    f()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

s = input()
t = input()

Ls = len(s)+1
Lt = len(t)+1

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

for i in range(1,Ls):
    for j in range(1,Lt):
        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 = Ls-1, Lt-1
ans = ''
while i >= 0 and j >= 0:
    if dp[i-1][j] == dp[i][j]:
        i -= 1
    elif dp[i][j-1] == dp[i][j]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i,j = i-1,j-1

print(ans)

Submission status: Accepted

Solution code:
a="0"+input()
b="1"+input()
dp=[[0]*len(b) for i in range(len(a))]
for i in range(len(a)):
    for j in range(len(b)):
        if a[i]==b[j]:
            if i>0 and j>0:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=1
        else:
            if i>0 and j>0:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
            elif i==0 and j>0:
                dp[i][j]=dp[i][j-1]
            elif i>0 and j==0:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=0

ans = []
x,y=len(a)-1,len(b)-1
lcs = dp[x][y]
while x > 0 or y > 0:
    if x-1 >= 0 and dp[x-1][y] == lcs:
        x -= 1
    elif y-1 >= 0 and dp[x][y-1] == lcs:
        y -= 1
    else:
        ans.append(a[x])
        y -= 1
        x -= 1
        
        lcs -= 1
print("".join(ans[::-1]))

Submission status: Accepted

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

lens = len(s)
lent = len(t)

# dp = [[None] * lent for _ in range(lens)]
# def dfs(aindex=0, bindex=0):
#     if aindex >= lens:
#         return 0
#     if bindex >= lent:
#         return 0
#
#     if dp[aindex][bindex] is not None:
#         return dp[aindex][bindex]
#
#     if s[aindex] == t[bindex]:
#         r = dfs(aindex + 1, bindex + 1) + 1
#     else:
#         r = max(dfs(aindex + 1, bindex), dfs(aindex, bindex + 1))
#     dp[aindex][bindex] = r
#     return r
#
# print(dfs())

shift = [1 << x for x in range(3000 + 1)]

dp = [[0] * (lent + 1) for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            r = dp[aindex + 1][bindex + 1] + 1
        else:
            r = max(dp[aindex + 1][bindex], dp[aindex][bindex + 1])
        dp[aindex][bindex] = r

ans = ""
ls = len(s)
lt = len(t)
ls = 0
lt = 0
while ls < lens and lt < lent:
    if dp[ls][lt] == dp[ls + 1][lt]:
        ls += 1
    elif dp[ls][lt] == dp[ls][lt + 1]:
        lt += 1
    else:
        ans += t[lt]
        ls += 1
        lt += 1
print(ans)

Submission status: Accepted

Solution code:
# @author 

import sys

class FLCS:
    def solve(self):
        s = input()
        t = input()
        n = len(s)
        m = len(t)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        dp[0][0] = 0
        for i in range(1, n + 1):
            for j in range(1, m + 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 = ""
        cur = max(dp[-1])
        cur_index = -float('inf')
        for i in range(n, 0, -1):
            if cur == 0:
                break
            if cur in dp[i] and (cur not in dp[i - 1] or dp[i - 1].index(cur) >= cur_index):
                index = dp[i].index(cur)
                ans += t[index - 1]
                cur -= 1
                cur_index = index

        print(ans[::-1])

solver = FLCS()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

s = input()
t = input()

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

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

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

ans = ""

def LCS(i=n,j=m):
    global ans
    if (i, j) == (0,0):
        return
    tmp = dp[i][j]
    if s[i-1] == t[j-1]:
        if i-1 >= 0 and j-1 >=0 and tmp == dp[i-1][j-1] + 1:
            ans = s[i-1] + ans
            LCS(i-1, j-1)
        elif i-1 >= 0 and tmp == dp[i-1][j]:
            LCS(i-1, j)
        elif j-1 >= 0 and tmp == dp[i][j-1]:
            LCS(i, j-1)
    else:
        if i-1 >= 0 and tmp == dp[i-1][j]:
            LCS(i-1, j)
        elif j-1 >= 0 and tmp == dp[i][j-1]:
            LCS(i, j-1)

LCS()
print(ans)

Submission status: Accepted

Solution code:
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
s = input()
t = input()
#dp[i][j]...sのi文字目まで、tのj文字目までを考えた時の共通する部分文字列の最長の長さ
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
ans = ''

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

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

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

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

Submission status: Accepted

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

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 = 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:
import sys

input = sys.stdin.readline

s = input()[:-1]
t = input()[:-1]

N = len(s) + 1
M = len(t) + 1


# dp[i][j] := s[i] t[j]までのLCS
dp = [[0]*M for _ in range(N)]


for i in range(1, N):
    for j in range(1, M):
        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])

"""
復元
もしdp[i][j] == dp[i][j-1]ならt[j-1]は使われていないことがわかる
もしdp[i][j] == dp[i-1][j]ならs[i-1]は使われていないことがわかる
それ以外の場合、s[i-1], t[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  # t[j-1] + ansでも同じ
        i -= 1
        j -= 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(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j + 1], dp[i + 1][j])

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

Submission status: Accepted

Solution code:
s=input()
l1=len(s)
t=input()
l2=len(t)
arr=[[0]*(l2+1) for _ in range(l1+1)]
for i in range(l1):
  for j in range(l2):
    if s[i]==t[j]:
      arr[i+1][j+1]=1
for i in range(1,l1+1):
  for j in range(1,l2+1):
    if arr[i][j]==1:
      arr[i][j]+=arr[i-1][j-1]
    else:
      arr[i][j]=max(arr[i-1][j],arr[i][j-1])
check=arr[l1][l2]
pos=0
ans=''
for i in range(l1,-1,-1):
  for j in range(l2-pos,-1,-1):
    if j==0:
      continue
    if arr[i][j]==check and arr[i][j-1]==check-1 and arr[i-1][j]==check-1:
      ans+=t[j-1]
      pos=l2-j+1
      check-=1
      break
print(ans[::-1])

Submission status: Accepted

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

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

string = ""
cnt = dp[s_len][t_len]

while t_len > 0 and s_len > 0:
    if dp[s_len][t_len] == dp[s_len - 1][t_len]:
        s_len -= 1
    elif dp[s_len][t_len] == dp[s_len][t_len - 1]:
        t_len -= 1
    else:
        string += s[s_len - 1]
        s_len -= 1
        t_len -= 1


print(string[::-1])

Submission status: Accepted

Solution code:
def lcs(str1, str2):
    '''文字列str1, str2の最長共通部分列(Lowest Common Subsequence, LCS)を求める
    計算量O(len(str1)*len(str2))  
    '''
    dp = [[0]*(len(str2) + 1) for _ in range(len(str1) + 1)]
    for i in range(len(str1)):
        for j in range(len(str2)):
            if str1[i] == str2[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])

    '''復元を実行
    最長の長さを求めるなら return dp[len(str1)][len(str2)] をするとよい'''
    res = ''
    i, j = len(str1), len(str2)
    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 = str1[i-1] + res
            i -= 1
            j -= 1
    return res

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

Submission status: Accepted

Solution code:
def lcs(str1, str2):
    '''文字列str1, str2の最長共通部分列(Lowest Common Subsequence, LCS)を求める
    計算量O(len(str1)*len(str2))  
    '''
    dp = [[0]*(len(str2) + 1) for _ in range(len(str1) + 1)]
    for i in range(len(str1)):
        for j in range(len(str2)):
            if str1[i] == str2[j]:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

    '''復元を実行
    最長の長さを求めるなら return dp[len(str1)][len(str2)] をするとよい
    '''
    res = ''
    i, j = len(str1), len(str2)
    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 = str1[i-1] + res
            i -= 1
            j -= 1
    return res

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

Submission status: Accepted

Solution code:
def f_lcs(S, T):
    """
    文字列s, tが与えられる。sの部分列かつtの部分列であるような文字列のうち、
    最長のものを1つ求めよ。文字列xの部分列とは、xから0個以上の文字を除いたあと、
    残りの文字を元の順序で連結して得られる文字列のことである。
    """
    # 参考: https://qiita.com/drken/items/03c7db44ccd27820ea0d
    from itertools import product

    # dp[i+1][j+1]: sのi文字目までとtのj文字目まで見たときにできる
    # Longest Common Subsequence (LCS) の長さ
    dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]
    for i, j in product(range(len(S)), range(len(T))):
        # もし s_i = t_j なら、dp[i][j] から作れるLCSに対し、 s_i(t_jも同じ) を
        # 加えることで、それまでより長いLCSを作りうる
        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] に対して、tのj文字目を見てもLCSの長さは不変。
            # なぜなら、もし、sのi文字目とtのj-1文字目が等しいなら、それらを
            # LCSに加えてしまっているのでsのi文字目とtのj文字目とではLCSの候補にできない。
            # つまり、 dp[i+1][j+1]=dp[i+1][j] である。
            # 逆に、等しくないなら、 sのi文字目とtのj文字目から新たなLCSを作りうるが、これは単に
            # dp[i+1][j+1] の値である。結局、配列の2つの要素のうち小さくない方を選べばいい。
            # 同じく、 dp[i][j+1] に対して、sのi文字目を見てもLCSの長さは不変。
            # これらの事実を反映したのが下の式。
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1])

    ans = ''
    # DPテーブルから、現時点で見ているノードがどのノードから遷移してきたかを
    # 特定することでLCSの文字列を復元する
    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1  # (i-1, j) -> (i, j) と遷移していた
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1  # (i, j-1) -> (i, j) と遷移していた
        else:
            # (i-1, j-1) -> (i, j) と遷移していた
            ans += S[i - 1]  # T[j-1]でも(同じ文字なので)構わない
            i -= 1
            j -= 1
    return ans[::-1]  # DPテーブルの末尾から走査する都合上、解が逆さになる

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

Submission status: Accepted

Solution code:
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))


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][j+1], dp[i+1][j])
# print(dp[len(s)][len(t)])
ans = []
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
        ans.append(s[x])
print(''.join(ans[::-1]))

Submission status: Accepted

Solution code:
def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)
    dp = [[0] * (lt + 1) for _ in range(ls + 1)]
    for i in range(ls):
        for j in range(lt):
            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 = ''
    while ls > 0 and lt > 0:
        if s[ls - 1] == t[lt - 1]:
            ls -= 1
            lt -= 1
            ans += s[ls]
            continue
        if dp[ls - 1][lt] > dp[ls][lt - 1]:
            ls -= 1
        else:
            lt -= 1
    print(ans[::-1])


main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template

# BEGIN CUT HERE
def lcs(s, t):
    '''s,tは文字列をリスト化したもの'''
    n = len(s)
    m = len(t)
    s.append('$')
    t.append('%')
    dp = [[0 for _j in range(m + 2)] for _i in range(n + 2)]
    dp[0][0] = 0
    for i in range(n+1):
        for j in range(m+1):
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
            dp[i][j + 1] = max(dp[i][j + 1], dp[i][j])
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + (s[i] == t[j]))
    # return dp[n][m]
    '''復元する'''
    length = dp[n][m]
    ans = ['']*(length+1)
    while(length > 0):
        if(s[n] == t[m]):
            ans[length] = s[n]
            n-=1
            m-=1
            length-=1
        elif(dp[n+1][m+1] == dp[n][m+1]):
            n-=1
        else:
            m-=1
    return ''.join(ans[1:])
# END CUT HERE

def ALDS1_10_C():
    q = ii()
    for _ in range(q):
        s = li()
        t = li()
        print(lcs(s, t))

def EDPC_F():
    s = li()
    t = li()
    print(lcs(s,t))


if __name__ == '__main__':
    # ALDS1_10_C()
    EDPC_F()

Submission status: Accepted

Solution code:
S = input()
T = input()


dp = [[0] * (len(T) + 1) for i in range(len(S) + 1)]
dp2 = [[(0, 0)] * (len(T) + 1) for i in range(len(S) + 1)]
for i, s in enumerate(S, start=1):
    for j, t in enumerate(T, start=1):
        if s == t:
            dp[i][j] = dp[i - 1][j - 1] + 1
            dp2[i][j] = (i - 1, j - 1)
        elif dp[i - 1][j] > dp[i][j - 1]:
            dp[i][j] = dp[i - 1][j]
            dp2[i][j] = (i - 1, j)
        else:
            dp[i][j] = dp[i][j - 1]
            dp2[i][j] = (i, j - 1)

ans = ''
s, t = len(S), len(T)
while (s > 0) and (t > 0):
    if S[s - 1] == T[t - 1]:
        ans += S[s - 1]
    ns, nt = dp2[s][t]
    s, t = ns, nt

print(ans[::-1])

Submission status: Accepted

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

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

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

print(revans[::-1])

Submission status: Accepted

Solution code:
import fileinput

def lcs(a, b):
    lcs_table = []

    def get_lcs(a_idx, b_idx):
        if a_idx < 0 or b_idx < 0:
            return 0
        else:
            return lcs_table[a_idx][b_idx] 

    for a_idx, last_a in enumerate(a):
        lcs_table.append([0] * len(b))
        for b_idx, last_b in enumerate(b):
            if last_a == last_b:
                new_lcs = get_lcs(a_idx - 1, b_idx - 1) + 1
            else:
                new_lcs = max(get_lcs(a_idx - 1, b_idx), get_lcs(a_idx, b_idx - 1))
            lcs_table[a_idx][b_idx] = new_lcs

    result = []
    current_a_idx = len(a) - 1
    current_b_idx = len(b) - 1
    while current_a_idx >= 0 and current_b_idx >= 0:
        if a[current_a_idx] == b[current_b_idx]:
            result.append(a[current_a_idx])
            current_a_idx -= 1
            current_b_idx -= 1
        else:
            if get_lcs(current_a_idx, current_b_idx) == 0:
                break
            if get_lcs(current_a_idx - 1, current_b_idx) > get_lcs(current_a_idx, current_b_idx - 1):
                current_a_idx -= 1
            else:
                current_b_idx -= 1

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

inp = fileinput.FileInput()

a = inp.readline()
b = inp.readline()
print(lcs(a, b))

Submission status: Accepted

Solution code:
#n,W=map(int, input().split())
s=input()
t=input()
ns=len(s)
nt=len(t)
dp=[[0 for j in range(ns+1)] for i in range(nt+1)]
    
for i in range(1,nt+1):
    for j in range(1,ns+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])

cnt=dp[-1][-1]
ans=[]
ct,cs=nt,ns
while cnt>0:
    while dp[ct][cs]==dp[ct-1][cs] and ct>0:
        ct-=1
        
    while dp[ct][cs]==dp[ct][cs-1] and cs>0:
        cs-=1

    ans.append(t[ct-1])
    cnt-=1
    #print(ct,cs,t[ct-1])
    ct-=1
    cs-=1

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def lcs(xs, ys):
    dp = [([0] * (len(ys) + 1)) for _ in range(len(xs) + 1)]
    for i, x in enumerate(xs):
        for j, y in enumerate(ys):
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j], dp[i][j] + int(x == y))

    s = []
    p = (-1, -1)
    while 0 < dp[p[0]][p[1]]:
        if dp[p[0]][p[1]] == dp[p[0]-1][p[1]]:
            p = (p[0]-1, p[1])
        elif dp[p[0]][p[1]] == (dp[p[0]-1][p[1]-1] + int(xs[p[0]] == ys[p[1]])):
            s.append(xs[p[0]])
            p = (p[0]-1, p[1]-1)
        else:
            p = (p[0], p[1]-1)

    return ''.join(reversed(s))


def solve(s: str, t: str):
    return lcs(s, t)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    result = solve(s, t)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
	S, T = input(), input()

	Z = 3010
	dp = [[0] * Z for _ in range(Z)]
	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])

	#for line in dp:
	#	print(line)
	#print(dp[len(S)][len(T)])
	i, j, result = len(S), len(T), ""
	while 0 < i and 0 < j:
		if dp[i][j] == dp[i - 1][j]:
			i -= 1
		elif dp[i][j] == dp[i][j - 1]:
			j -= 1
		else:
			result = S[i - 1] + result
			i -= 1
			j -= 1
	print(result)

main()