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 = list(input())
t = list(input())

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

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

ans = []

i_s = len(s)
i_t = len(t)

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

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

Submission status: Accepted

Solution code:
def solve(s, t):
    n, m = len(s), len(t)
    dp = [[0] * (m+1) for _ in range(n+1)]
    s, t = ' ' + s, ' ' + t

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

    cur = dp[n][m]
    ans = ''
    while n > 0 and m > 0:
        if s[n] == t[m]:
            ans += s[n]
            cur, n, m = cur-1, n-1, m-1
        elif dp[n-1][m] == cur:
            n -= 1
        else:
            m -=1

    return ans[::-1]


def main():
    s = input()
    t = input()
    print(solve(s, t))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = input()
t = input()
n = len(s)
m = len(t)
LCS = [[0 for _ in range(m+1)] for j in range(n+1)]

for i in range(n+1):
    for j in range(m+1):
        if i==0 or j==0:
            LCS[i][j] = 0
        elif s[i-1] == t[j-1]:
            LCS[i][j] = 1+ LCS[i-1][j-1]
        else:
            LCS[i][j] = max(LCS[i-1][j],LCS[i][j-1])
i = n
j = m
st = []
while i>0 and j>0:
    if s[i-1]==t[j-1]:
        st.append(s[i-1])
        i-=1
        j-=1
    elif LCS[i][j-1]>LCS[i-1][j]:
        j-=1
    else:
        i-=1
ans = st[::-1]
a = ''.join(ans)
print(a)

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

##moji利用したらTLE
S = input()
T = input()
ls = len(S)+1
lt = len(T)+1
dp = dp2(0, ls, lt)

#moji = [['']*ls for i in range(lt)]

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

#print(moji[lt-1][ls-1])
ans = ''
i = lt-1
j = ls-1
while i > 0 and j > 0:
    if dp[i][j] > dp[i-1][j-1] and S[j-1]==T[i-1]:
        ans += S[j-1]
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        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

S = input()
T = input()
ls = len(S)+1
lt = len(T)+1

dp = dp2(0, ls, lt)

#moji = [['']*ls for i in range(lt)]
#print(moji)
for i in range(1, lt):
    for j in range(1, ls):
        if S[j-1]==T[i-1]:
            dp[i][j] = dp[i-1][j-1]+1
            #moji[i][j] = moji[i-1][j-1] + S[j-1]
        else:
            if dp[i-1][j] >= dp[i][j-1]:
                dp[i][j] = dp[i-1][j]
                #moji[i][j] = moji[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
                #moji[i][j] = moji[i][j-1]
#print(moji)
#print(moji[lt-1][ls-1])
ans = ''
i = lt-1
j = ls-1
while i > 0 and j > 0:
    if dp[i][j] > dp[i-1][j-1] and S[j-1]==T[i-1]:
        ans += S[j-1]
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1

print(ans[::-1])

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

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

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

    ans = []
    while slen > 0 and tlen > 0:
        if dp[slen][tlen] == dp[slen - 1][tlen]:
            slen -= 1
        elif dp[slen][tlen] == dp[slen][tlen - 1]:
            tlen -= 1
        else:
            slen -= 1
            tlen -= 1
            ans.append(s[slen])
    print(*ans[::-1], sep='')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = list(input())
t = list(input())
ls = len(s)
lt = len(t)
ans = []
dp = [[0] * (lt+1) for i in range(ls+1)]
for i in range(ls):
    flag = True
    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][j+1],dp[i+1][j])
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.append(s[i])
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])

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


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

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

"""
復元
"""
res = ''
n = lenS
m = lenT
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:

#EDPC_F
s=input()
t=input()
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][j+1],dp[i+1][j])
i=lens
j=lent
ans=''
while i>0 and j>0:
    if s[i-1]==t[j-1]:
        ans=s[i-1]+ans
        i-=1
        j-=1
    elif dp[i][j]==dp[i-1][j]:
        i-=1
    else:
        j-=1  
print(ans)

Submission status: Accepted

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

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

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

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

print(ans[::-1])

Submission status: Accepted

Solution code:
#EDPC_F
s=input()
t=input()
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][j+1],dp[i+1][j])
i=lens
j=lent
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
    elif dp[i][j]==dp[i-1][j-1]+1:
        ans=s[i-1]+ans
        i-=1
        j-=1
print(ans)

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
l = dp[-1][-1]
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()

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

for i in range(1, 1+len(S)):
    for j in range(1, 1 + len(T)):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1]
                       [j-1] + (S[i-1] == T[j-1]))

#print(*dp, sep='\n')
# print(dp[-1][-1])

length = dp[-1][-1]
ans = ''
i = len(S)
j = len(T)
while length > 0:
    if S[i-1] == T[j-1]:
        ans = S[i-1] + ans
        i -= 1
        j -= 1
        length -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    s = input()
    t = input()
    ls,lt = len(s),len(t)
    
    dp = [[0 for _ in range(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][j+1],dp[i+1][j])

    i += 1;j += 1
    ans = ""
    k = dp[-1][-1]
    while k:
        if dp[i-1][j] == k:
            i -= 1
        elif dp[i][j-1] == k:
            j -= 1
        else:
            k -= 1
            i -= 1
            j -= 1
            ans += s[i]
    
    print(ans[::-1])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# LongestCommonSubsequences
import numpy as np
S = np.array([ord(i)-97 for i in input()], dtype=int)
T = np.array([ord(i)-97 for i in input()], dtype=int)
Ns = len(S)
Nt = len(T)
equal = np.equal.outer(S, T).astype(int)

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


ans = ""
i, j = Ns, Nt
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans += chr(S[i-1]+97)
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1

print(ans[::-1])

Submission status: Accepted

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

dp = [[0 for _ in range(3100)] for _ in range(3100)]

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

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

ans = ""
i, j = len(s), len(t)
while dp[i][j]:
	if s[i-1] == t[j-1]:
		ans += s[i-1]
		i -= 1
		j -= 1
	else:
		if dp[i][j] == dp[i-1][j]:
			i -= 1
		else:
			j -= 1
print(ans[::-1])

Submission status: Accepted

Solution code:
# Dynamic Programming implementation of LCS problem 

def lcs(X , Y): 
	# find the length of the strings 
	m = len(X) 
	n = len(Y) 

	# declaring the array for storing the dp values 
	L = [[None]*(n+1) for i in range(m+1)] 

	"""Following steps build L[m+1][n+1] in bottom up fashion 
	Note: L[i][j] contains length of LCS of X[0..i-1] 
	and Y[0..j-1]"""
	for i in range(m+1): 
		for j in range(n+1): 
			if i == 0 or j == 0 : 
				L[i][j] = 0
			elif X[i-1] == Y[j-1]: 
				L[i][j] = L[i-1][j-1]+1
			else: 
				L[i][j] = max(L[i-1][j] , L[i][j-1]) 

	# L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1] 
	idx = L[m][n]
	ans = [''] * (idx+1)
	ans[idx] = ""

	i, j = m, n
	while i> 0 and j >0:
		if X[i-1] == Y[j-1]:
			ans[idx-1] = X[i-1]
			i-=1
			j-=1
			idx-=1
		elif L[i-1][j] > L[i][j-1]:
			i-=1
		else:
			j-=1
#end of function lcs 
	return "".join(ans)


# Driver program to test the above function 
X = input()
Y = input()

print (lcs(X, Y))

Submission status: Accepted

Solution code:
# F - LCS
from io import StringIO


def get_lcs(str_1: str, str_2: str) -> str:
    dp = [[0] * (len(str_2) + 1) for _ in range(len(str_1) + 1)]
    for i, s in enumerate(str_1):
        for j, t in enumerate(str_2):
            if s == t:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

    i, j = len(str_1), len(str_2)
    buf = StringIO()
    while i and j:
        if str_1[i - 1] == str_2[j - 1]:
            i -= 1
            j -= 1
            buf.write(str_1[i])
            continue
        if dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    buf.seek(0)
    return buf.read()[::-1]


def main():
    S, T = open(0).read().split()
    print(get_lcs(S, T))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# F - LCS
def get_lcs(str_1: str, str_2: str):
    dp = [[0] * (len(str_2) + 1) for _ in range(len(str_1) + 1)]
    for i, s in enumerate(str_1):
        for j, t in enumerate(str_2):
            if s == t:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

    i, j = len(str_1), len(str_2)
    reversed_lcs = ""
    while i and j:
        if str_1[i - 1] == str_2[j - 1]:
            i -= 1
            j -= 1
            reversed_lcs += str_1[i]
            continue
        if dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return reversed_lcs[::-1]


def main():
    S, T = open(0).read().split()
    print(get_lcs(S, T))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def get_lcs(S: str, T: str):
    N, M = len(S), len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if s == t:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

    reversed_lcs = ""
    while N and M:
        if S[N - 1] == T[M - 1]:
            N -= 1
            M -= 1
            reversed_lcs += S[N]
            continue
        if dp[N - 1][M] > dp[N][M - 1]:
            N -= 1
        else:
            M -= 1
    return reversed_lcs[::-1]


def main():
    S, T = open(0).read().split()
    print(get_lcs(S, T))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# F - LCS
def lcs(S: str, T: str) -> str:
    # dp[i][j] := the maximum length of LCS of S[:i+1] and T[:j+1]
    dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if s == t:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1)
            else:
                dp[i][j] = max(dp[i][j], dp[i - 1][j], dp[i][j - 1])

    res = ""
    i, j = len(S) - 1, len(T) - 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
        elif dp[i][j] == dp[i - 1][j - 1] + 1:
            res += S[i]
            i -= 1
            j -= 1
    return res[::-1]  # dp[-1][-1]


def main():
    S, T = open(0).read().split()
    print(lcs(S, T))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

slen = len(s)
tlen = len(t)

s = " " + s
t = " " + t

dp = [ [0]*(tlen+1) for _ in range(slen+1) ]

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

anslen = dp[slen][tlen]
i = slen
j = tlen
ans = []

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

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

Submission status: Accepted

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

# dp[i][j] : s[:i], t[:j]のLCS. ただしi==0 or j==0のとき0
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])

i = len(s)
j = 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

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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]=max(dp[i-1][j-1]+1,dp[i][j])
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
            
ans=[]
ns=len(s)-1
nt=len(t)-1

#print(dp)

while ns>-1 and nt>-1:
    #print(ns,nt)
    if s[ns]==t[nt]:
        ans.append(s[ns])
        ns-=1
        nt-=1
    elif dp[ns][nt]==dp[ns+1][nt]:
        ns-=1
    else:
        nt-=1

print("".join(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 j in range(1,len(t)+1):
    for i in range(1,len(s)+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 = []
p = len(s)
q = len(t)
len = dp[p][q]
while len > 0:
    if s[p-1] == t[q-1]:
        ans.append(s[p-1])
        len -= 1
        p -= 1
        q -= 1
    elif dp[p][q] == dp[p-1][q]:
        p -= 1
    else:
        q -= 1
an = ''.join(ans[::-1])
print(an)

Submission status: Accepted

Solution code:
from subprocess import*
call(('pypy3','-c',"""
s=input()
t=input()
a=len(s)
b=len(t)
dp=[[0]*(b+1) for i in range(a+1)]
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])
res=''
while a!=0 and b!=0:
  if dp[a][b]==dp[a-1][b]:
    a-=1
  elif dp[a][b]==dp[a][b-1]:
    b-=1
  else:
    a-=1
    b-=1
    res=s[a]+res
print(res)
"""))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
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 LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	s = IS()
	t = IS()
	n = len(s)
	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(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 (n>0  and m>0):
	    if dp[n][m] == dp[n-1][m]:
	        n -= 1
	    elif dp[n][m] == dp[n][m-1]:
	        m -= 1
	    else:
	        ans += s[n-1]
	        n -= 1
	        m -= 1
	print(ans[::-1])

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from itertools import product
from collections import deque
import sys
sys.setrecursionlimit(100000)


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


def lcs(s, t):
    S = len(s)
    T = len(t)
    dp = [[0 for j in range(T+1)] for i in range(S+1)]
    for i, j in product(range(S), range(T)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        else:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])
    maxpos = (0, 0)
    maxv = dp[0][0]
    for i, j in product(range(S), range(T)):
        if maxv < dp[i+1][j+1]:
            maxpos = (i, j)
            maxv = dp[i+1][j+1]
    return maxpos, dp


def retrieve(s, t, i, j, dp):
    x = list()
    while i >= 0 and j >= 0:
        if dp[i+1][j+1] == dp[i+1][j]:
            j -= 1
        elif dp[i+1][j+1] == dp[i][j+1]:
            i -= 1
        else:
            x.append(s[i])
            i -= 1
            j -= 1
    return ''.join(reversed(x))


def solve(s, t):
    maxpos, dp = lcs(s, t)
    i, j = maxpos
    ans = retrieve(s, t, i, j, dp)
    return ans


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Accepted

Solution code:
input = raw_input
s = input().strip()
t = input().strip()

NS = len(s)
NT = len(t)

dp = [[0] * (NT+2) for i in range(NS+2)]
dp2 = [[""] * (NT+2) for i in range(NS+2)]

for i in range(1,NS+1):
    for j in range(1,NT+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = max(dp[i-1][j-1]+1, dp[i-1][j], dp[i][j-1])
            if dp[i-1][j-1]+1 > dp[i-1][j] and dp[i-1][j-1]+1 > dp[i][j-1]:
                dp2[i][j] = dp2[i-1][j-1] + s[i-1]
            elif dp[i-1][j] > dp[i][j-1]:
                dp2[i][j] = dp2[i-1][j]
            else:
                dp2[i][j] = dp2[i][j-1]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            if dp[i-1][j] > dp[i][j-1]:
                dp2[i][j] = dp2[i-1][j]
            else:
                dp2[i][j] = dp2[i][j-1]
print(dp2[NS][NT])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a = input()
b = input()
n, m = len(a), len(b)

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

for i in range(n):
    for j in range(m):
        if a[i] == b[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")

c, d = n, m
ans = ""
while c > 0 and d > 0:
    if dp[c - 1][d] == dp[c][d]:
        c -= 1
    elif dp[c][d - 1] == dp[c][d]:
        d -= 1
    else:
        ans = a[c - 1] + ans
        c -= 1
        d -= 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

# dp[i][j] = s[:i], t[:j]の共通部分列の長さ
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][j+1], dp[i+1][j])

ans = deque()
i, j = n, m
while i and 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.appendleft(s[i])

print("".join(ans))

Submission status: Accepted

Solution code:
def rr(): return input().rstrip()
def rri(): return int(rr())
def rrl(): return list(map(int, rr().split()))
def rrt(): return tuple(map(int, rr().split()))
from collections import defaultdict
def mus(d=lambda: 0): return defaultdict(lambda: defaultdict(d))
def dd0(d=lambda: 0): return defaultdict(d)
def ms(x, y, d=0): return [[0]*y for i in range(x)]
def ar(x, d=0): return [d]*x
def ppm(m, n=0, x=0, y=0): print("\n".join(("\t".join((str(m[j][i]) for j in range(y or n))) for i in range(x or n))))
def ppa(a, n): print("\t".join(map(str, a[0:n])))
def ppl(a=0, x=[1]): x[0]=a or (x[0]+1); print("-"+"- -"*14+"-# "+str(x[0]-2)+" #-"+"- -"*14+"-")
def fltn(a): (i for sub in a for i in sub)
def yn(x): return "YES" if x else "NO"
from itertools import accumulate
from itertools import groupby
def grp(x): return ((i, sum(1 for _ in g)) for i, g in groupby(x))
import math
#def rnar(): return (*rrl(), rrl())
#def rn(): return (*rrl(),)
def dpp(a, b=""): print(")#| {} |#(o) ? {} ? (".format(a, b))

def read():
    #return rnar()
    return (rr(), rr())

def solve(s, t):
    dp = ms(len(s)+1, 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[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
    tl = dp[len(s)][len(t)]
    #ppm(dp, len(s)+1, len(t)+1)

    if tl == 0: return ''
    
    i = len(s); j = len(t)
    ts = []
    while (i > 0) and (j > 0):
        if s[i-1] == t[j-1]:
            ts.append(s[i-1])
            i -= 1; j -= 1;
        else:
            if dp[i-1][j] == dp[i][j]:
                i -= 1
            else:
                j -= 1

    ts = "".join(reversed(ts))

    return ts

if __name__ == "__main__":
    #test_count = rri()
    test_count = 1
    for _ in range(test_count):
        input_data = read()
        result = solve(*input_data)
        print(result)

Submission status: Accepted

Solution code:
tmp1 = input()
tmp2 = input()
s = ""
t = ""
if (len(tmp1)<=len(tmp2)):
    s = tmp1
    t = tmp2
else:
    t = tmp1
    s = tmp2

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

ret = ""
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]):
        ret = s[i-1] + ret
        i -= 1
        j -= 1

print(ret)

Submission status: Accepted

Solution code:
def lcs(s1,s2):
    dp = [[0 for i in range(1+len(s1))] for j in range(1+len(s2))]
    for i in range(len(s1)):
        for j in range(len(s2)):
            lis = [dp[j][i+1],dp[j+1][i]]
            if s1[i] == s2[j]:
                lis.append(dp[j][i]+1)
            dp[j+1][i+1] = max(lis)
    ans=[]
    i=len(s1)
    j=len(s2)
    while i>0 and j>0:
        if s1[i-1]==s2[j-1]:
            ans.append(s1[i-1])
            i-=1
            j-=1
        elif dp[j][i]==dp[j-1][i]:
            j-=1
        else:
            i-=1
    print(''.join(ans[::-1]))

s=input()
t=input()

lcs(s,t)

Submission status: Accepted

Solution code:
S = input()
T = input()
dp = [[-1 for i in range(len(S)+1)] for j in range(len(T)+1)]
sub = [["" for i in range(len(S)+1)] for j in range(len(T)+1)]
for a in range(len(S)+1):
	dp[0][a] = 0
for b in range(len(T)+1):
	dp[b][0] = 0
for p in range(1, len(T)+1):
	for q in range(1, len(S)+1):
		if T[p-1] == S[q-1]:
			dp[p][q] = 1 + dp[p-1][q-1]
			sub[p][q] = "c"
		else:
			if dp[p-1][q] > dp[p][q-1]:
				dp[p][q] = dp[p-1][q]
				sub[p][q] = "u"
			else:
				dp[p][q] = dp[p][q-1]
				sub[p][q] = "l"
t = len(T)
s = len(S)
out = ""
while sub[t][s] != "":
	if sub[t][s] == "c":
		out = S[s-1] + out
		t -= 1
		s -= 1
	elif sub[t][s] == "u":
		t -= 1
	else:
		s -= 1
print(out)