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

len_s = len(s)
len_t = len(t)

# LCSの最長を求める
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])

# DPを後ろから遡っていって、LCSを求める
lcs_str = ''
i, j = len_s-1, len_t-1
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        lcs_str += s[i]
        i -= 1
        j -= 1
    else:
        if dp[i][j+1] > dp[i+1][j]:
            i -= 1
        else:
            j -= 1
print(lcs_str[::-1])

Submission status: Accepted

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

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

ans = ""
x = len(s)
y = len(t)
d = dp[-1][-1]
while True:
  if d == 0:
    break
  if dp[y - 1][x] == d:
    y -= 1
  elif dp[y][x - 1] == d:
    x -= 1
  else:
    ans += t[y - 1]
    x -= 1
    y -= 1
    d -= 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][j+1], dp[i+1][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(st[::-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

s=ss()
t=ss()
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
print(lcs(s,t))

Submission status: Accepted

Solution code:
#ひとまず長さだけ持つ，後から表を後ろ向きに見て復元を試みる

s=input()
t=input()

ls=len(s)
lt=len(t)
    
    
#sのi文字目とtのj文字目までで取れる最長部分列の長さ
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=""
i=ls
j=lt
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]
        


print(ans[::-1])

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def add_mod(a,b): return (a+b) % MOD

s = input()
t = input()

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

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


for i in range(sl):
    for j in range(tl):
        if s[i] == t[j]: dp[i+1][j+1] = 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 sl > 0 and tl > 0:
    if dp[sl][tl] == dp[sl-1][tl]:
        sl -= 1
    elif dp[sl][tl] == dp[sl][tl-1]:
        tl -= 1
    else:
        ans = s[sl-1] + ans
        sl -= 1
        tl -= 1
print(ans)

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
MOD = 10**9+7

s = input()
t = input()

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

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

for i in range(sl):
    for j in range(tl):
        if s[i] == t[j]: dp[i+1][j+1] = dp[i][j] + 1
        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 sl > 0 and tl > 0:
    if dp[sl-1][tl] == dp[sl][tl]:
        sl -= 1
    elif dp[sl][tl-1] == dp[sl][tl]:
        tl -= 1
    else:
        ans = s[sl-1] + ans
        sl -= 1
        tl -= 1
print(ans)

Submission status: Accepted

Solution code:
def LCS(X,Y):
    m,n=len(X),len(Y)
    MAP=[[0 for i in range(m)] for j in range(n)]
    for i in range(1,n):
        for j in range(1,m):
            if Y[i]==X[j]:
                MAP[i][j]=MAP[i-1][j-1]+1
            else:
                MAP[i][j]=max(MAP[i][j-1],MAP[i-1][j])

    i,j=n-1,m-1
    ans=""
    while MAP[i][j]!=0:
        if MAP[i][j]==MAP[i-1][j]:i -=1
        elif MAP[i][j]==MAP[i][j-1]:j -=1
        else:
            ans +=Y[i]
            i -=1
            j -=1
    return ans[::-1]

print(LCS(" "+input()," "+input()))

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
MOD = 10**9+7

s = input()
t = input()

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

for i in range(sl):
    for j in range(tl):
        if s[i] == t[j]: dp[i+1][j+1] = 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 sl > 0 and tl > 0:
    if dp[sl][tl-1] == dp[sl][tl]:
        tl -= 1
    elif dp[sl-1][tl] == dp[sl][tl]:
        sl -= 1
    else:
        ans = s[sl-1] + ans
        sl -= 1
        tl -= 1
print(ans)

Submission status: Accepted

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

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
s = input()
n = len(s)
t = input()
m = len(t)

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

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

ans = ''

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

print(ans[::-1])

Submission status: Accepted

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

li = [[0 for _ in range(len(S)+1)] for _ in range(len(T)+1)]

for s in range(1,len(S)+1):
    for t in range(1,len(T)+1):
        if S[s-1] == T[t-1]:
            li[t][s] = max(li[t-1][s], li[t][s-1], li[t-1][s-1]+1)
        else:
            li[t][s] = max(li[t-1][s],li[t][s-1])

s = len(S)
t = len(T)
ans = ""
while(s and t):
    if (S[s-1]==T[t-1]) and (li[t][s]-1==li[t-1][s-1]):
        ans = S[s-1]+ans
        s-=1
        t-=1
    elif li[t-1][s] >= li[t][s-1]:
        t-=1
    elif li[t-1][s] < li[t][s-1]:
        s-=1
print(ans)

Submission status: Accepted

Solution code:
#Educational DP Contest
#F-LCS

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

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

#process1
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]) #2箇所参照することに注意

#output process
"""
LCSの長さを求めるなら以下で正解
print(dp[-1][-1])
"""

#今回求めるのは、その文字列
#後ろ側から共通のものを足していく
ans = ""
while True:
    if n == 0 or m == 0: #sかtどちらかの文字列を先頭まで参照したらbreak
        break
    if dp[n][m] == dp[n-1][m]:
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    else: #どちらの数字も変動するとき=共通文字の時
        n,m = n-1,m-1 #処理順序に注意
        ans = s[n] + ans #前に足す(なお、t[m]でも同じことが言える)

print(ans)

Submission status: Accepted

Solution code:
S = input()
T = input()
 
lenS = len(S)
lenT = len(T)
 
lcs = [[0 for i in range(lenT + 1)] for j in range(lenS + 1)]
 
for i in range(lenS):
  for j in range(lenT):
    if S[i] == T[j]:
      lcs[i + 1][j + 1] = lcs[i][j] + 1
    else:
      lcs[i + 1][j + 1] = max(lcs[i + 1][j], lcs[i][j + 1])
#for i in range(lenS + 1):
#  print(lcs[i])

i, j = lenS, lenT
answer = ""
while i != 0 and j != 0:
  if lcs[i - 1][j] == lcs[i][j] - 1:
    if lcs[i][j - 1] == lcs[i][j] - 1:
      answer += S[i - 1]
      i -= 1
    j -= 1
  else:
    i -= 1
  #print(i, j, lcs[i][j], answer)
print(answer[::-1])

Submission status: Accepted

Solution code:
import unittest


class TestF(unittest.TestCase):
    def test_1(self):
        self.assertEqual(
            len(think('axyb', 'abyxb')),
            3
        )

    def test_2(self):
        self.assertEqual(
            len(think('aa', 'xayaz')),
            2
        )

    def test_3(self):
        self.assertEqual(
            len(think('a', 'z')),
            0
        )

    def test_4(self):
        self.assertEqual(
            len(think('abracadabra', 'avadakedavra')),
            7
        )


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


def read():
    s = read_line()
    t = read_line()
    return s, t


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


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


def think(s, t):
    # dp[0][j] = 0
    # dp[i][j] = 0
    # dp[i + 1][j + 1] = max len of LCS for s[0 to ith] and t[0 to jth]
    dp = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]

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

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

    return restore_lcs(s, t, dp)


def write(result):
    print(result)


def restore_lcs(s, t, dp):
    lcs = ''
    i, j = len(s), len(t)

    while i >= 0 and j >= 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
            continue
        if dp[i][j] == dp[i][j - 1]:
            j -= 1
            continue
        lcs += s[i - 1]
        i -= 1
        j -= 1

    return lcs[::-1]


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Accepted

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

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

ans = []
while i > 0 and j > 0:
  if dp[i][j] == dp[i][j-1]:
    j -= 1
  elif dp[i][j] == dp[i-1][j]:
    i -= 1
  else:
    ans.append(S[i-1])
    i -= 1
    j -= 1

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

Submission status: Accepted

Solution code:
def lcs(x, y):
    dp = [[0]* (len(y)+1) for _ in range(len(x)+1)]
    

    for r in range(len(x)+1):
        for c in range(len(y)+1):
            if r == 0 or c == 0:
                dp[r][c] = 0
            elif x[r-1] == y[c-1]:
                dp[r][c] = dp[r-1][c-1] + 1
            else:
                dp[r][c] = max(dp[r-1][c], dp[r][c-1])
    
    
    lcs = []
    r = len(x)
    c = len(y)
    
    while r>0 and c>0:
        if x[r-1] == y[c-1]:
            lcs.append(x[r-1])
            r-=1
            c-=1
        elif dp[r-1][c] > dp[r][c-1]:
            r-=1
        else:
            c-=1
    print(''.join(lcs[::-1]))

x = input()
y = input()
lcs(x, y)

Submission status: Accepted

Solution code:
def lcs(s, t):
    ls = len(s)
    lt = len(t)
    d = [[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]:
                d[i][j] = d[i - 1][j - 1] + 1
            else:
                d[i][j] = max(d[i - 1][j], d[i][j - 1])

    res = ""
    i, j = ls, lt
    while i > 0 < j:
        if s[i - 1] == t[j - 1]:
            i -= 1
            j -= 1
            res += s[i]
        elif d[i - 1][j] > d[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return res[::-1]


def main():
    s = input()
    t = input()
    return lcs(s, t)


print(main())

Submission status: Accepted

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

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

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

ans = ''
x = s_len
y = t_len

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 = ans + s[x]

ans = ans[::-1]
print(ans)

Submission status: Accepted

Solution code:
s = input().strip()
t = input().strip()
ls = len(s)
lt = len(t)

dp = [[0]*(lt+1) for i 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 = ''
i, j = ls, lt
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().strip()
t = input().strip()
ls = len(s)
lt = len(t)

dp = [[0]*(lt+1) for i 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 = ''
i, j = ls, lt
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().strip()
t = " " + input().strip()
LS, LT = len(s), len(t)
dp = [[0]*LT for _ in range(LS)]
for i in range(1, LS):
    for j in range(1, LT):
        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])
a, b = (LS-1, LT-1)
r = ""
while a > 0 and b > 0:
    if s[a] == t[b]:
        r+=s[a]
        a, b = a-1, b-1
    elif dp[a][b] == dp[a-1][b]:
        a -= 1
    else:
        b -= 1

print(r[::-1])

Submission status: Accepted

Solution code:
s = input().strip()
t = input().strip()
LS, LT = len(s), len(t)
dp = [[0]*(LT+1) for _ in range(LS+1)]
dp2 = [[(0, 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
            dp2[i+1][j+1] = (i, j)
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
            if dp[i][j+1] > dp[i+1][j]:
                dp2[i+1][j+1] = (i, j+1)
            else:
                dp2[i+1][j+1] = (i+1, j)
bb = []
a, b = (LS, LT)
while a > 0 and b > 0:
    if s[a-1] == t[b-1]:
        bb.append(s[a-1])
    a, b = dp2[a][b]

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

Submission status: Accepted

Solution code:
def LCS(s, t): 
    A = []
    for i in range(len(s)+1):
        A.append([0]*(len(t)+1))
    for i in range(1, len(s)+1):
        for j in range(1, len(t)+1): 
            if s[i-1] == t[j-1]:
                A[i][j] =max(1 + A[i-1][j-1], A[i-1][j], A[i][j-1])
            else: 
                A[i][j] = max(A[i-1][j], A[i][j-1])
    dlugosc = A[-1][-1]
    i = len(s)
    j = len(t)
    odp = []
    while dlugosc > 0: 
        if s[i-1]==t[j-1] and A[i-1][j-1]+1== A[i][j]:
            odp.append(s[i-1])
            i -= 1
            j -= 1
            dlugosc -= 1
        else: 
            if A[i-1][j] == A[i][j]:
                i -= 1
            else: 
                j -= 1
    return ''.join(odp [::-1])
        
def LCS_zadanie(): 
    s = input()
    t = input()
    print(LCS(s,t))

LCS_zadanie()

Submission status: Accepted

Solution code:
def main():
    S, T = input(), input()
    L_S, L_T = len(S), len(T)
    dp = [[(0, (0, 0)) for _ in range(L_T+1)] for _ in range(L_S+1)]
    for i in range(L_S):
        for j in range(L_T):
            if S[i] == T[j]:
                dp[i+1][j+1] = (dp[i][j][0] + 1, (-1, -1))
            else:
                dp[i+1][j+1] = max((dp[i+1][j][0], (0, -1)), (dp[i][j+1][0], (-1, 0)))
    i, j = L_S, L_T
    ans = []
    while i > 0 and j > 0:
        di, dj = dp[i][j][1]
        if di != 0 and dj != 0:
            ans.append(S[i-1])
        i, j = i + di, j + dj
    print(''.join(ans[::-1]))



if __name__ == '__main__':
    main()

Submission status: Accepted

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

S = input()
T = input()

# print(S, T)

# lcs[Sのi文字目まで][Tのj文字目まで]
# 求める答えはlcs[len(S)][len(T)]
lcs = [[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]:
      lcs[i+1][j+1] = lcs[i][j] + 1
    else:
      # print(i,j)
      lcs[i+1][j+1] = max(lcs[i][j+1], lcs[i+1][j])

# print(lcs)
# print(lcs[len(S)][len(T)])

lcs_string = ""

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:# lcs[i][j] == lcs[i-1][j-1] + 1:
    lcs_string = S[i-1] + lcs_string
    i -= 1
    j -= 1

print(lcs_string)

Submission status: Accepted

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

S = input()
T = input()

# print(S, T)

# lcs[Sのi文字目まで][Tのj文字目まで]
# 求める答えはlcs[len(S)][len(T)]
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):
    if S[i-1] == T[j-1]:
      lcs[i][j] = max(lcs[i-1][j-1] + 1, lcs[i-1][j], lcs[i][j-1])
    else:
      # print(i,j)
      lcs[i][j] = max(lcs[i][j-1], lcs[i-1][j])

# print(lcs)
# print(lcs[len(S)][len(T)])

lcs_string = ""

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:# lcs[i][j] == lcs[i-1][j-1] + 1:
    lcs_string = S[i-1] + lcs_string
    i -= 1
    j -= 1

print(lcs_string)

Submission status: Accepted

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

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

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

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

ans = ''
while(s_len > 0 and t_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:
        ans = s[s_len-1]  + ans
        s_len -= 1
        t_len -= 1

print(ans)

Submission status: Accepted

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

ss = len(s)
tt = len(t)

dp = [[0 for _ in range(tt+1)] for __ in range(ss+1)]

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

i = ss
j = tt
ans = []

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

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

ans = []
i = len(s) - 1
j = len(t) - 1
while True:
    if i < 0 or j < 0:
        break
    if dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    elif dp[i+1][j+1] == dp[i][j+1]:
        i -= 1
    elif dp[i+1][j+1] == dp[i][j] + 1:
        ans.append(t[j])
        i -= 1
        j -= 1

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

Submission status: Accepted

Solution code:
S = input()
T = input()
dp = [[0 for j in range(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][j+1], dp[i+1][j])

ans = ""
row = len(S)
col = len(T)
while row > 0 and col > 0:
    if dp[row][col] == dp[row-1][col]:
        row -= 1
    elif dp[row][col] == dp[row][col-1]:
        col -= 1
    else:
        ans += S[row - 1]
        row -= 1
        col -= 1

print(ans[::-1])

Submission status: Accepted

Solution code:
def main():
    s = input()
    sl = len(s)
    t = input()
    tl = len(t)

    # dp[s][t]: value
    dp = [[(0) for _ in range(tl + 1)] for _ in range(sl + 1)]

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

    # import pprint
    # print("dp={}".format(pprint.pformat(dp)))

    ret = []
    si, ti = sl, tl
    while 0 < si and 0 < ti:
        if dp[si][ti] == dp[si - 1][ti]:
            si -= 1
        elif dp[si][ti] == dp[si][ti - 1]:
            ti -= 1
        else:
            ret.insert(0, s[si - 1])
            si -= 1
            ti -= 1

    print("".join(ret))


main()

Submission status: Accepted

Solution code:
s = input().rstrip("\n")
t = input().rstrip("\n")

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

# 任意のwについて、
# 初期条件は、dp[0][w] = 0, dp[w][0] = 0

# 貰うdpでLCSを求める
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])

# LCSとなる文字列の復元
answer = ""
i,j = len(s),len(t)
while i > 0 and j > 0:
    # dp[i-1][j] -> dp[i][j]と更新されていた場合
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    # dp[i][j-1] -> dp[i][j]と更新されていた場合
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    # dp[i-1][j-1] -> dp[i][j]と更新されていた場合
    else:
        # s[i-1] == t[i-1] なので
        # char = t[i-1]でも OK
        char = s[i-1]
        answer = char + answer
        i -= 1
        j -= 1

print(answer)

Submission status: Accepted

Solution code:
s = list(input())
t = list(input())
a = len(s)
b = len(t)
dp = [[0]*(b+1) for _ in range(a+1)]
ans = ""
#dp[i][j]はi文字目までのsとtのj文字目までの共通部分
for i in range(a):
  for j in range(b):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j]+1
    else:
      dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
i = a
j = b
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 = t[j-1]+ans
    i -= 1
    j -= 1
print(ans)

Submission status: Accepted

Solution code:
from subprocess import*
call(('pypy3','-c',"""
s=input()
t=input()
n,m=len(s),len(t)
dp=[[0]*(m+1) for i in range(n+1)]
dp[0][0]=1
for i in range(n+1):
    for j in range(m+1):
        dp[i][j]=max(dp[i][j-1],dp[i-1][j])
        if i*j!=0 and s[i-1]==t[j-1]:
            dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j])
ans=""
i,j=n,m
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:
        ans+=s[i-1]
        i-=1
        j-=1

print(ans[::-1])
"""))

Submission status: Accepted

Solution code:
S = input()
T = input()
lenS = len(S)
lenT = len(T)
dp = [[0 for _ in range(lenT+1)] for _ in range(lenS+1)]

for i in range(lenS):
  for j in range(lenT):
    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]

ans = ''
n = lenS
m = lenT
while (n>0 and m>0):
  if S[n-1] != T[m-1]:
    if dp[n-1][m] >= dp[n][m-1]: n -= 1
    else: m -= 1
  else:
    ans += S[n-1]
    n -= 1
    m -= 1
print(ans[::-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
s = list(input())[: -1]
t = list(input())[: -1]
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
mx = 0
res = []
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][j] + 1, dp[i + 1][j + 1])
      mx = max(mx, dp[i + 1][j + 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])
for i in range(len(s), 0, -1):
  for j in range(len(t), 0, -1):
    if dp[i - 1][j - 1] + 1 == dp[i][j]:
      if dp[i][j] == mx and (s[i - 1] == t[j - 1]):
        res += s[i - 1]
        mx -= 1
        break


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

Submission status: Accepted

Solution code:
S = input()
T = input()
ls = len(S)
lt = len(T)
dp = [[0] * (lt+1) for i in range(ls+1)]

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

ans = ""
while ls > 0 and lt > 0:
  if   dp[ls][lt] == dp[ls-1][lt]: ls -= 1
  elif dp[ls][lt] == dp[ls][lt-1]: lt -= 1
  else:
    ans = S[ls-1] + ans
    ls -= 1
    lt -= 1

print(ans)