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:
from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce


def input():
    return sys.stdin.readline().strip()


def iinput():
    return int(input())


def tinput():
    return input().split()


def rinput():
    return map(int, tinput())


def rlinput():
    return list(rinput())


mod = int(1e9)+7


def factors(n):
    return set(reduce(list.__add__,
                      ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))


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

if __name__ == "__main__":
    a = input()
    b = input()
    n, m = len(a), len(b)
    lcs = [[0 for i in range(n+1)] for j in range(m+1)]


    for i in range(1,m+1):
        for j in range(1,n+1):
            if b[i-1] == a[j-1]:
                lcs[i][j] = 1 + lcs[i-1][j-1]
            else:
                lcs[i][j] = max(lcs[i][j-1],lcs[i-1][j])
    
    s=""
    i=m
    j=n
    # print(lcs)
    while i>0 and j>0:
        if b[i-1] == a[j-1]:
            s+=b[i-1]
            i-=1
            j-=1
        elif lcs[i-1][j] > lcs[i][j-1]:
            i-=1
        else:
            j-=1

    print(s[::-1])

Submission status: Accepted

Solution code:
s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0 for i in range(m+1)] for j in range(n+1)]
lcs = [[(0,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 dp[i-1][j]>=dp[i][j-1]:
      dp[i][j] = dp[i-1][j]
      lcs[i][j] = (i-1,j)
    else:
      dp[i][j] = dp[i][j-1]
      lcs[i][j] = (i,j-1)
    if s[i-1] == t[j-1] and dp[i-1][j-1]+1>=dp[i][j]:
      dp[i][j] = dp[i-1][j-1]+1
      lcs[i][j] = (i,j)
ans = []
x = dp[n][m]
a = n
b = m
while x:
  if dp[a][b] == dp[a-1][b-1]+1 and dp[a][b] > max(dp[a-1][b],dp[a][b-1]):
    ans.append(s[lcs[a][b][0]-1])
    a -= 1
    b -= 1
    x -= 1
  elif dp[a][b] == dp[a-1][b]:
    a -= 1
  else:
    b -= 1
ans = ans[::-1]
print(*ans,sep="")

Submission status: Accepted

Solution code:
from copy import deepcopy
s = ['_']
s.extend(list(input()))
t = ['.']
t.extend(list(input()))
N = len(s)
M = len(t)
DP = [[0]*(M+1) for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+1):
        if s[i-1] == t[j-1]:
            DP[i][j] = DP[i-1][j-1]+1
        else:
            DP[i][j] = max(DP[i-1][j],DP[i][j-1])

i = N
j = M
ans = []
while i != 0 and j != 0:
    if DP[i-1][j] < DP[i][j] and DP[i][j-1] < DP[i][j]:
        ans.append(s[i-1])
        i -= 1
        j -= 1
    elif DP[i-1][j] == DP[i][j]:
        i -= 1
    elif DP[i][j-1] == DP[i][j]:
        j -= 1

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0] * (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] = 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])

#import numpy as np
#print(np.array(dp))

#from collections import deque
#ans = deque()

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

Submission status: Accepted

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

dp = [[0]*(3001) for j in range(3001)]

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

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

res = ""
s_len = len(s)
t_len = len(t)
while s_len > 0 and t_len > 0:
    if dp[s_len][t_len] == dp[s_len-1][t_len]:
        s_len -= 1
    elif dp[s_len][t_len] == dp[s_len][t_len-1]:
        t_len -= 1
    else:
        res = s[s_len-1] + res
        s_len -= 1
        t_len -= 1
print(res)

Submission status: Accepted

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

"""
dp[s][t]: Sのs文字目までとTのt文字目までの解
"""

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

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

result = ""
s = len(S)
t = len(T)
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
    elif dp[s][t] == dp[s-1][t-1] + 1:
        result = S[s-1] + result
        s -= 1
        t -= 1
print(result)

Submission status: Accepted

Solution code:
s=input()
t=input()
ls=len(s)
lt=len(t)
dp=[[0 for i in range(ls)] for i in range(lt)]
a=0
for i in range(ls):
    if t[0]==s[i]:
        a=1
    dp[0][i]=a
a=0
for i in range(lt):
    if s[0]==t[i]:
        a=1
    dp[i][0]=a
for i in range(1,lt):
    for j in range(1,ls):
        if s[j]==t[i]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
ans=[]
x=ls-1
y=lt-1
while x>0 or y>0:
    if x==0:
        y-=1
        if dp[y][0]!=dp[y+1][0]:
            ans.append(t[y+1])
    elif y==0:
        x-=1
        if dp[0][x]!=dp[0][x+1]:
            ans.append(s[x+1])
    elif dp[y][x]==dp[y-1][x]:
        y-=1
    elif dp[y][x]==dp[y][x-1]:
        x-=1
    else:
        x-=1
        y-=1
        ans.append(s[x+1])
if dp[y][x]==1:
    ans.append(s[0])
print(''.join(ans[::-1]))

Submission status: Accepted

Solution code:
s = input()
t = input()
dp = [[0]*(len(t)+1) for i in range(len(s)+1)]
#dp[i+1][j+1]sのi文字目までとtのj文字目までを比較したときのLCS
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)-1
j = len(t)-1
ans = ''
while j>= 0 and i >= 0:
    if dp[i][j+1] == dp[i+1][j+1]:i-= 1
    elif dp[i+1][j] == dp[i+1][j+1] :j-= 1
    else:
        ans = s[i] + ans
        i -= 1
        j -= 1
        
print(ans)

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)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(3000*3000)

A = input()
B = input()

# dp = [[None] * (len(B) + 1) for _ in range(len(A) + 1)]
# def dfs(a=0, b=0):
#     if dp[a][b] is not None:
#         return dp[a][b]
#
#     if a >= len(A) or b >= len(B):
#         dp[a][b] = 0
#         return 0
#
#     match = A[a] == B[b]
#     if match:
#         r = dfs(a + 1, b + 1) + 1
#     else:
#         r = max(dfs(a + 1, b), dfs(a, b + 1))
#     dp[a][b] = r
#     return r
# dfs()
# print(dfs())

dp = [[None] * (len(B) + 1) for _ in range(len(A) + 1)]
for a in reversed(range(len(A) + 1)):
    for b in reversed(range(len(B) + 1)):
        if a >= len(A) or b >= len(B):
            dp[a][b] = 0
            continue

        match = A[a] == B[b]
        if match:
            r = dp[a + 1][b + 1] + 1
        else:
            r = max(dp[a + 1][b], dp[a][b + 1])
        dp[a][b] = r

# print("---")
# for v in dp:
#     print(*map(lambda x: x if x is not None else "*", v))

def or_inf(v):
    return float('inf') if v is None else v

def reconst(a=0, b=0):
    if a >= len(A) or b >= len(B):
        return ''

    match = A[a] == B[b]
    if match:
        return reconst(a + 1, b + 1) + A[a]
    else:
        if or_inf(dp[a + 1][b]) >= or_inf(dp[a][b + 1]):
            return reconst(a + 1, b)
        else:
            return reconst(a, b + 1)
print(reconst()[::-1])

Submission status: Accepted

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

        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j],dp[i][j+1])
#print(dp)

#部分配列を復元する

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

Submission status: Accepted

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

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

# dp[n+1][m+1]

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

i = n; j = m

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

print(res)

Submission status: Accepted

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

n = len(s); m = len(t)
# dp [s+1][t+1]

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] = 1 + dp[i-1][j-1]
    else:
      dp[i][j] = max(dp[i-1][j],dp[i][j-1])
      
res = ""
i=n; j = m

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

Submission status: Accepted

Solution code:
def main():
    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):
            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=len(s)
    j=len(t)
    result=[]
    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:
            result.append(s[i-1])
            i-=1
            j-=1
    s="".join(result)
    s=s[::-1]
    print(s)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def LCS(s,t,restore=False):
    dp = [[0 for j in range(len(t)+1)] for i in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j]+1
            else:
                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])
    if restore:
        lcs = []
        stack = [(len(s),len(t))]
        while stack:
            x,y = stack.pop()
            if dp[x][y] == 0:
                break
            if x-1 >= 0 and dp[x][y] == dp[x-1][y]:
                stack.append((x-1,y))
            elif y-1 >= 0 and dp[x][y] == dp[x][y-1]:
                stack.append((x,y-1))
            else:
                lcs.append(s[x-1])
                stack.append((x-1,y-1))
        lcs = ''.join(lcs)[::-1]
        return dp[-1][-1],lcs
    return dp[-1][-1]
  
S = input()
T = input()

print(LCS(S,T,True)[1])

Submission status: Accepted

Solution code:
s = input() + "!"
t = input() + "@"
len_s = len(s)
len_t = len(t)

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

# dp[i][j] := sをi+1番目,tをj+1番目まで見たときの最長部分列
# 最後の文字を使うか使わないか
ans = ''
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])

j= len_t - 1
for i in range(len_s)[::-1]:
    while(dp[i][j - 1] == dp[i][j] and j >= 1):
        j -= 1
    if dp[i - 1][j] == dp[i][j]:
        continue
    ans += s[i -1]
print(ans[::-1])

Submission status: Accepted

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

A = len(S)
B = len(T)

dp = [[0] * (B+1) for _ in range(A+1)]
    
for i in range(1, A+1):
    for j in range(1, B+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])

lcs_len = dp[A][B]
i = A
j = B
ans = ""
while lcs_len > 0:
    if S[i-1] == T[j-1]:
        ans = S[i-1] + ans
        i -= 1
        j -= 1
        lcs_len -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        i -= 1
        
print(ans)

Submission status: Accepted

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

x = input().rstrip()
y = input().rstrip()

lx = len(x)
ly = len(y)
c1 = [[0 for _ in range(lx+1)] for _ in range(ly+1)]
for i in range(1,ly+1):
    e1 = y[i-1]
    for j in range(1,lx+1):
        if (e1 == x[j-1]):
            c1[i][j] = c1[i-1][j-1] + 1
        else:
            c1[i][j] = max(c1[i-1][j],c1[i][j-1])
i = ly
j = lx
s = ''
m = c1[i][j]
di = -1
dj = 0
while c1[i][j] > 0:
    if c1[i][j] > c1[i-1][j] and c1[i][j] > c1[i][j-1] and c1[i][j] > c1[i-1][j-1]:
        s = x[j-1] + s
        m = m - 1
        i = i - 1
        j = j - 1
    else:
        ni = i + di
        nj = j + dj
        if c1[ni][nj] == m:
            i = ni
            j = nj
        else:
            di, dj = dj, di

print (s)

Submission status: Accepted

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

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

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

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

i = ls
j = lt
ans = ""
while i>=1 and j>=1:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
        continue
    if dp[i][j] == dp[i-1][j]:
        i -= 1
        continue
    ans = s[i-1] + ans
    i -= 1
    j -= 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

s = input()
t = input()

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

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

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

Submission status: Accepted

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

table = [[0] * (lt+1) for i in range(ls+1)]
for ss in range(ls):
    for st in range(lt):
        table[ss+1][st+1] = table[ss][st] + 1 if s[ss] == t[st] else max(table[ss+1][st], table[ss][st+1] )

ans = ""
ss, st = ls, lt
while ss * st != 0:
    if table[ss][st] == table[ss-1][st]:
        ss -= 1
    elif table[ss][st] == table[ss][st-1]:
        st -= 1

    else:
        ss -= 1
        st -= 1
        ans = s[ss] + ans

print(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+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])
#print(*dp,sep='\n')
#復元していく
ans_str=''
i=len(s)
j=len(t)
while i>0 and j>0:
    #一致しているのは(i,j)→(i+1,j+1)の時だけ
    if dp[i][j]==dp[i-1][j]:
        i=i-1
    elif dp[i][j]==dp[i][j-1]:
        j=j-1
    else:
        ans_str=s[i-1]+ans_str
        i=i-1
        j=j-1
print(ans_str)

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

# DPを逆に辿って復元する
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:
s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0] * (ls+1) for _ in range(lt+1)]

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

ret = []
while ls > 0 and lt > 0:
    # dpテーブルの番号が一致しているということは、今評価対象の文字は最長共通部分列に含まれないということになる
    # そのため評価対象の文字を変更して次のループに入る
    # dpテーブルを右下から左上になめるように見ていくのは、評価対象以降の文字列の影響を除くため
    if dp[lt][ls] == dp[lt][ls-1]:
        ls -= 1
    elif dp[lt][ls] == dp[lt-1][ls]:
        lt -= 1
    else:
        ret.append(s[ls-1])
        ls -= 1
        lt -= 1

ret.reverse()
print("".join(ret))

Submission status: Accepted

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

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

ret = []
while ls > 0 and lt > 0:
    if dp[lt][ls] == dp[lt][ls-1]:
        ls -= 1
    elif dp[lt][ls] == dp[lt-1][ls]:
        lt -= 1
    else:
        ret.append(s[ls-1])
        ls -= 1
        lt -= 1

ret.reverse()
print("".join(ret))

Submission status: Accepted

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

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

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

# reconstruction
i, j = T, S
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[j-1] + ans
        i -= 1
        j -= 1

print(ans)

Submission status: Accepted

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


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] = dp[i-1][j-1] + 1
    else:
      dp[i][j] = max(dp[i][j-1], dp[i-1][j])
ans = []
s = (len(S)-1, len(T)-1)
while True:
  x, y = s
  if x < 0 or y < 0:
    break
  if S[x] == T[y]:
    ans.append(S[x])
    s = (x-1, y-1)
  else:
    if dp[x-1][y] > dp[x][y-1]:
      s = (x-1, y)
    else:
      s = (x, y-1)

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

Submission status: Accepted

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

dp = [ [ 0 for i in range(3010)] for j in range(3010) ]

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)
        else:
            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)-1
j = len(t)-1
ans = ""

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

print(ans)

Submission status: Accepted

Solution code:
def main2():
    #1:初期化
    s = input()
    t = input()
    v = [0] * (len(t) + 1)
    dp = [v]
    #print(v)
    #print(dp)

    #2:初期値(いらない)

    #3:dp実行部(貰うDP)
    for str1 in s:
        v = v.copy()
        dp.append(v)
        #print("in",*dp,sep="\n")
        ll, ul = 0, 0
        for j, str2 in enumerate(t, 1):
            uu = v[j]
            if str1 == str2:
                v[j] = ll = ul + 1
            elif ll > uu:
                v[j] = ll
            ul = uu
        #print(ll,ul,uu,"out",*dp,sep="\n")
            
    # #4:出力
    #print(*dp,sep="\n")
    res = ""
    s_len = len(s)
    t_len = len(t)
    while s_len > 0 and t_len > 0:
        if dp[s_len][t_len] == dp[s_len-1][t_len]:
            s_len -= 1
        elif dp[s_len][t_len] == dp[s_len][t_len-1]:
            t_len -= 1
        else:
            res = s[s_len-1] + res
            s_len -= 1
            t_len -= 1
    print(res)
        
if __name__ == '__main__':
    main2()

Submission status: Accepted

Solution code:
"""memo
    いつものように，numpyを使いたくなかったので他人のコードを参考にした．
    enumerateは「https://note.nkmk.me/python-enumerate-start/」を参考．
"""

def main2():
    #1:初期化
    s = input()
    t = input()
    v = [0] * (len(t) + 1)
    dp = [v]
    #print(v)
    #print(dp)

    #2:初期値(いらない)

    #3:dp実行部(貰うDP)
    for str1 in s:
        v = v.copy()
        #print(i, str1, u, v)
        dp.append(v)
        #print("in",*dp,sep="\n")
        ll, ul = 0, 0
        for j, str2 in enumerate(t, 1):
            uu = v[j]
            if str1 == str2:
                v[j] = ll = ul + 1
            else:
                if ll > uu:
                    v[j] = ll
                else:
                    ll = uu
            ul = uu
        #print("out",*dp,sep="\n")
            
    # #4:出力
    #print(*dp,sep="\n")
    res = ""
    s_len = len(s)
    t_len = len(t)
    while s_len > 0 and t_len > 0:
        if dp[s_len][t_len] == dp[s_len-1][t_len]:
            s_len -= 1
        elif dp[s_len][t_len] == dp[s_len][t_len-1]:
            t_len -= 1
        else:
            res = s[s_len-1] + res
            s_len -= 1
            t_len -= 1
    print(res)

if __name__ == '__main__':
    main2()

Submission status: Accepted

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

for i in range(n):
    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])

lcs_str = ''
i, j = n, m
while i >= 1 and j >= 1:
    if s[i - 1] == t[j - 1]:
        lcs_str += s[i - 1]
        i -= 1
        j -= 1
    else:
        if dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

print(lcs_str[::-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

s = input(); t = input()
n = len(s); m = len(t)
dp=[[0] * (m+1) for i in range(n+1)]
repair = [[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
      repair[i+1][j+1] = (i,j)
    else:
      dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
      repair[i+1][j+1] = (i,j+1) if dp[i][j+1] >= dp[i+1][j] else (i+1,j)


M = dp[n][m]
ans = []
i = n; j = m
while i != 0 and j != 0:
  # print(i,j,repair[i][j])
  ni,nj = repair[i][j]
  if dp[ni][nj] < dp[i][j]:
    ans.append(s[ni])
  i,j = ni,nj
ans.reverse()
print(*ans, sep = "")

Submission status: Accepted

Solution code:
import sys

def solve(s: str, t: str):
    ls=len(s)
    lt=len(t)
    dp=[[0]*(lt+1) for _ in range(ls+1)] # dp[0:ls+1][0:lt+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
            if dp[i+1][j]>dp[i+1][j+1]: dp[i+1][j+1]=dp[i+1][j]
            if dp[i][j+1]>dp[i+1][j+1]: dp[i+1][j+1]=dp[i][j+1]

    ans=""
    while ls>0 and lt>0:
        if dp[ls][lt]==dp[ls-1][lt]:
            ls-=1
        elif dp[ls][lt]==dp[ls][lt-1]:
            lt-=1
        else:
            ans=s[ls-1]+ans
            ls-=1
            lt-=1

    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s=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):
        #print(i-1, j-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])
#print(dp)
str = ''

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

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



        
def main(): #startline--------------------------------------------
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)
    dp = [[0]*(lt+1) for i 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+1][j],dp[i][j+1])


    ans = ""
    i = ls
    j = lt
    while dp[i][j] > 0:
        if dp[i-1][j] == dp[i][j]:
            i -= 1
        elif dp[i][j-1] == dp[i][j]:
            j -= 1
        else:
            ans = s[i-1]+ans
            i -= 1
            j -= 1

    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
# dpに文字列を格納 (TLE)
def resolve():
    s = input()
    t = input()

    dp = [[""] * (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] + s[i]
            else:
                if len(dp[i][j+1]) >= len(dp[i+1][j]):
                    dp[i+1][j+1] = dp[i][j+1]
                else:
                    dp[i+1][j+1] = dp[i+1][j]

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

def resolve():
    s = input()
    t = input()

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

    # 後ろから探索
    # s[i-1]が、LCSに含まれるかどうか判定
    # dp[i][j]とdp[i-1][j]またはdp[i][j-1]が一致(変化なし)の場合、s[i-1]はLCSに含まれない
    res = ""
    i = len(dp) - 1
    j = len(dp[0]) - 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:
            res = s[i-1] + res
            i -= 1
            j -= 1

    print(res)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

#sの文字数行*tの文字数列のDP
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]:
        # sとtの見た文字が一致
        # →sとtの双方の1個前までの共通最大連続数に+1追加
            dp[i][j]=dp[i-1][j-1]+1
        else:
        # 一致しないとき
        # sの1個前までか、tの1個前の共通最大連続数の
        # 大きいほうを採用
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])

# 復元はs,tとも後ろから見ていく
ans = ''
i=ls
j=lt
while i != 0 and j != 0:
    if dp[i][j] == dp[i-1][j]:
        # DP上でsの一個前から更新されてない
        # 即ちs[i-1]は共通列に入ってない
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        # 上と同じ論法でtの場合
        j -= 1
    else:
        # 今見ているs[i-1]とt[j-1]が共通になっているとき
        # 答えに採用（s[i-1]は頭につける）
        ans = s[i-1] + ans 
        i -= 1
        j -= 1
        
print(ans)

Submission status: Accepted

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