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

def solve(S,T):
    # print(W)
    s = len(S)
    t = len(T)
    dp = [[0]*(t+1) for _ 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])
    ans = ''
    i,j = s,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
    return ans
print(solve(S,T))

Submission status: Accepted

Solution code:
def solve():
    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] = 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])
    
    i = len(s)
    j = len(t)
    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 = s[i-1] + ans
            i -= 1
            j -= 1
    
    print(ans)

            
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
inf = float("inf")

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

len_s, len_t = len(s), len(t)
max_len = max(len_s, len_t)
dp = [[0 for j in range(max_len + 1)] for i in range(max_len + 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])

# pprint(dp)
# print(dp[len(s)][len(t)])

res = ''
i, j = len_s, len_t
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        # (i - 1, j) -> (i, j)
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        # (i, j - 1) -> (i, j)
        j -= 1
    else:
        # (i - 1, j - 1) -> (i, j)
        res = s[i - 1] + res
        i -= 1
        j -= 1

print(res)

Submission status: Accepted

Solution code:
s = input()
t = input()
x = len(s)
y = len(t)
dp = [[0]*(y+1) for _ in range(x+1)]
for i in range(x):
    for j in range(y):
        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])
        
# for i in range(x+1): print(dp[i])
ans = ""
i = x
j = y
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 numpy as np
s=np.array(list(input()))
t=np.array(list(input()))
is_eq=np.array(s[:,None]==t[None,])
# is_eq[i][j]:sのi文字目とtのj文字目が等しいかどうか
# print(is_eq)
ns=len(s)
nt=len(t)
dp=np.zeros((ns+1,nt+1),np.int64)

# dp[i+1][j+1]:sのi文字目までとtのj文字目までで最長の部分列
# dp[0][j]=0,dp[i][0]=0,dp[n+1][w+1]の値がsとtで最長の部分列の長さ
for i in range(ns): #sのi文字目までの文字列で調査
    dp[i+1][1:]=np.maximum(dp[i][:-1]+is_eq[i],dp[i][1:])#左上からの更新、真上からの更新
    dp[i+1]=np.maximum.accumulate(dp[i+1])#左からの更新
i=ns
j=nt
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.append(s[i-1])
            i-=1
            j-=1
a=''
for _ in range(len(ans)):
      a+=ans.pop()
print(a)

Submission status: Accepted

Solution code:
s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
def al(str):
    return alphabetlist.index(str)+1

dp=[[0 for i in range(0,M+1)] for i in range(0,N+1)]

for i in range(0,N):
    for j in range(0,M):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            if dp[i+1][j]>dp[i][j+1]:
                dp[i+1][j+1]=dp[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]

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

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

Submission status: Accepted

Solution code:
import sys
def ii(): 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)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

#N = ii()
#ss = [sys.stdin.readline().rstrip() for i in range(2*N)]
#for i in range(N):
S = input()
T = input()
#S = ss[2*i]
#T = ss[2*i+1]

ls, lt = len(S), len(T)
dp = dp2(0, ls+1, lt+1)
#if S[0] == T[0]:
    #dp[1][1] = 1

for i in range(lt):
    for j in range(ls):
        dp[i][j+1] = max(dp[i][j], dp[i][j+1])
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])
        if S[j] == T[i]:
            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
dp = dp2(0, ls+1, lt+1)
for i in range(1, lt+1):
    for j in range(1, ls+1):
        if S[j-1] == T[i-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
'''


i, j = lt, ls
ans = ''

while dp[i][j] != 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans += S[j-1]
        i -= 1
        j -= 1

print(ans[::-1])

Submission status: Accepted

Solution code:
import sys
def ii(): 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)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

#N = ii()
#ss = [sys.stdin.readline().rstrip() for i in range(2*N)]
#for i in range(N):
S = input()
T = input()
#S = ss[2*i]
#T = ss[2*i+1]

ls, lt = len(S), len(T)
dp = dp2(0, ls+1, lt+1)
#if S[0] == T[0]:
    #dp[1][1] = 1

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

        
        
#if not dp[lt][ls]:
    #dp[lt][ls] = max(dp[lt-1][ls], dp[lt][ls-1])

i, j = lt, ls
ans = ''

while dp[i][j] != 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans += S[j-1]
        i -= 1
        j -= 1

print(ans[::-1])

Submission status: Accepted

Solution code:
import sys
def ii(): 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)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

#N = ii()
#ss = [sys.stdin.readline().rstrip() for i in range(2*N)]
#for i in range(N):
S = input()
T = input()
#S = ss[2*i]
#T = ss[2*i+1]

ls, lt = len(S), len(T)
dp = dp2(0, ls+1, lt+1)
#if S[0] == T[0]:
    #dp[1][1] = 1

for i in range(lt+1):
    for j in range(ls+1):
        if (i < lt and j < ls) and S[j] == T[i]:
            dp[i+1][j+1] = dp[i][j] + 1
        if j < ls:
            dp[i][j+1] = max(dp[i][j], dp[i][j+1])
        if i < lt:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j])
if not dp[lt][ls]:
    dp[lt][ls] = max(dp[lt-1][ls], dp[lt][ls-1])

#print(dp[lt][ls])


i, j = lt, ls
ans = ''

while dp[i][j] != 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans += S[j-1]
        i -= 1
        j -= 1

print(ans[::-1])

Submission status: Accepted

Solution code:
a=str(input())
b=str(input())
dp=[[0 for i in range(len(a)+1)] for j in range(len(b)+1)]
ret=[]
for i in range(1,len(b)+1):
    for j in range(1,len(a)+1):
        if b[i-1]==a[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 i!=0 and j!=0:
    if dp[i][j]!=dp[i-1][j] and dp[i][j]!=dp[i][j-1]:
        ret.append(a[j-1])
        i-=1
        j-=1
    else:
        if dp[i][j]==dp[i-1][j]:
            i-=1
        else:
            j-=1

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

Submission status: Accepted

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

s_len = len(S)
t_len = len(T)
ans_array = [[0] * (s_len + 1) for _ in range(t_len + 1)]

for t in range(1, t_len + 1):
    for s in range(1, s_len + 1):
        ans_array[t][s] = max(ans_array[t - 1][s], ans_array[t][s - 1])
        if T[t - 1] == S[s - 1]:
            ans_array[t][s] = ans_array[t - 1][s - 1] + 1

# ans_r = []

# s = s_len
# t = t_len

# while s > 0 and t > 0:
#     if ans_array[t][s] == ans_array[t - 1][s]:
#         t -= 1
#     elif ans_array[t][s] == ans_array[t][s - 1]:
#         s -= 1
#     else:
#         t -= 1
#         s -= 1
#         ans_r.append(S[s])

# print("".join(reversed(ans_r)))

ans_len = ans_array[-1][-1]
ans = [""] * ans_len
s_last = s_len
t_last = t_len
for i in range(ans_len - 1, -1, -1):
    s_next = 0
    t_next = 0
    for s in range(s_last, 0, -1):
        if ans_array[t_last][s] != ans_array[t_last][s - 1]:
            s_next = s
            break
    s_last = s_next
    for t in range(t_last, 0, -1):
        if ans_array[t][s_last] != ans_array[t - 1][s_last]:
            t_next = t
            break
    ans[i] = S[s_next - 1]
    s_last = s_next - 1
    t_last = t_next - 1

print("".join(ans))

Submission status: Accepted

Solution code:
import numpy as np

s = np.array(list(input()))
t = np.array(list(input()))
dp = np.zeros((len(s) + 1, len(t) + 1), dtype=int)

is_eq = s[:, None] == t[None,]
for i in range(len(s)):
    dp[i + 1, 1:] = np.maximum(dp[i, :-1] + is_eq[i], dp[i, 1:])
    dp[i + 1] = np.maximum.accumulate(dp[i + 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]
        i -= 1
        j -= 1
print(ans[::-1])

Submission status: Accepted

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

s_len = len(S)
t_len = len(T)
ans_array = [[0] * (s_len + 1) for _ in range(t_len + 1)]

for t in range(1, t_len + 1):
    for s in range(1, s_len + 1):
        ans_array[t][s] = max(ans_array[t - 1][s], ans_array[t][s - 1])
        if T[t - 1] == S[s - 1]:
            ans_array[t][s] = ans_array[t - 1][s - 1] + 1

ans_r = []

s = s_len
t = t_len

while s > 0 and t > 0:
    if ans_array[t][s] == ans_array[t - 1][s]:
        t -= 1
    elif ans_array[t][s] == ans_array[t][s - 1]:
        s -= 1
    else:
        t -= 1
        s -= 1
        ans_r.append(S[s])

print("".join(reversed(ans_r)))

Submission status: Accepted

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

def main():
    s = input().strip()
    t = input().strip()
    n = len(s)
    m = len(t)
    dp = [[0] * (m+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            if s[i-1] == t[j-1]:
                dp[i][j] = max(dp[i-1][j-1] + 1, dp[i][j])
    
    ans_r = []
    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_r.append(s[n])
    print("".join(reversed(ans_r)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    s = input()
    t = input()
    dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]
    for i,x in enumerate(s):
        for j,y in enumerate(t):
            if x == y:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] =  max(dp[i][j+1], dp[i+1][j])

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

s,t=len(S),len(T)
#DPテーブル作成
dp=[[0]*(t+1) for _ 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] ])
# print(*dp,sep="\n")

res = ''
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:
        s -= 1
        t -= 1
        res = S[s] + res

# print(dp[s][t])
print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(s: str, t: str):
    n, m = len(s), 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+1][j], dp[i][j+1], dp[i][j] + 1)
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

    ans = ""
    while m > 0 and n > 0:
        if s[n-1] == t[m-1]:
            ans = s[n-1] + ans
            n -= 1
            m -= 1
        elif dp[n][m] == dp[n-1][m]:
            n -= 1
        else:
            m -= 1
    print(ans)


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    solve(s, t)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = ["0"] + list(input())
t = ["0"] + list(input())
n, m = len(s), len(t)
dp = [[0] * m for _ in range(n)]
for i in range(1, n):
    for j in range(1, m):
        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 = []
c = dp[n - 1][m - 1]
for i in range(n - 1, 0, -1):
    if m == 0:
        break
    for j in range(m - 1, 0, -1):
        if s[i] == t[j] and dp[i][j] == c:
            ans.append(s[i])
            c -= 1
            m = j
            break
        elif dp[i][j] < c:
            break
ans.reverse()
print("".join(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys


def solve(s, t):
    v = [0] * (len(s) + 1)
    dp = [v]
    for _, ti in enumerate(t, 1):
        u, v = v, v.copy()
        dp.append(v)
        ll, ul = 0, 0
        for j, sj in enumerate(s, 1):
            uj = u[j]
            if sj == ti:
                v[j] = 1 + ul
                ll = 1 + ul
            else:
                if ll > uj:
                    v[j] = ll
                else:
                    ll = uj
            ul = uj
    i = len(t)
    j = len(s)
    k = dp[i][j]
    selected = []
    while k > 0:
        if dp[i - 1][j] == k:
            i -= 1
        elif dp[i][j - 1] == k:
            j -= 1
        else:
            selected.append(t[i - 1])
            k -= 1
            i -= 1
            j -= 1
    return "".join(selected[::-1])


def do_job():
    "Do the work"
    s = input()
    t = input()
    result = solve(s, t)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Accepted

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

    s = input().rstrip()
    t = input().rstrip()

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

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

    for i in range(1, n + 1):
        s_ = s[i - 1]
        for j in range(1, m + 1):
            t_ = t[j - 1]
            if s_ != t_:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            else:
                dp[i][j] = dp[i - 1][j - 1] + 1
    ans = []
    while n > 0 and m > 0:
        if s[n - 1] == t[m - 1]:
            ans.append(s[n - 1])
            n -= 1
            m -= 1
        elif dp[n][m] == dp[n - 1][m]:
            n -= 1
        else:
            m -= 1
    print("".join(ans[::-1]))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    s = input().rstrip()
    t = input().rstrip()

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

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

    for i in range(1, n + 1):
        s_ = s[i - 1]
        for j in range(1, m + 1):
            t_ = t[j - 1]
            if s_ != t_:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            else:
                dp[i][j] = dp[i - 1][j - 1] + 1
    ans = []
    while n > 0 and m > 0:
        if dp[n][m] == dp[n][m - 1]:
            m -= 1
        elif dp[n][m] == dp[n - 1][m]:
            n -= 1
        else:
            ans.append(s[n - 1])
            n -= 1
            m -= 1
    print("".join(ans[::-1]))


if __name__ == '__main__':
    main()

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

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

Submission status: Accepted

Solution code:
s=input()
t=input()
sl=len(s)
tl=len(t)
dp=[[0 for i 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][j]+1,dp[i+1][j+1])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j],dp[i][j+1])

ans=str()
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]
        sl-=1
        tl-=1

print(ans[::-1])

Submission status: Accepted

Solution code:
s=input()
t=input()
sl=len(s)
tl=len(t)
dp=[[0 for i in range(tl+1)] for _ in range(sl+1)]

if s[0]==t[0]:
    dp[0][0]=1

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

ans=str()
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]
        sl-=1
        tl-=1

print(ans[::-1])

Submission status: Accepted

Solution code:
def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)
    dp = [[0] * (M+1) for _ in range(N+1)]
    
    for i in range(1, N+1):
        for j in range(1, M+1):
            p = (S[i-1] == T[j-1])
            dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + p)
            
    ans = []
    x, y = N, M
    while x and y:
        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(reversed(ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

s = np.array(list(input()), dtype='U1')
t = np.array(list(input()), dtype='U1')

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

eq = s[:, None] == t[None, :] 
dp = [np.zeros(lt + 1)]

for i in range(ls):
    prev = dp[-1].copy()
    np.maximum(prev[:-1] + eq[i], prev[1:], out=prev[1:])
    np.maximum.accumulate(prev, out=prev)
    dp.append(prev)

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

Submission status: Accepted

Solution code:
S = input()
T = input()
ls = len(S)
lt = len(T)

dp = [[0]*(lt+1) for _ in range(ls+1)]
dp[0][0] = 0
for i, s in enumerate(S):
    for j, t in enumerate(T):
        if s == t:
            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 = 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:
        ans = S[i-1] + ans
        i -= 1
        j -= 1
print(ans)

Submission status: Accepted

Solution code:

def backtrace(dp, col_str):
    res = []
    r, c = len(dp) - 1, len(dp[0]) - 1
    while dp[r][c] != 0:
        if dp[r-1][c] == dp[r][c]:
            r -= 1
        elif dp[r][c-1] == dp[r][c]:
            c -= 1
        elif dp[r-1][c-1] + 1 == dp[r][c]:
            res.append(col_str[c-1])
            r -= 1
            c -= 1

    if res == []:
        return ""
    else:
        return "".join(map(str, res[::-1]))

def solve(s, t):
    len_s, len_t = len(s), len(t)
    dp = [[0] * (len_t+1) for _ in range(len_s+1) ]

    for r in range(1, len_s+1):
        for c in range(1, len_t+1):
            if s[r-1] == t[c-1]:
                dp[r][c] = dp[r-1][c-1] + 1
            else:
                dp[r][c] = max(dp[r-1][c], dp[r][c-1])
    
    #for r in dp:
        #print(r)

    return backtrace(dp, t)

s = input()
t = input()

print(solve(s, t))

Submission status: Accepted

Solution code:
def solve(s, t):
    n, m = len(s), 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] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    sol = []
    pr, pc = n, m
    while pr > 0 and pc > 0:
        if dp[pr][pc] > dp[pr-1][pc] and dp[pr][pc] > dp[pr][pc-1]:
            sol.append(s[pr-1])
            pr -= 1
            pc -= 1
        elif dp[pr][pc-1] > dp[pr-1][pc]:
            pc -= 1
        else:
            pr -= 1
    return ''.join(reversed(sol))
  
s = input()
t = input()
print(solve(s, t))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Apr 13 22:34:56 2020

@author: ctiuser
"""

import numpy as np

s = np.array(list(input()), dtype='U1')
t = np.array(list(input()), dtype='U1')

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

eq = s[:, None] == t[None,:]
dp = [np.zeros(lt+1, int)]

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

i, j = ls, lt
ans = ''
while i > 0 and j > 0:
    if eq[i-1][j-1]:
        ans += s[i-1]
        i -= 1
        j -= 1
        
    if dp[i][j] == dp[i][j-1]:
        j -= 1
        continue
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
        continue
        
ans = ans[::-1]
print(ans)

Submission status: Accepted

Solution code:
def solve(X,Y):
    res=''
    n,m=len(X),len(Y)
    dp=[[0]*(m+1) for i in range(n+1)]
    for i in range(n):
        for j in range(m):
            if(X[i]==Y[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]])
    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-=1;j-=1
            res+=X[i]
    return res[::-1]

def main():
    X=input()
    Y=input()
    print(solve(X,Y))

if __name__=='__main__':
    main()

Submission status: Accepted

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

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

i1,i2 = len(s),len(t)
#  print(" " + s)
#  for i,row in enumerate(dp):
    #  if i == 0:
        #  print(" ",row)
    #  else:
        #  print(t[i-1],row)

rev_ans = ""
while i1 != 0:
    lru = dp[i2-1][i1-1]
    now = dp[i2][i1]
    dup = now - dp[i2-1][i1]
    dleft = now - dp[i2][i1-1]
    dupleft = now - lru
    #  print(i1,i2,dupleft,dup,dleft)
    if dupleft == 1 and dleft == 1 and dup == 1:
        rev_ans += t[i2-1]
        i2 -= 1
        i1 -= 1
    elif dleft == 1:
        i2 -= 1
    else:
        i1 -= 1

for c in reversed(rev_ans):
    print(c,end='')

Submission status: Accepted

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

ans = []
i = n - 1
j = m - 1
while i >= 0 and j >= 0:
    if i >= 0 and dp[i - 1][j] == dp[i][j]:
        i -= 1
    elif j >= 0 and dp[i][j - 1] == dp[i][j]:
        j -= 1
    else:
        ans.append(s[i])
        i -= 1
        j -= 1
print("".join(reversed(ans)))

Submission status: Accepted

Solution code:
S = input()
T = input()
m, n = len(S), len(T)
C = [[0 for j in range(n+1)] for i in range(m+1)]
for i in range(m):
    for j in range(n):
        if S[i] == T[j]:
            C[i+1][j+1] = C[i][j] + 1
        else:
            C[i+1][j+1] = max(C[i][j+1], C[i+1][j])
l = C[m][n]
X = ''
while l:
    if S[m-1] == T[n-1]:
        X = S[m-1]+X
        m -= 1
        n -= 1
        l -= 1
    elif C[m][n] == C[m-1][n]:
        m -= 1
    else:
        n -= 1
print(X)

Submission status: Accepted

Solution code:
s = input()
t = input()
lenS = len(s)
lenT = len(t)

dp = [[0]*(lenT+1)for _ in range(lenS+1)]

for i in range(1,lenS+1):
  for j in range(1,lenT+1):
    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])
      
m = lenS
n = lenT
ans = ""
while m and n:
  if dp[m][n] == dp[m-1][n]:
    m -= 1
    continue
  elif dp[m][n] == dp[m][n-1]:
    n -= 1
    continue
  else:
    m -= 1
    n -= 1
    ans = "".join([s[m],ans])
    continue
print(ans)

Submission status: Accepted

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

ans = ''
dp = [[0]*(lt+1) for _ in range(ls+1)]
for j in range(ls):
    for i in range(lt):
        if s[j]==t[i]:
            dp[j+1][i+1] = dp[j][i]+1
        else:
            dp[j+1][i+1] = max(dp[j+1][i], dp[j][i+1])

if dp[ls][lt] == 0:
    print('')
    exit()

i = lt
j = ls

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

Submission status: Accepted

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

# dp[i][j]:s[i],t[j]までで、最長の部分列の長さ
dp = [[0]*(m+1) for i in range(n+1)]

for i in range(1,n+1):
    for j in range(1,m+1):
        # s[i]とt[j]が等しいとき
        # dp[i][j]=s[i-1],t[j-1]までの最長部分列にs[i],t[j]を加えればよい
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1]  + 1
        # s[i]とt[j]が等しくないとき
        # dp[i][j]=(s[i-1],t[j]までの最長部分列)or(s[i],t[j-1]までの最長部分列)
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

res = ''
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
        res = s[n] + res
print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# E-LCS: Longest Common Subsequence


'''
axyb
abyxb
'''

import sys

sys.setrecursionlimit(4000)
S = input()
T = input()

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

# print(lcs)


def print_lcs (S, T, lcs, i, j):
    global ans
    if (i == 0 or j == 0):
        return
    if (S[i - 1] == T[j - 1]):
        print_lcs(S, T, lcs, i - 1, j - 1)
        ans.append(S[i - 1])
    else:
        if lcs[i-1][j] >= lcs[i][j-1]:
            print_lcs(S, T, lcs, i - 1, j)
        else:
            print_lcs(S, T, lcs, i, j - 1)


ans = []
print_lcs(S, T, lcs, len(S), len(T))
print("".join(ans))