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: Time Limit Exceeded

Solution code:
*S, = map(ord, input())
*T, = map(ord, input())
LS = len(S); LT = len(T)

dp = [[-1]*(LT+1) for i in range(LS+1)]
nxt = [[(0, None, None)]*(LT+1) for i in range(LS+1)]
P = [[None]*(LT+1) for i in range(LS+1)]
Q = [[None]*(LT+1) for i in range(LS+1)]
R = [[0]*(LT+1) for i in range(LS+1)]
for i in range(LS-1, -1, -1):
    for j in range(LT-1, -1, -1):
        r0 = dp[i+1][j]; r1 = dp[i][j+1]
        r = max(r0, r1)
        if r0 < r1:
            rr = 0; p0 = i; q0 = j+1
        else:
            rr = 0; p0 = i+1; q0 = j
        if S[i] == T[j]:
            r2 = dp[i+1][j+1] + 1
            if r < r2:
                r = r2
                rr = 1; p0 = i+1; q0 = j+1
        dp[i][j] = r
        R[i][j] = rr
        P[i][j] = p0; Q[i][j] = q0

i = j = 0
ans = []
while i is not None:
    if R[i][j]:
        ans.append(S[i])
    i, j = P[i][j], Q[i][j]
print(*map(chr, ans), sep='')

Submission status: Time Limit Exceeded

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

# dp[i][j] := Sのi文字目, Tのj文字目まで見た場合のLCS
dp = [[''] * (len(T) + 1) for i in range(len(S) + 1)]

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

print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
LS = len(S); LT = len(T)

dp = [[-1]*(LT+1) for i in range(LS+1)]
nxt = [[(0, None, None)]*(LT+1) for i in range(LS+1)]
P = [[None]*(LT+1) for i in range(LS+1)]
Q = [[None]*(LT+1) for i in range(LS+1)]
R = [[0]*(LT+1) for i in range(LS+1)]
for i in range(LS-1, -1, -1):
    for j in range(LT-1, -1, -1):
        r0 = dp[i+1][j]; r1 = dp[i][j+1]
        r = max(r0, r1)
        if r0 < r1:
            rr = 0; p0 = i; q0 = j+1
        else:
            rr = 0; p0 = i+1; q0 = j
        if S[i] == T[j]:
            r2 = dp[i+1][j+1] + 1
            if r < r2:
                r = r2
                rr = 1; p0 = i+1; q0 = j+1
        dp[i][j] = r
        R[i][j] = rr
        P[i][j] = p0; Q[i][j] = q0

i = j = 0
ans = []
while i is not None:
    if R[i][j]:
        ans.append(S[i])
    i, j = P[i][j], Q[i][j]
print(*ans, sep='')

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
LS = len(S); LT = len(T)

dp = [[-1]*(LT+1) for i in range(LS+1)]
nxt = [[(0, None, None)]*(LT+1) for i in range(LS+1)]
for i in range(LS-1, -1, -1):
    for j in range(LT-1, -1, -1):
        r0 = dp[i+1][j]; r1 = dp[i][j+1]
        r = max(r0, r1)
        x = (0, i, j+1) if r0 < r1 else (0, i+1, j)
        if S[i] == T[j]:
            r2 = dp[i+1][j+1] + 1
            if r < r2:
                r = r2
                x = (1, i+1, j+1)
        dp[i][j] = r
        nxt[i][j] = x

i = j = 0
ans = []
while i is not None:
    m, i0, j = nxt[i][j]
    if m:
        ans.append(S[i])
    i = i0
print(*ans, sep='')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)

S = input()
T = input()
LS = len(S); LT = len(T)

memo = [[-1]*LT for i in range(LS)]
nxt = [[(0, None, None)]*(LT+1) for i in range(LS+1)]
def dfs(i, j):
    if i == LS or j == LT:
        return 0
    if memo[i][j] != -1:
        return memo[i][j]
    r0 = dfs(i+1, j); r1 = dfs(i, j+1)
    r = max(r0, r1)
    x = (0, i, j+1) if r0 < r1 else (0, i+1, j)
    if S[i] == T[j]:
        r2 = dfs(i+1, j+1) + 1
        if r < r2:
            r = r2
            x = (1, i+1, j+1)
    memo[i][j] = r
    nxt[i][j] = x
    return r

dfs(0, 0)
i = j = 0
ans = []
while i is not None:
    m, i0, j = nxt[i][j]
    if m:
        ans.append(S[i])
    i = i0
print(*ans, sep='')

Submission status: Time Limit Exceeded

Solution code:
def lcs(X, Y, m, n): 
    L = [[0 for x in range(n+1)] for x in range(m+1)] 
  
    # Following steps build L[m+1][n+1] in bottom up fashion. Note 
    # that 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]) 
  
    # Following code is used to print LCS 
    index = L[m][n] 
  
    # Create a character array to store the lcs string 
    lcs = [""] * (index+1) 
    lcs[index] = "" 
  
    # Start from the right-most-bottom-most corner and 
    # one by one store characters in lcs[] 
    i = m 
    j = n 
    while i > 0 and j > 0: 
  
        # If current character in X[] and Y are same, then 
        # current character is part of LCS 
        if X[i-1] == Y[j-1]: 
            lcs[index-1] = X[i-1] 
            i-=1
            j-=1
            index-=1
  
        # If not same, then find the larger of two and 
        # go in the direction of larger value 
        elif L[i-1][j] > L[i][j-1]: 
            i-=1
        else: 
            j-=1
    ans = ""
    for i in range(len(lcs)):
      ans += lcs[i]
    print(ans)
  
# Driver program 
X = input()
Y = input()
m = len(X) 
n = len(Y) 
lcs(X, Y, m, n)

Submission status: Accepted

Solution code:
s=input()
t=input()
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]=dp[i][j]+1
    else:dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j],dp[i+1][j+1])
ans=''
while n*m:
  if s[n-1]==t[m-1]:
    ans+=s[n-1]
    n-=1
    m-=1
  else:
    if dp[n-1][m]>dp[n][m-1]:n-=1
    else:m-=1
print(ans[::-1])

Submission status: Accepted

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

dp = [[0]*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])

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

Submission status: Accepted

Solution code:
string1 = input()
string2 = input()

dp = [[0 for i in range(len(string1) + 1)] for j in range(len(string2) + 1)]
substring = ""
for i in range(len(string2) + 1):
    for j in range(len(string1) + 1):
        if i == 0 or j == 0:
            dp[i][j] = 0
        elif string2[i - 1] == string1[j - 1]:
            dp[i][j] = 1 + dp[i - 1][j - 1]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

def recon(dp, string1, string2):
    string = ""
    i, j = len(dp) - 1, len(dp[0]) - 1
    while i != 0 and j != 0:
        if dp[i][j] > max(dp[i - 1][j], dp[i][j - 1]):
            string += string2[i - 1]
            i -= 1
            j -= 1
        else:
            if dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1

    return string

print(recon(dp, string1, string2)[::-1])

Submission status: Accepted

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

l=dp[S][T]
x,y=S,T
ans=[0]*l
while l>0:
    if s[x-1]==t[y-1]:
        ans[l-1]=s[x-1]
        l-=1
        x-=1
        y-=1
    else:
        if dp[x][y]==dp[x-1][y]:x-=1
        else:y-=1
print("".join(ans))

Submission status: Accepted

Solution code:
# メイン関数
def main():
    # 入力データ
    s = input()
    t = input()

    # dpテーブルの作成
    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] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

    # 部分列の復元
    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:
            i -= 1
            j -= 1
            ans = s[i] + ans

    # 解答の出力
    print(ans)
    return


# 実行
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

len=dp[S][T]
x,y=S-1,T-1
ans=[0]*len
while len>0:
    if s[x]==t[y]:
        ans[len-1]=s[x]
        x-=1
        y-=1
        len-=1
    else:
        if dp[x+1][y+1]==dp[x][y+1]: x-=1
        else: y-=1

print("".join(ans))

Submission status: Accepted

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

#import
#import math
#import numpy as np
#= int(input())
S = input()
T = input()

ls = len(S)
lt = len(T)

dp = [[0] * (lt + 1) for _ in range(ls + 1)]

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

print(ans)

Submission status: Accepted

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

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

    # dp[i][j] = the maximum length of common part of s[:i] and t[:j]
    dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
    for i in range(1, len_s + 1):
        for j in range(1, len_t + 1):
            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])

    i, j = len_s, len_t
    ans = ''
    while dp[i][j] > 0:
        while dp[i-1][j] == dp[i][j]:
            i -= 1
        while dp[i][j-1] == dp[i][j]:
            j -= 1

        ans += s[i-1]
        i -= 1
        j -= 1

    print(ans[::-1])

main()

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

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

Submission status: Accepted

Solution code:
s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0] * (tlen+1) for i in range(slen+1)]
for i in range(slen):
    for j in range(tlen):
        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])
stlen = dp[slen][tlen]
ans = [0]*stlen
i = slen
j = tlen
while stlen > 0:
    if s[i-1] == t[j-1]:
        ans[stlen-1] = s[i-1]
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1
    stlen = dp[i][j]
print(''.join(ans))

Submission status: Accepted

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

ssize = len(s)
tsize = len(t)

# dp[i][j]: sのi文字目まで、tのj文字目までのLongestCommonSubsequence
dp = [[0] * (tsize+1) for _ in range(ssize+1)]

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

i, j = ssize, tsize

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] + ans
        i -= 1
        j -= 1

print(ans)

Submission status: Accepted

Solution code:
s = input()
t = input()
n_s = len(s)
n_t = len(t)

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

for i in range(n_s+1):
    for j in range(n_t+1):
        if i == 0 or j == 0:
            continue
        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)

sna = ""
while n_s > 0 and n_t > 0:
    if dp[n_s][n_t] == dp[n_s-1][n_t]:
        n_s -= 1
    elif dp[n_s][n_t] == dp[n_s][n_t-1]:
        n_t -= 1
    else:
        sna += s[n_s-1]
        n_s -= 1
        n_t -= 1
ans = ""
for i in range(len(sna))[::-1]:
    ans += sna[i]
print(ans)

Submission status: Accepted

Solution code:
''' ===============================
    -- @uthor : Kaleab Asfaw
    -- Handle : kaleabasfaw2010
    -- Bio    : High-School Student
    ==============================='''

# Fast IO
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file): self._fd = file.fileno(); self.buffer = BytesIO(); self.writable = "x" in file.mode or "r" not in file.mode; self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b: break
            ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0; return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)); self.newlines = b.count(b"\n") + (not b); ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1; return self.buffer.readline()
    def flush(self):
        if self.writable: os.write(self._fd, self.buffer.getvalue()); self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file): self.buffer = FastIO(file); self.flush = self.buffer.flush; self.writable = self.buffer.writable; self.write = lambda s: self.buffer.write(s.encode("ascii")); self.read = lambda: self.buffer.read().decode("ascii"); self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout); input = lambda: sys.stdin.readline().rstrip("\r\n")
# Others
# from math import floor, ceil, gcd
# from decimal import Decimal as d
mod = 10**9+7
def lcm(x, y): return (x * y) / (gcd(x, y))
def fact(x, mod=mod):
	ans = 1
	for i in range(1, x+1): ans = (ans * i) % mod
	return ans
def arr2D(n, m, default=0):
	lst = []
	for i in range(n): temp = [default] * m; lst.append(temp)
	return lst
def sortDictV(x): return {k: v for k, v in sorted(x.items(), key = lambda item : item[1])}

def solve(st1, st2):
	n, m = len(st1), len(st2)
	dp = arr2D(n+1, m+1)

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

	lcs = ""
	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:
			lcs += st1[i-1]
			i -= 1
			j -= 1
	return lcs[::-1]
		
st1 = input()
st2 = input()
print(solve(st1, st2))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
s = np.array(list(input()))
t = np.array(list(input()))
dp = np.zeros((len(s)+1, len(t)+1), dtype=int)

equal = s[:, None] == t[None, :]

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

i = len(s)
j = len(t)
ans = []

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

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

Submission status: Accepted

Solution code:
from copy import copy

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

def main(s,t):
    dp = ["" for i in range(len(t)+1)]
    for i in range(len(s)):
        temp = [""]
        for j in range(len(t)):
            prev = dp[j+1]
            last = temp[-1]
            if len(prev)>len(last):
                temp.append(prev)
            elif len(prev)<len(last):
                temp.append(last)
            elif s[i]==t[j]:
                temp.append("".join([dp[j],s[i]]))
            else:
                temp.append(prev)
        dp = copy(temp)
        
    print(dp[len(t)])
                    
if __name__=="__main__":
    s,t = getval()
    main(s,t)

Submission status: Accepted

Solution code:
s = input()
t = input()
slen = len(s)
tlen = len(t)

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

length = dp[slen][tlen]

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

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

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

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

# 文字列作成
length = dp[len(s)][len(t)]
_debug(length)

i = len(s) - 1
j = len(t) - 1
ans = [""] * length
_debug(ans)
while length > 0:
    if s[i] == t[j]:
        ans[length-1] = s[i]
        i -= 1
        j -= 1
        length -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    else:
        i -= 1
print("".join(ans))

Submission status: Accepted

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

DP = [[0] * (lt + 1) for _ in range(ls + 1)]
Ans = []
for i, s in enumerate(S, 1):
    for j, t in enumerate(T, 1):
        if s == t:
            DP[i][j] = DP[i - 1][j - 1] + 1
        else:
            DP[i][j] = max(DP[i - 1][j], DP[i][j - 1])
cnts = ls
cntt = lt

while DP[cnts][cntt]:
    while DP[cnts][cntt] == DP[cnts][cntt - 1]:
        cntt -= 1
    while DP[cnts][cntt] == DP[cnts - 1][cntt]:
        cnts -= 1
    cnts -= 1
    cntt -= 1
    Ans.append(S[cnts])
print(''.join(Ans[::-1]))

Submission status: Accepted

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

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

#dp[i][j] sをi文字目、tをj文字目まで求めたときの最大の長さ

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

ansl = dp[sl][tl]
i = sl
j = tl
ans = [""]*ansl
while(ansl>0):
    if s[i-1] == t[j-1]:
        ans[ansl-1] = s[i-1]
        i -= 1
        j -= 1
        ansl -= 1
    elif dp[i][j]==dp[i-1][j]:
        i -= 1
    else:
        j -= 1

print("".join(ans))

Submission status: Accepted

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0 for j in range(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]:
      dp[i][j] = dp[i-1][j-1] + 1
    else:
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])
ans = ""
length = dp[ls][lt]
i = ls
j = lt
while length > 0:
  if s[ls-1] == t[lt-1]:
    ans = s[ls-1] + ans
    ls -= 1
    lt -= 1
    length -= 1
  elif dp[ls-1][lt] == length:
    ls -= 1
  else:
    lt -= 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_f?lang=ja

# get LCS length
def lcs_len(s1,s2):
    n1,n2 = len(s1),len(s2)
    dp = [ [0]*(n2+1) for _ in range(n1+1) ]
    for i in range(1,n1+1):
        for j in range(1,n2+1):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 
            if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]+1
    return dp[-1][-1]

# get LCS string
def lcs_str(s1,s2):
    n1,n2 = len(s1),len(s2)
    dp = [ [0]*(n2+1) for _ in range(n1+1) ]
    for i in range(1,n1+1):
        for j in range(1,n2+1):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 
            if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]+1
    ansr = []
    i,j = n1,n2
    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: 
            ansr.append(s1[i-1])
            i -= 1
            j -= 1
    ans = ansr[::-1]
    return ''.join(ans)


s1 = input()
s2 = input()
ans = lcs_str(s1,s2)
print(ans,flush=True)

Submission status: Accepted

Solution code:
S = input()
T = input()
m = len(S)
n = len(T)
dp = [[0]*(n+1) for _ 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] = 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])

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

Submission status: Accepted

Solution code:

# Returns length of LCS for X[0..m-1], Y[0..n-1] 
def lcs(X, Y, m, n): 
	L = [[0 for x in range(n+1)] for x in range(m+1)] 

	# Following steps build L[m+1][n+1] in bottom up fashion. Note 
	# that 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]) 

	# Following code is used to print LCS 
	index = L[m][n] 

	# Create a character array to store the lcs string 
	lcs = [""] * (index+1) 
	lcs[index] = "" 

	# Start from the right-most-bottom-most corner and 
	# one by one store characters in lcs[] 
	i = m 
	j = n 
	while i > 0 and j > 0: 

		# If current character in X[] and Y are same, then 
		# current character is part of LCS 
		if X[i-1] == Y[j-1]: 
			lcs[index-1] = X[i-1] 
			i-=1
			j-=1
			index-=1

		# If not same, then find the larger of two and 
		# go in the direction of larger value 
		elif L[i-1][j] > L[i][j-1]: 
			i-=1
		else: 
			j-=1

	print (''.join(lcs))

# Driver program 

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

Submission status: Accepted

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0 for _ in range(lt + 1)] for _ in range(ls + 1)]
ans = 0
for i in range(ls):
    for j in range(lt):
        if s[i] == t[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
            if dp[i][j] > ans:
                ans = dp[i][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            
l = dp[i][j]
ans = ""
while l > 0:
    if s[i] == t[j]:
        ans += s[i]
        i -= 1
        j -= 1
        l -= 1
    elif dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1
print(ans[::-1])

Submission status: Accepted

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

        i-=1
print(''.join(an))

Submission status: Accepted

Solution code:
s=input() 
t=input() 
dp=[[0 for j in range(len(t)+1)] for i in range(len(s)+1)]
res=''  
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[-1][-1] 
res=['']*(length+1)  
i=len(s) 
j=len(t) 
while i>0 and j>0:
	if s[i-1]==t[j-1]:
		res[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(res))

Submission status: Accepted

Solution code:
from itertools import combinations
s = input()
n = len(s)
t = input()
m = len(t)

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

i = n
j = m
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
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
print(ans)

Submission status: Accepted

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

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

dp = [[0 for a in range(3300)] for b in range(3300)]

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

        dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1])

rewsna = ""

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:
        rewsna += s[n-1]
        n -= 1
        m -= 1

print(rewsna[::-1])

Submission status: Accepted

Solution code:
s=input()
t=input()
lens=len(s)
lent=len(t)
dp=[[0 for _ in range(lent+1)] for _ in range(lens+1)] 
for i in range(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)
      #print(max(dp[i+1][j+1],dp[i][j]+1))
    dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1],dp[i+1][j])
    #print(dp)
#print(dp)
#len=dp[lens][lent]
#print(len)
i=lens
j=lent
#ans=["" for _ in range(len)]
ans=""
while i>0 and j>0:
  #print(i,j,ans)
  if dp[i][j]==dp[i-1][j]:
    i-=1
  elif dp[i][j]==dp[i][j-1]:
    j-=1
  else:
    #print(i,j,ans)
    ans+=s[i-1]
    i-=1
    j-=1
    #len-=1
    #print(ans)
print(ans[::-1])

Submission status: Accepted

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

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

for i in range(1,m+1) :
    for j in range(1,n+1):
        if t[i-1] == s[j-1] :
            ans[i][j]='match' 
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=dp[i-1][j-1]
            ans[i][j]='lu'
            if dp[i-1][j]>=dp[i][j] :
                dp[i][j]=dp[i-1][j]
                ans[i][j]='u' 
            
            if dp[i][j-1]>=dp[i][j] :
                dp[i][j]=dp[i][j-1]
                ans[i][j]='l' 
for i in range(m+1):
    ans[i][0]='u'
for j in range(n+1):
    ans[0][j]='l'


answer=[]
i=m ; j=n 
while (i>=0 and j>=0):
    if ans[i][j]=='match' :
        answer.append(s[j-1])
        i-=1
        j-=1
    elif ans[i][j]=='l' :
        j-=1
    elif ans[i][j]=='lu':
        i-=1
        j-=1
    else:
        i-=1


answer.reverse()
print(''.join(answer))

Submission status: Accepted

Solution code:
def main():
    s = input()
    t = input()
    dp = [["" for _ in range(3010)] for _ in range(3010)]
    for i in range(len(s)):
        for j in range(len(t)):
            dp[i + 1][j + 1] = dp[i][j + 1] if len(dp[i][j + 1]) >= len(dp[i + 1][j]) else dp[i + 1][j]
            if s[i] == t[j] and len(dp[i][j]) + 1 > len(dp[i + 1][j + 1]):
                dp[i + 1][j + 1] = dp[i][j] + s[i]
    print(dp[len(s)][len(t)])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

S=len(s)+1
T=len(t)+1

dp=[[0]*T for i in range(S)]

for i in range(1,S):
  for j in range(1,T):
    if s[i-1]==t[j-1]:
      dp[i][j] = max(dp[i][j],dp[i-1][j-1] + 1)
    dp[i][j] = max(dp[i][j],dp[i-1][j]) 
    dp[i][j] = max(dp[i][j],dp[i][j-1])
    
res=""
i=len(s)
j=len(t)
while i>0 and j>0:
  #(i-1,j)->(i,j)に更新した場合
  if dp[i][j] == dp[i-1][j]:
    i -= 1
  #(i,j-1)->(i,j)に更新した場合
  elif dp[i][j] == dp[i][j-1]:
    j -= 1
  #s[i]=t[j]であり、(i-1,j-1)->(i,j)に更新した場合
  else:
    res = s[i-1] + res
    i -= 1
    j -= 1
print(res)