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:
s1=input()
s2=input()
n1,n2=len(s1),len(s2)
dp=[[-1 for j in range(n2+1)] for i in range(n1+1)]
for i in range(n1,-1,-1):
    for j in range(n2,-1,-1):
        if i==n1 or j==n2:
            dp[i][j]=0
        else:
            if s1[i]==s2[j]:
                dp[i][j]=1+dp[i+1][j+1]
            else:
                dp[i][j]=max(dp[i][j+1],dp[i+1][j])
n=""
i,j=0,0
while i<n1 and j<n2:
    if dp[i][j]==dp[i+1][j]:
        i+=1
    elif dp[i][j]==dp[i][j+1]:
        j+=1
    else:
        n+=s1[i]
        i+=1
        j+=1
print(n)

Submission status: Accepted

Solution code:
def solve(S, T):
    L1 = len(S)
    L2 = len(T)
    dp = [[0]*(L2+1) for i in range(L1+1)]

    for i in range(L1-1, -1, -1):
        for j in range(L2-1, -1, -1):
            r = max(dp[i+1][j], dp[i][j+1])
            if S[i] == T[j]:
                r = max(r, dp[i+1][j+1] + 1)
            dp[i][j] = r

    # dp[0][0] が長さの解

    # ここからは復元処理
    res = []
    i = 0; j = 0
    while i < L1 and j < L2:
        if S[i] == T[j]:
            res.append(S[i])
            i += 1; j += 1
        elif dp[i][j] == dp[i+1][j]:
            i += 1
        elif dp[i][j] == dp[i][j+1]:
            j += 1
    return "".join(res)

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

Submission status: Accepted

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

S, T = len(s), len(t)
dp = [[0]*(T+1) for _ in range(S+1)]
prev = [[(-1,-1)]*(T+1) for _ in range(S+1)]

for i in range(S):
    for j in range(T): 
        r = max(dp[i][j-1], dp[i-1][j])
        p = (i, j-1) if r == dp[i][j-1] else (i-1, j)
        if s[i] == t[j]:
            r = max(dp[i-1][j-1] + 1, r) 
            p = (i-1, j-1) if r == dp[i-1][j-1] + 1 else p
        dp[i][j] = r
        prev[i][j] = p


ans = ''
i, j = S - 1, T - 1
while i >= 0 and j >= 0:
    if prev[i][j] == (i-1, j-1):
        ans += s[i]
    i, j = prev[i][j]

print(ans[::-1])

Submission status: Accepted

Solution code:
#!python3

# input
s = input()
t = input()


def main():
    sn, tn = len(s), len(t)
    dp = [[0] * (tn + 1) for _ in range(sn + 1)]
    w = [[None] * (tn + 1) for _ in range(sn + 1)]
    for i in range(1, sn + 1):
        for j in range(1, tn + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                w[i][j] = s[i - 1]
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
    ans = []
    i, j = sn, tn
    while i != 0 and j != 0:
        if s[i - 1] == t[j - 1]:
            ans.append(w[i][j])
            i, j = i - 1, j - 1
        else:
            if dp[i][j - 1] < dp[i - 1][j]:
                i -= 1
            else:
                j -= 1
    print("".join(ans[::-1]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def longest_common_subsequence(S, T):
    """compute table dp satisfying: 
    dp[i,j] = LCS(S[:i], T[:j])"""
    LS, LT = len(S), len(T)
    dp = np.zeros((LS + 1, LT + 1), np.int32)
    for n in range(1, LS + 1):
        dp[n, 1:] = dp[n - 1, :-1] + (S[n - 1] == T)  # 左上から
        np.maximum(dp[n], dp[n - 1], out=dp[n])  # 上から
        np.maximum.accumulate(dp[n], out=dp[n])  # 左から
    return dp

def reconstruct_LCS(S, T, dp):
    tmp = []
    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if S[i - 1] == T[j - 1]:
            i, j = i - 1, j - 1
            tmp.append(S[i])
        elif dp[i, j] == dp[i - 1, j]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(tmp))

S = np.array(list(readline().decode()), 'U1')[:-1]
T = np.array(list(readline().decode()), 'U1')[:-1]

dp = longest_common_subsequence(S, T)

print(reconstruct_LCS(S, T, dp))

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def longest_common_subsequence(S, T):
    """compute table dp satisfying: 
    dp[i,j] = LCS(S[:i], T[:j])"""
    LS, LT = len(S), len(T)
    dp = np.zeros((LS + 1, LT + 1), np.int32)
    for n in range(1, LS + 1):
        dp[n, 1:] = dp[n - 1, :-1] + (S[n - 1] == T)  # 左上から
        np.maximum(dp[n], dp[n - 1], out=dp[n])  # 上から
        np.maximum.accumulate(dp[n], out=dp[n])  # 左から
    return dp


def reconstruct_LCS(S, T, dp):
    tmp = []
    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if S[i - 1] == T[j - 1]:
            i, j = i - 1, j - 1
            tmp.append(S[i])
        elif dp[i, j] == dp[i - 1, j]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(tmp))

S = np.array(list(readline().decode()), 'U1')[:-1]
T = np.array(list(readline().decode()), 'U1')[:-1]
dp = longest_common_subsequence(S, T)

print(reconstruct_LCS(S, T, dp))

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = np.array(list(readline().decode()), 'U1')[:-1]
T = np.array(list(readline().decode()), 'U1')[:-1]

def longest_common_subsequence(S, T):
    """compute table dp satisfying: 
    dp[i,j] = LCS(S[:i], T[:j])"""
    LS, LT = len(S), len(T)
    dp = np.zeros((LS + 1, LT + 1), np.int32)
    for n in range(1, LS + 1):
        dp[n, 1:] = dp[n - 1, :-1] + (S[n - 1] == T)  # 左上から
        np.maximum(dp[n], dp[n - 1], out=dp[n])  # 上から
        np.maximum.accumulate(dp[n], out=dp[n])  # 左から
    return dp

dp = longest_common_subsequence(S, T)

answer = []
i, j = len(S), len(T)
while i > 0 and j > 0:
    if dp[i, j] == dp[i - 1, j - 1] + (S[i - 1] == T[j - 1]):
        i, j = i - 1, j - 1
        if S[i] == T[j]:
            answer.append(S[i])
    elif dp[i, j] == dp[i - 1, j]:
        i -= 1
    elif dp[i, j] == dp[i, j - 1]:
        j -= 1
    else:
        raise ValueError

answer = ''.join(reversed(answer))
print(answer)

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)]
#print(lcs(s,t,0,0," ",dp))

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

x=len(s)
y=len(t)
ans=""
while x!=0 and y!=0:
    if dp[x-1][y]==dp[x][y]:
        x-=1
    elif dp[x][y-1]==dp[x][y]:
        y-=1
    else:
        ans=t[y-1]+ans
        x-=1
        y-=1
print(ans)

Submission status: Accepted

Solution code:
def solve():
    Ss = input().rstrip()
    Ts = input().rstrip()

    lenS, lenT = len(Ss), len(Ts)

    dp = [[0]*(lenT+1) for _ in range(lenS+1)]
    for iS, S in enumerate(Ss, start=1):
        dp0 = dp[iS-1]
        dpi = dp[iS]
        for jT, T in enumerate(Ts, start=1):
            if S == T:
                dpi[jT] = dp0[jT-1] + 1
            else:
                dpi[jT] = dpi[jT-1]
                if dp0[jT] > dpi[jT]:
                    dpi[jT] = dp0[jT]

    anss = ''
    iS, jT = lenS, lenT
    while True:
        if Ss[iS-1] == Ts[jT-1]:
            anss += Ss[iS-1]
            iS, jT = iS-1, jT-1
        elif dp[iS-1][jT] >= dp[iS][jT-1]:
            iS -= 1
        else:
            jT -= 1
        if iS == 0 or jT == 0:
            break

    print(anss[::-1])


solve()

Submission status: Accepted

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


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

for i in range(len(s)):
    for j in range(len(t)):
        if i==0:
            if s[i]==t[j]:
                dp[i][j]=1
            else:
                dp[i][j]=dp[i][j-1] if j>=1 else 0
        elif j==0:
            if s[i]==t[j]:
                dp[i][j]=1
            else:
                dp[i][j]=dp[i-1][j]
        else:
            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])

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

L=dp[i][j]

while L>=1:
    if i==0 and dp[i][j]==1:
        result+=s[i]
        L-=1
    elif j==0 and dp[i][j]==1:
        result+=t[j]
        L-=1
    elif dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        result+=t[j]
        L-=1
        i-=1
        j-=1


print(result[::-1])

Submission status: Accepted

Solution code:
s=input()
t=input()
n = len(s)
m = len(t)
dp=[]
for i in range(n+1):
    dp.append([0]*(m+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] = 1 + dp[i-1][j-1]
        else:
            dp[i][j] = max(dp[i-1][j],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+=s[i-1]
        i-=1
        j-=1
print(ans[::-1])

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

####################################################
# LCS(longest common sequence)
# 部分列で最長の共通のもの
####################################################

# dp[i+1][j+1]:= s の i 文字目までと t の j 文字目まででの LCS の長さ

import numpy as np

def main():
    S = np.array(list(input()), dtype='unicode')
    T = np.array(list(input()), dtype='unicode')
    ls = len(S)
    lt = len(T)

    equal = S[:, None] == T[None,:]
#    print(eq)

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

#    for i in range(ls):
#        for j in range(lt):
#            dp[i+1][j+1] = max(dp[i][j+1], dp[i][j]+ eq[i][j])
#            dp[i+1][j+1] = max(dp[i+1][j+1] , dp[i+1][j])

#    print(dp)

    # 復元
    res = ''
    i, j = ls, lt
    while (i > 0 and j > 0):
        # (i-1, j) -> (i, j) と更新されていた場合
        if dp[i][j] == dp[i-1][j]:
            i-=1   # DP の遷移を遡る
        # (i, j-1) -> (i, j) と更新されていた場合
        elif dp[i][j] == dp[i][j-1]:
            j-=1   # DP の遷移を遡る
        # (i-1, j-1) -> (i, j) と更新されていた場合
        else:
            res += S[i-1]
            # このとき s[i-1] == t[j-1] なので、t[j-1] + res でも OK
            i-=1
            j-=1   # DP の遷移を遡る
    print(res[::-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

####################################################
# LCS(longest common sequence)
# 部分列で最長の共通のもの
####################################################

# dp[i+1][j+1]:= s の i 文字目までと t の j 文字目まででの LCS の長さ

import numpy as np

def main():
    S = np.array(list(input()), dtype='unicode')
    T = np.array(list(input()), dtype='unicode')
    ls = len(S)
    lt = len(T)

    equal = S[:, None] == T[None,:]
#    print(eq)

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

#    for i in range(ls):
#        for j in range(lt):
#            dp[i+1][j+1] = max(dp[i][j+1], dp[i][j]+ eq[i][j])
#            dp[i+1][j+1] = max(dp[i+1][j+1] , dp[i+1][j])

#    print(dp)

    # 復元
    res = ''
    i, j = ls, lt
    while (i > 0 and j > 0):
        # (i-1, j) -> (i, j) と更新されていた場合
        if dp[i][j] == dp[i-1][j]:
            i-=1   # DP の遷移を遡る
        # (i, j-1) -> (i, j) と更新されていた場合
        elif dp[i][j] == dp[i][j-1]:
            j-=1   # DP の遷移を遡る
        # (i-1, j-1) -> (i, j) と更新されていた場合
        else:
            res = S[i-1] + res
            # このとき s[i-1] == t[j-1] なので、t[j-1] + res でも OK
            i-=1
            j-=1   # DP の遷移を遡る
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for i,c in enumerate(s):
    for j,d in enumerate(t):
        if c==d:
            dp[i+1][j+1]=dp[i][j]+1
            ans[i+1][j+1]=(i,j)
        else:
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
            ans[i+1][j+1]=ans[i][j+1] if dp[i+1][j+1]==dp[i][j+1] else ans[i+1][j]

i=len(s)
j=len(t)
ss=['']*dp[i][j]
l=dp[i][j]-1
while i>0 and j>0:
    i,j=ans[i][j]
    if i>-1:
        ss[l]=s[i]
        l-=1

print(''.join(ss))

Submission status: Accepted

Solution code:
s1=input()
s2=input()
l1=len(s1)
l2=len(s2)
dp=[[0 for i in range(l2+1)] for j in range(l1+1)]
for i in range(1,l1+1):
    for j in range(1,l2+1):
        if s1[i-1]==s2[j-1]:
            dp[i][j]=1+dp[i-1][j-1]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
i=l1;j=l2
ans=""
while(i>0 and j>0):
    if s1[i-1]==s2[j-1]:
        ans=s1[i-1]+ans
        i-=1
        j-=1
    else:
        if dp[i-1][j]>dp[i][j-1]:
            i-=1
        else:
            j-=1
print(ans)

Submission status: Accepted

Solution code:
import numpy
s = numpy.array(list(input()))
t = numpy.array(list(input()))
ns = len(s)
nt = len(t)
match = s.reshape(-1,1) == t.reshape(1,-1)
memo = numpy.zeros([ns+1, nt+1], dtype = int)
for i in range(ns):
    memo[i+1, 1:] = numpy.fmax(memo[i, :-1]+match[i], memo[i, 1:])
    
    memo[i+1] = numpy.maximum.accumulate(memo[i+1])
ans = []
while ns >0 and nt>0:
    if memo[ns, nt] == memo[ns-1, nt]:
        ns -= 1
    elif memo[ns, nt] == memo[ns, nt-1]:
        nt -= 1
    else:
        ans.append(s[ns-1])
        
        nt-=1
        ns -=1
print("".join(ans[::-1]))

Submission status: Accepted

Solution code:
s=input()
t=input()
n=len(t)
m=len(s)
dp=[[0]*(n+1) for i in range(m+1)]
for i in range(m):
  for j in range(n):
    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])

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


kotae.reverse()
kotae = "".join(kotae)
print(kotae)

Submission status: Accepted

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

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

ans = []
s_i = len(s)
t_i = len(t)
while s_i > 0 and t_i > 0:
    if dp[s_i][t_i] == dp[s_i][t_i-1]:
        t_i -= 1
    elif dp[s_i][t_i] == dp[s_i-1][t_i]:
        s_i -= 1
    else: #dp[s_i][t_i]  dp[s_i-1][t_i] == 1:
        s_i -= 1
        t_i -= 1
        if t_i >= 0:
            ans.append(t[t_i])


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

Submission status: Accepted

Solution code:
s = input()
t = input()
dp = [[0] * (len(s)+1) for _ in range(len(t)+1)]
for i in range(1, len(t)+1):
    ti = t[i-1]
    dp[i] = dp[i-1][:]
    for j in range(1, len(s)+1):
        if ti == s[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 = ''
sl = len(s)
tl = len(t)
while sl > 0 and tl > 0:
    if s[sl-1] == t[tl-1]:
        sl -= 1
        tl -= 1
        ans = s[sl] + ans
        continue
    if dp[tl][sl] == dp[tl][sl-1]:
        sl -= 1
    elif dp[tl][sl] == dp[tl-1][sl]:
        tl -= 1
print(ans)

Submission status: Accepted

Solution code:
s=input()
t=input()
dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            dp[i+1][j+1]=max(dp[i+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="".join([s[i-1],res])
        i-=1
        j-=1
print(res)

Submission status: Accepted

Solution code:
# F LCS

s = input()
t = input()

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

ans = []

for i,_s in enumerate(s):
    for j,_t in enumerate(t):
        dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
        if _s == _t:
            dp[i+1][j+1] = max(dp[i][j]+1,dp[i+1][j+1])

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

print(*(list(reversed(ans))),sep="")

Submission status: Accepted

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

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

revlst = []

lt -= 1
ls -= 1
while dp[lt][ls] != 0:
    while dp[lt][ls] == dp[lt-1][ls]:
        lt -= 1
    while dp[lt][ls] == dp[lt][ls-1]:
        ls -= 1
    revlst.append(lt)
    lt -= 1
    ls -= 1

ans = ''.join([t[_-1] for _ in reversed(revlst)])
print(ans)

Submission status: Accepted

Solution code:
a = input()
b = input()
n = len(a)
m = len(b)
dp = [[0 for i in range(m + 1)] for j in range(n + 1)]

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

lim = dp[-1][-1]

i = n
j = m
ans = [None] * (lim)
while i > 0 and j > 0:

    if a[i - 1] == b[j - 1]:
        ans[lim-1] = a[i - 1]
        i -= 1
        j -= 1
        lim -= 1

    else:
        if dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
if ans:
    print("".join(ans))
else:
    print(' ')

Submission status: Accepted

Solution code:
s = list(input())
t = list(input())
ns=len(s)
nt=len(t)
dp=[[0]*(nt+1) for _ in range(ns+1)]
for i in range(ns):
    for j in range(nt):
        if s[i]==t[j]:
            dp[i+1][j+1]=max(dp[i+1][j+1], dp[i][j]+1)
        else:
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
ans=[]
i,j=ns,nt
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(''.join(ans))

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

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 += t[j-1]
        i -= 1
        j -= 1
print(ans[::-1])

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_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')
mod = 10**9 + 7
#from decimal import *
		
s = input()
t = input()

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



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


y = len(s)
x = len(t)
ans = ""
while 1:
	#print(y, x, ans)
	if x*y == 0:
		break
	elif s[y-1] == t[x-1]:
		ans += s[y-1]
		x -= 1
		y -= 1
	else:
		if dp[y][x] == dp[y-1][x]:
			y -= 1
		elif dp[y][x] == dp[y][x-1]:
			x -= 1

lcs  = dp[len(s)][len(t)]

q = deque([(len(s), len(t))])
common = [set() for _ in range(lcs)]

while q:
	#print(q)
	y, x =q.popleft()
	if x*y != 0 :
		if s[y-1] == t[x-1]:
			common[dp[y][x]-1].add(t[x-1])
			y -= 1
			x -= 1
			q.append((y, x))
		else:
			if dp[y][x] == dp[y-1][x]:
				q.append((y-1, x))

			elif dp[y][x] == dp[y][x-1]:
				q.append((y, x-1))

print(*[list(common[i])[0] for i in range(lcs)], sep="")

Submission status: Accepted

Solution code:
s1=input()
s2=input()
n=len(s1)
m=len(s2)
# import numpy as np
dp=[[0 for i in range(m+1)]for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        if s1[i-1]==s2[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# print(np.array(dp))
ans=""
# print(dp[-1][-1])
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=s1[i-1]+ans
        i-=1
        j-=1
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s = input()
t = input()

S,T = len(s),len(t)
dp = [[0 for _ in range(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] = 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])
# dpの終点から文字列を復元していく
ans=''
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:
    ans = s[S-1] + ans
    S -=1
    T -=1
print(ans)

Submission status: Accepted

Solution code:
def main():
    s = input()
    t = input()
    sn = len(s)
    tn = len(t)
    dp = [[0] * (tn + 1) for _ in range(sn + 1)]
    for i in range(1, sn + 1):
        for j in range(1, tn + 1):
            if s[i - 1] == t[j - 1]:
                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] = max(dp[i][j], dp[i][j - 1])
    ans = []
    i, j = sn, tn
    while i > 0 and j > 0:
        if dp[i][j] == dp[i][j - 1]:
            j -= 1
        elif dp[i][j] == dp[i - 1][j]:
            i -= 1
        else:
            ans.append(s[i - 1])
            i -= 1
            j -= 1
    print(''.join(ans[::-1]))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

s = readline().rstrip()
t = readline().rstrip()
 
def LCS(X,Y):
    XL = len(X)
    YL = len(Y)
    dp = [[0 for j in range(YL+1)] for i in range(XL+1)]
    for i in range(XL):
        for j in range(YL):
            if X[i] == Y[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])
    # 以下復元
    S = ''
    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,j = i-1,j-1
            S += X[i]
    S = S[::-1]
    return S
 
print(LCS(s,t))

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=S()
  t=S()

  ns=len(s)
  nt=len(t)

  dp=[[0]*(ns+1) for _ in range(nt+1)]

  for i in range(nt):
    for j in range(ns):
      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=[]
  i=nt
  j=ns
  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
    elif dp[i][j]==dp[i-1][j-1]:
      i-=1
      j-=1
    elif dp[i][j]==dp[i-1][j-1]+1:
      i-=1
      j-=1
      ans.append(t[i])

  ans.reverse()
  return ''.join(ans)

# main()
print(main())

Submission status: Accepted

Solution code:
X = input()
Y = input()
dp = [[0 for j in range(len(Y)+1)] for i in range(len(X)+1)]
fxy = [[(0, 0) for j in range(len(Y)+1)] for i in range(len(X)+1)]
for i in range(len(X)):
    for j in range(len(Y)):
        if X[i] == Y[j]:
            dp[i+1][j+1] = dp[i][j] + 1
            fxy[i+1][j+1] = (i, j)
        elif dp[i+1][j] >= dp[i][j+1]:
            dp[i+1][j+1] = dp[i+1][j]
            fxy[i+1][j+1] = (i+1, j)
        else:
            dp[i+1][j+1] = dp[i][j+1]
            fxy[i+1][j+1] = (i, j+1)
ans = ''
px, py = -1, -1
while not(px == py == 0):
    cx, cy = fxy[px][py]
    if dp[px][py] != dp[cx][cy]:
        ans += X[cx]
    px, py = cx, cy
print(ans[::-1])
# for i in range(len(X)+1):
#     print(dp[i])
# for i in range(len(X)+1):
#     print(fxy[i])

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    S = readline().strip()
    T = readline().strip()
    N, M = len(S), len(T)

    dp = [[0] * (M + 1) for _ in range(N + 1)]
    prev = [[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
                prev[i + 1][j + 1] = (i, j)
            elif dp[i + 1][j] > dp[i][j + 1]:
                dp[i + 1][j + 1] = dp[i + 1][j]
                prev[i + 1][j + 1] = (i + 1, j)
            else:
                dp[i + 1][j + 1] = dp[i][j + 1]
                prev[i + 1][j + 1] = (i, j + 1)

    ans = []
    i, j = N, M
    while i and j:
        p, q = prev[i][j]
        if i > p and j > q:
            ans.append(S[p])
        i, j = p, q

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
s=input()
t=input()
dp=[[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
for i,sele in enumerate(s):
  for j ,tele in enumerate(t):
    if sele==tele:
      dp[i+1][j+1]=dp[i][j] +1
    else :
      dp[i+1][j+1]=dp[i+1][j] if dp[i+1][j]>=dp[i][j+1] else dp[i][j+1]     
res=""
i=len(s)
j=len(t)
#print(dp)
while True:
#for k in range(9):
  #rint(i,j,dp[i][j])
  if i-1>=0:
    if dp[i-1][j]==dp[i][j]:
      i=i-1
      continue
  if j-1>=0:
    if dp[i][j-1]==dp[i][j]:
      j=j-1
      continue
  if i-1>=0 and j-1>=0:
    if dp[i-1][j-1]==dp[i][j]-1:
      j=j-1
      i=i-1
      res=s[i]+res
      #print(i,res)
      if dp[i][j]==0:
        break
      continue
  break
print(res)

Submission status: Accepted

Solution code:
import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

def LCS(s, t):
	n, m = len(s), len(t)
	dp = [[0 for i 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:
				dp[i][j] = 0
			elif 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])
	index = dp[n][m]
	ans = [" "]*index
	i, j = n, m
	while index:
		if s[i-1] == t[j-1]:
			ans[index-1] =  s[i-1]
			index -= 1
			i -= 1; j -= 1
		elif dp[i-1][j] > dp[i][j-1]:
			i -= 1
		else:
			j -= 1
	return(("").join(ans))

def solve():
	s1 = inp().strip(); s2 = inp().strip()
	print(LCS(s1, s2))


if __name__ == "__main__":
	solve()

Submission status: Accepted

Solution code:
n=input()
m=input()
x=len(n)
 
y=len(m)
 
dp=[[0 for i in range(y+1)] for j in range(x+1)]
#print(len(dp),len(dp[0]))
for i in range(0,x+1):
  for j in range(0,y+1):
    if(i==0 or j==0):
      dp[i][j]=0
    elif n[i-1]==m[j-1]:
      dp[i][j]=1+dp[i-1][j-1]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
 
i=x
j=y
ans=""
 
while i>0 and j>0:
    if(n[i-1]==m[j-1]):
        ans=ans+n[i-1]
        #print(n[i-1],1)
        i=i-1
        j=j-1
    else:
        mx=max(dp[i-1][j],dp[i][j-1])
        if mx==dp[i-1][j]:
            i=i-1
        else:
            j=j-1
print(ans[::-1])

Submission status: Accepted

Solution code:
n=input()
m=input()
x=len(n)

y=len(m)

dp=[[0 for i in range(y+1)] for j in range(x+1)]
#print(len(dp),len(dp[0]))
for i in range(0,x+1):
  for j in range(0,y+1):
    if(i==0 or j==0):
      dp[i][j]=0
    elif n[i-1]==m[j-1]:
      dp[i][j]=1+dp[i-1][j-1]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
j=y
i=x
ans=""
#print(i,j)
while i>0 and j>0:
    if(n[i-1]==m[j-1]):
        #print(n[i-1],m[j-1])
        ans=ans+n[i-1]
        #print(n[i-1],1)
        i=i-1
        j=j-1
    else:
        mx=max(dp[i-1][j],dp[i][j-1])
        if mx==dp[i-1][j]:
            i=i-1
        else:
            j=j-1
print(ans[::-1])

Submission status: Accepted

Solution code:
n=input()
m=input()
x=len(n)

y=len(m)

dp=[[0 for i in range(y+1)] for j in range(x+1)]
#print(len(dp),len(dp[0]))
for i in range(0,x+1):
  for j in range(0,y+1):
    if(i==0 or j==0):
      dp[i][j]=0
    elif n[i-1]==m[j-1]:
      dp[i][j]=1+dp[i-1][j-1]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
j=y
i=x
ans=""
#print(i,j)
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 = n[i-1]+ans
    i -= 1
    j -= 1
print(ans)