Problem:


Score : 100 points

Problem Statement

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

Notes

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

Constraints

s and t are strings consisting of lowercase English letters.

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

Input

Input is given from Standard Input in the following format:

s
t

Output

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

Sample Input 1

axyb
abyxb

Sample Output 1

axb

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

Sample Input 2

aa
xayaz

Sample Output 2

aa

Sample Input 3

a
z

Sample Output 3

The answer is  (an empty string).

Sample Input 4

abracadabra
avadakedavra

Sample Output 4

aaadara



Sample input:
axyb
abyxb


Sample output:
axb

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

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

# print([list(line) for line in dp])

# restore
res = ''
i, j = ls, lt
while i > 0 and j > 0:
    if eq[i - 1][j - 1]:
        res += s[i - 1]
        i, j = i - 1, j - 1
        continue

    if dp[i - 1][j] > dp[i][j - 1]:
        i -= 1
    else:
        j -= 1

print(res[::-1])

Submission status: Accepted

Solution code:
s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0] * 3100 for _ in range(3100)]
for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    S = input()
    T = input()
    m = len(S)
    n = len(T)
    dp = [[-INF] * (n + 1) for _ in range(m + 1)]
    prev = [[(-1, -1)] * (n + 1) for _ in range(m + 1)]

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

    for i in range(m):
        for j in range(n):
            if S[i] == T[j]:
                if dp[i + 1][j + 1] < dp[i][j] + 1:
                    dp[i + 1][j + 1] = dp[i][j] + 1
                    prev[i + 1][j + 1] = (i, j)
            else:
                if dp[i + 1][j + 1] < dp[i + 1][j]:
                    dp[i + 1][j + 1] = dp[i + 1][j]
                    prev[i + 1][j + 1] = (i + 1, j)
                if dp[i + 1][j + 1] < dp[i][j + 1]:
                    dp[i + 1][j + 1] = dp[i][j + 1]
                    prev[i + 1][j + 1] = (i, j + 1)

    i, j = m, n
    res = []
    cnt = 0
    while 1:
        pi, pj = prev[i][j]
        if (pi, pj) == (-1, -1):
            break
        if i - pi == 1 and j - pj == 1:
            res.append(S[pi])
        i, j = pi, pj

    print(''.join(reversed(res)))
resolve()

Submission status: Accepted

Solution code:
from collections import deque

s = input()
t = input()
ls = len(s)
lt = len(t)
DP_len = [[0] * (lt + 1) for i in range(ls + 1)]
Prev =[[0] * (lt + 1) for i 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]:
            if max(DP_len[i - 1][j - 1] + 1, DP_len[i][j - 1], DP_len[i - 1][j]) == DP_len[i-1][j-1] + 1:
                DP_len[i][j] = DP_len[i-1][j-1] + 1
                Prev[i][j] = (i-1, j-1)
            else:
                if DP_len[i][j - 1] >= DP_len[i - 1][j]:
                    DP_len[i][j] = DP_len[i][j - 1]
                    Prev[i][j] = (i, j - 1)
                else:
                    DP_len[i][j] = DP_len[i - 1][j]
                    Prev[i][j] = (i - 1, j)

        else:
            if DP_len[i][j - 1] >= DP_len[i - 1][j]:
                DP_len[i][j] = DP_len[i][j - 1]
                Prev[i][j] = (i, j-1)
            else:
                DP_len[i][j] = DP_len[i - 1][j]
                Prev[i][j] = (i - 1, j)

x = ls
y = lt
ans = ''
while True:
    if x == 0 or y == 0:
        break
    nx, ny = Prev[x][y]
    if (nx != x) and (ny != y):
        ans = s[x-1] + ans
    x = nx
    y = ny
print(ans)

Submission status: Accepted

Solution code:
s=str(input())
t=str(input())
len_s=len(s)
len_t=len(t)
ans=""
dp=[[0 for i in range(len_t+1)] for j in range(len_s+1)]
for i in range(len_s):
    for j in range(len_t):
        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])

while len_s>0 and len_t>0:
    if dp[len_s][len_t]==dp[len_s-1][len_t]:
        len_s-=1
    elif dp[len_s][len_t]==dp[len_s][len_t-1]:
        len_t-=1
    else:
        ans=s[len_s-1]+ans
        len_s-=1
        len_t-=1
print(ans)

Submission status: Accepted

Solution code:
S = input()
T = input()
dp = [[0 for i in range(len(T)+1)] for j in range(len(S)+1)]
for i in range(1,len(S)+1):
    for j in range(1,len(T)+1):
        if S[i-1] == T[j-1]:
            dp[i][j] = 1 + dp[i-1][j-1]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1]) 

length = dp[len(S)][len(T)]
LCS = [0]*length
i = len(S)
j = len(T)
while i > 0 and j > 0: 
    if S[i-1] == T[j-1]: 
        LCS[length-1] = S[i-1]
        i-=1
        j-=1
        length-=1
    elif dp[i-1][j] > dp[i][j-1]: 
        i-=1
    else: 
        j-=1
print("".join(LCS))

Submission status: Accepted

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

"""
dp[i][j] = 長さ
i : sのi文字目まで見た状態
j : tのj文字目まで見た状態

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

dp = [[0]*3001 for i in range(3001)]
res = ""
for i in range(len(s)):
    for j in range(len(t)):
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j+1])
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i+1][j])
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1)
#復元
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:
        res = s[i-1] + res
        i -= 1
        j -= 1

print(res)

Submission status: Accepted

Solution code:
s=input()
t=input()
a=len(s)
b=len(t)
n_list=  ['' for i in range(a)]
b_list=['' for j in range(b)]
for i in range(b) :
  if s[0] in t[:i+1] :
    b_list[i]=s[0]
for i in range(a) :
  if t[0] in s[:i+1] :
    n_list[i]=t[0]

import copy
for i in range(1,b) :
  n_list1=copy.copy(n_list)
  n_list[0]=b_list[i]
  for j in range(1,a) :

    if len(n_list1[j])>len(n_list[j]) :
      n_list[j]=n_list1[j]
    if len(n_list[j-1])>len(n_list[j]) :
      n_list[j]=n_list[j-1]
    if t[i]==s[j] and len(n_list1[j-1])+1>len(n_list[j])  :
      n_list[j] = n_list1[j - 1]+t[i]

print(n_list[-1])

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

s = input()
t = input()

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

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

Submission status: Accepted

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

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

ans = []
tmp_i, tmp_j = ls, lt
while tmp_i * tmp_j > 0:
    if dp[tmp_i][tmp_j] == dp[tmp_i - 1][tmp_j]:
        tmp_i -= 1
    elif dp[tmp_i][tmp_j] == dp[tmp_i][tmp_j - 1]:
        tmp_j -= 1
    else:
        tmp_i, tmp_j = tmp_i - 1, tmp_j - 1
        ans.append(s[tmp_i])
print(''.join(ans[::-1]))

Submission status: Accepted

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

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

ans = []
tmp_i, tmp_j, cnt = ls, lt, dp[ls][lt]
while tmp_i * tmp_j > 0:
    if dp[tmp_i][tmp_j] == dp[tmp_i - 1][tmp_j]:
        tmp_i -= 1
    elif dp[tmp_i][tmp_j] == dp[tmp_i][tmp_j - 1]:
        tmp_j -= 1
    else:
        tmp_i, tmp_j = tmp_i - 1, tmp_j - 1
        ans.append(s[tmp_i])
print(''.join(ans[::-1]))

Submission status: Accepted

Solution code:
import numpy as np
def resolve():
    s = np.array(list(input()))
    t = np.array(list(input()))

    dp = np.zeros([len(s) + 1, len(t) + 1], dtype=np.int64)

    match = s.reshape(-1, 1) == t.reshape(1, -1)

    for i in range(len(s)):
        dp[i + 1][1:] = np.maximum(dp[i][:-1] + match[i], dp[i][1:])
        dp[i + 1] = np.maximum.accumulate(dp[i + 1])

    res = ''
    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
        elif dp[i][j] == dp[i - 1][j - 1] + 1:
            res = s[i - 1] + res
            i -= 1
            j -= 1

    print(res)
    
resolve()

Submission status: Accepted

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

    res = ''
    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
        elif dp[i][j] == dp[i - 1][j - 1] + 1:
            res = s[i - 1] + res
            i -= 1
            j -= 1

    print(res)
resolve()

Submission status: Accepted

Solution code:
s=input()
t=input()
N,M=len(s),len(t)
dp=[[0]*(M+1) for i in range(N+1)]
dp2=[[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
            dp2[i+1][j+1]=3
        elif dp[i][j+1]<dp[i+1][j]:
            dp[i+1][j+1]=dp[i+1][j]
            dp2[i+1][j+1]=1
        else:
            dp[i+1][j+1]=dp[i][j+1]
            dp2[i+1][j+1]=2
a=[]
while i>=0 and j>=0:
    if dp2[i+1][j+1]==1:
        j-=1
    elif dp2[i+1][j+1]==2:
        i-=1
    else:
        a.append(s[i])
        i-=1
        j-=1
print(*reversed(a),sep='')

Submission status: Accepted

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

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

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.append(s[n])

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

Submission status: Accepted

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


def solve(s: str, t: str):
    len_s = len(s)
    len_t = len(t)

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

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

    print("".join(reversed(ans)))
    return


# 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 = list(input())
t = list(input())
lens = len(s)
lent = len(t)
dp = [[0]*(lens+1) for _ in range(lent+1)]

for i in range(1,lent+1):
    x = t[i-1]
    for j in range(1,lens+1):
        y = s[j-1]
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        if x == y:
            dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1)

m = lent
n = lens
ans = ""
while m>0 and n>0:
    if dp[m][n] == dp[m-1][n]:
        m -= 1
        continue
    if dp[m][n] == dp[m][n-1]:
        n -= 1
        continue
    m -= 1
    n -= 1
    ans = t[m]+ans

print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

s = ns()
t = ns()
lenS = len(s)
lenT = len(t)

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

rest = []
m = 0
i, j = lenS, lenT
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        rest.append(s[i - 1])
        i -= 1
        j -= 1

print(*rest[::-1], sep="")

Submission status: Accepted

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

Submission status: Accepted

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

s = list(input())
t = list(input())
n = len(s)-1
m = len(t)-1
value = [[0]*(m+1) for i in range(n+1)]


for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
        elif value[i][j + 1] > value[i + 1][j]: #UP
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            value[i + 1][j + 1] = value[i + 1][j]
i = n-1
j = m-1
ans=""
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        ans = s[i] + ans
        i -= 1
        j -= 1
    elif value[i][j + 1] > value[i + 1][j]:
        i -= 1
    else:
        j -= 1
print(ans)

Submission status: Accepted

Solution code:
s,t = input(),input()
n,m=len(s),len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m):
  for j in range(n):
    if t[i] == s[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 = ""
cnt = 0
i,j = m,n
while cnt != dp[-1][-1]:
  if dp[i][j] == dp[i][j-1]:
    j -= 1
  elif dp[i][j] == dp[i-1][j]:
    i -= 1
  else:
    ans += s[j-1]
    cnt += 1
    i,j = i-1,j-1

print(ans[::-1])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
s,t=input(),input()
S,T=len(s),len(t)

DP=[[0 for _ in range(T+1)] for _ in range(S+1)]
for i in range(1,S+1):
    for j in range(1,T+1):
        if s[i-1]==t[j-1]:DP[i][j]=DP[i-1][j-1]+1
        else:DP[i][j]=max(DP[i-1][j],DP[i][j-1])

ans=""
x,y=S,T
while DP[x][y]!=0:
    if DP[x][y]==DP[x-1][y]:x -=1
    elif DP[x][y]==DP[x][y-1]:y -=1
    else:
        ans +=s[x-1]
        x -=1
        y -=1

print(ans[::-1])

Submission status: Accepted

Solution code:
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][j-1],dp[i-1][j])
ans=""
i=ls-1
j=lt-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 = s[i-1] + ans
        i-=1
        j-=1
print(ans)

Submission status: Accepted

Solution code:
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]=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])
ans=""
i=ls-1
j=lt-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 = s[i-1] + ans
        i-=1
        j-=1
print(ans)

Submission status: Accepted

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

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

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

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.append(s[n])
print(''.join(res[::-1]))

Submission status: Accepted

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

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

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], dp[i + 1][j + 1])

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

while(j > 0 and i > 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]
    i -= 1
    j -= 1

print(ans[::-1])

Submission status: Accepted

Solution code:
import numpy as np

S = np.array([ord(i) for i in input()], dtype=np.int8)
T = np.array([ord(i) for i in input()], dtype=np.int8)
LS = len(S)
LT = len(T)
equal = np.equal.outer(S, T).astype(int)

dp = [np.zeros(LT + 1, dtype=int)]
for i in range(LS):
    ndp = dp[-1].copy()
    np.maximum(ndp[:-1] + equal[i], ndp[1:], out=ndp[1:])
    np.maximum.accumulate(ndp, out=ndp)
    dp.append(ndp)


ans = []
i, j = LS, LT
while i > 0 and j > 0:
    if S[i - 1] == T[j - 1]:
        ans.append(chr(S[i - 1]))
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1
ans.reverse()
print("".join(ans))

Submission status: Accepted

Solution code:
s=list(input())
t=list(input())
dp=[[0]*(3030) for j in range(3030)]

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)])
answer=[]
i,j=len(s),len(t)
d=dp[i-1][j-1]
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:
        answer.append(s[i - 1])
        i -= 1
        j -= 1
print("".join(reversed(answer)))

Submission status: Accepted

Solution code:
s=list(input())
t=list(input())
dp=[[0]*(3030) for j in range(3030)]
ans=[]
memo=-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
             if memo < i:
                 ans.append(t[j])
                 memo = i

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

#print(dp[len(s)][len(t)])
answer=[]
i,j=len(s),len(t)
d=dp[i-1][j-1]
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:
        answer.append(s[i - 1])
        i -= 1
        j -= 1
print("".join(reversed(answer)))

Submission status: Accepted

Solution code:
import numpy as np

S = np.array([ord(i) for i in input()], dtype=int)
T = np.array([ord(i) for i in input()], dtype=int)
NS = len(S)
NT = len(T)
equal = np.equal.outer(S, T).astype(int)

dp = [np.zeros(NT + 1, dtype=int)]
for i in range(NS):
    x = dp[-1].copy()
    ndp = x.copy()
    ndp[1:] = np.maximum(x[:-1] + equal[i], ndp[1:])
    np.maximum.accumulate(ndp, out=ndp)
    dp.append(ndp)


ans = []
i, j = NS, NT
while i > 0 and j > 0:
    if S[i - 1] == T[j - 1]:
        ans.append(chr(S[i - 1]))
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1
ans.reverse()
print("".join(ans))

Submission status: Accepted

Solution code:
s = input()
t = input()
len_s = len(s)
len_t = len(t)
dp = [[0]*(len_t+1) for _ in range(len_s+1)]
# dp[i][j]はi、j文字目までのs[i],t[j]で、最長の部分列の長さ
for i in range(len_s):
    for j in range(len_t):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i][j]+1, dp[i+1][j], dp[i][j+1])

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

Submission status: Accepted

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

#dp[i+1][j+1]:Sのi文字目までとTのj文字目まででのLCSの長さ

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


#復元
res = ""
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:
        res = s[i-1] + res
        i -= 1
        j -= 1

print(res)

Submission status: Accepted

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

maxLength = [[0 for i in range(len(s)+2)] for j in range(len(t)+2)] # index_s, index_t

for i_t in range(1,len(t)+1) :
	for i_s in range(1,len(s)+1) :
		if s[i_s-1] == t[i_t-1] :
			maxLength[i_t][i_s] = max(maxLength[i_t-1][i_s-1] + 1, maxLength[i_t][i_s])
		maxLength[i_t+1][i_s] = max(maxLength[i_t+1][i_s], maxLength[i_t][i_s])
		maxLength[i_t][i_s+1] = max(maxLength[i_t][i_s+1],maxLength[i_t][i_s])

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

while( i > 0 and j > 0) :
	if maxLength[i][j] == maxLength[i-1][j] :
		i -= 1

	elif maxLength[i][j] == maxLength[i][j-1] :
		j -= 1

	else :
		str = s[j-1] + str # (j + 1)文字目
		i -= 1
		j -= 1

print(str)

Submission status: Accepted

Solution code:
s=input()
t=input()
ns,nt=len(s),len(t)
#dp=np.zeros((ns+1,nt+1),np.int64)
dp=[[0]*(nt+1) for _ in range(ns+1)]
# dp[i+1][j+1]:sのi文字目まで、tのj文字目まで考えた時の最長
for i in range(ns):
      for j in range(nt):
            if s[i]==t[j]:
                  dp[i+1][j+1]=dp[i][j]+1
            dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j],dp[i][j+1])
lg=dp[-1][-1]
ans=[]
#print(dp)
i,j=ns,nt
while i>0 and j>0:
      if dp[i][j]==dp[i][j-1]:
            j-=1
      elif dp[i][j]==dp[i-1][j]:
            i-=1
      else:
            i-=1
            j-=1
            ans.append(s[i])
s=''
for _ in range(lg):
      s+=ans.pop()
print(s)

Submission status: Accepted

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

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

  #print "      " + '  '.join(list(T))
  #for i in range(len(dp)) : print S[i-1] if i > 0 else " ", dp[i]

  res = ''
  s, t = len(S), len(T)
  while s > 0 and t > 0 :
    if S[s-1] == T[t-1] : 
      res = S[s-1] + res
      s, t = s-1, t-1
    else :
      if dp[s][t-1] > dp[s-1][t] : t -= 1
      else : s -= 1
  
  print res

LCS(S, T)

Submission status: Accepted

Solution code:
S = input()
T = input()
m, n = len(S), len(T)
DP = [[0 for j in range(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-1] == T[j-1]:
            DP[i][j] = DP[i-1][j-1] + 1
        else:
            DP[i][j] = max(DP[i][j-1], DP[i-1][j])
i, j = m, n
X = ''
while len(X) < DP[m][n]:
    if S[i-1] == T[j-1]:
        X = S[i-1] + X
        i -= 1
        j -= 1
    elif DP[i][j] == DP[i-1][j]:
        i -= 1
    elif DP[i][j] == DP[i][j]:
        j -= 1
print(X)

Submission status: Accepted

Solution code:
import numpy as np

s = np.array(list(input()))
t = np.array(list(input()))

equal = (s[:, None] == t[None, :])
ls, lt = len(s), len(t)
dp = np.zeros((ls + 1, lt + 1), dtype=int)

for i in range(ls):
    dp[i + 1][1:] = np.maximum(dp[i][1:], dp[i][:-1] + equal[i])
    dp[i + 1] = np.maximum.accumulate(dp[i + 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()
t = input()
s_length = len(s)
t_length = len(t)
dp = [[0] * (s_length + 1) for i in range(t_length + 1)]
for i in range(1, t_length + 1):
    for j in range(1, s_length + 1):
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        if t[i - 1] == s[j - 1]:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + 1)
        # print(t[i-1],s[j-1])
        #print(dp)
    #print('---')

answer = ""

while s_length >= 0 and t_length >= 0:
    if dp[t_length][s_length] == dp[t_length - 1][s_length]:
        t_length -= 1
        continue
    elif dp[t_length][s_length] == dp[t_length][s_length-1]:
        s_length -= 1
        continue
    else:
        answer += s[s_length-1]
        s_length -= 1
        t_length -= 1
#print(dp[i][j])
print(answer[::-1])

Submission status: Accepted

Solution code:
from sys import stdin


# 最大化問題
def chmax(a,b):
    if a < b: return b
    else: return a


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    s =     _in[0]   # type:str
    t =     _in[1]   # type:str
    S, T = len(s), len(t)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    dp = [[0] * (T+1) for _ in range(S+1)]  # 最大化問題
    # dp[i+1][j+1]:=sのi文字目までとtのj文字目までのLCSの長さ
    dp[0][0] = 0  # 初期条件

    # 配るDP
    for i,_s in enumerate(s):
        for j,_t in enumerate(t):
            if _s == _t:
                dp[i+1][j+1] = chmax(dp[i+1][j+1],dp[i][j]+1)
            dp[i+1][j+1] = chmax(dp[i+1][j+1],dp[i+1][j])
            dp[i+1][j+1] = chmax(dp[i+1][j+1],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
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)

Submission status: Accepted

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0 for _ in range(ls + 1)] for _ in range(lt + 1)]
for i in range(1, lt+1):
    for j in range(1, ls+1):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        if s[j-1] == t[i-1]:
            dp[i][j] = max(dp[i-1][j-1] + 1, dp[i][j-1])
ans = ''
# print(*dp, sep='\n')
while ls > 0 and lt > 0:
    if dp[lt][ls] == dp[lt-1][ls]:
        lt -= 1
    elif dp[lt][ls] == dp[lt][ls-1]:
        ls -= 1
    else:
        ans += s[ls-1]
        lt -= 1
        ls -= 1

print(ans[::-1])

Submission status: Accepted

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

path=[]

lens=len(s)
lent=len(t)
while lens>-1 and lent>-1 :
    if dp[lens][lent]==dp[lens-1][lent]:
        lens-=1
    elif dp[lens][lent]==dp[lens][lent-1]:
        lent-=1
    else:
        path.append(lens)
        lens-=1
        lent-=1

path.sort()
if path==[]:
    print("")
else:
    for i in path:
    	print(s[i-1],end="")

Submission status: Accepted

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

# 文字列の復元、後ろから見て、目的の数字見つけたら斜め上に飛ぶ
v=dp[-1][-1]
# tの飛んだ時がtの何文字目かを記録する
ans=''
while x>0 and y>0:
    # 左に移動
    if dp[x][y]==dp[x][y-1]:
        y-=1
    # 下に移動
    elif dp[x][y]==dp[x-1][y]:
        x-=1
    # 斜めに移動
    else:
        x-=1
        y-=1
        ans=t[y]+ans
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


s=data()
t=data()
dp=[[0]*(len(s)+1) for i in range(len(t)+1)]
for i in range(1,len(t)+1):
    for j in range(1,len(s)+1):
        if 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])
m=max(max(dp))
ans=''
for i in range(len(t)-1,-1,-1):
    for j in range(len(s)-1,-1,-1):
        if dp[i+1][j+1]==m and s[j]==t[i]:
            ans=s[j]+ans
            m-=1
            break
print(ans)