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:
#!/usr/bin/env python
import os
import operator
import sys
from io import BytesIO, IOBase

def inar():
    return [int(k) for k in input().split()]
def main():
    s=input()
    t=input()
    dp=[]
    arrow=[]
    for i in range(len(t)+1):
        lis=[0 for k in range(len(s)+1)]
        lis1=["" for l in range(len(s)+1)]
        dp.append(lis)
        arrow.append(lis1)
    for i in range(1,len(t)+1):
        for j in range(1,len(s)+1):
            if t[i-1]==s[j-1]:
                dp[i][j]=dp[i-1][j-1]+1
                arrow[i][j]="C"
            else:
                if dp[i][j-1]>dp[i-1][j]:
                    dp[i][j]=dp[i][j-1]
                    arrow[i][j]="L"
                else:
                    dp[i][j]=dp[i-1][j]
                    arrow[i][j]="U"
    res=""
    i=len(t)
    j=len(s)
    # for i in range(len(t)+1):
    #     print(*arrow[i])
    while 1:
        if i==0 or j==0:
            break
        if arrow[i][j]=="C":
            res+=s[j-1]
            i-=1
            j-=1
        elif arrow[i][j]=="U":
            i-=1
        else:
            j-=1
    print(res[::-1])



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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

res=''

j=len(a)
i=len(b)
while j>0 and i>0:
 
    if dp[i][j]==dp[i-1][j]:
        i-=1
  
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    elif dp[i][j]==dp[i-1][j-1]+1:

        res+=a[j-1]
        i-=1
        j-=1
    
print(res[::-1])

Submission status: Accepted

Solution code:
def LCS(s1,s2):
    l1, l2 = len(s1), len(s2)
    if l1 == 0 or l2 == 0:
        return ''
    
    dp = [[0 for i in range(l2+1)] for j in range(l1+1)]

    for i in range(l1):
        for j in range(l2):
            if s1[i] == s2[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            dp[i+1][j+1] = max(max(dp[i+1][j+1],dp[i][j+1]),dp[i+1][j])
    
    lcs_str = ''
    i,j = l1,l2
    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_str += s[i-1]
            i -= 1
            j -= 1
    
    return lcs_str[::-1]

s = input()
t = input()
print(LCS(s,t))

Submission status: Accepted

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

# pad a character to the first because i want to count index from 1
s = "." + s; t = "." + t;

a = len(s)
b = len(t)

dp = [['']*(b) for _ in range(2)]
# dp[i][j] is the length of lcs of s[0]s[1]...s[i] and t[0]t[1]...t[j]

for i in range(1, a):
    for j in range(1, b):
        if s[i] == t[j]:
            if len(dp[i&1][j]) < len(dp[(i+1)&1][j-1]) + 1:
                dp[i&1][j] = dp[(i+1)&1][j-1] + s[i]
        else:
            for adja in [[i-1, j-1], [i-1, j], [i, j-1]]:
                if len(dp[i&1][j]) < len(dp[adja[0]&1][adja[1]]):
                    dp[i&1][j] = dp[adja[0]&1][adja[1]]

print(dp[(a+1)&1][b-1])

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] = dp[i][j] + 1
    else:
      dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
      
s = len(S)
t = len(T)
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]
    s -= 1
    t -= 1
    
print(ans[::-1])

Submission status: Accepted

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

S = readline().rstrip()
T = readline().rstrip()

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])
      
#for d in dp:
#  print(d)
x = len(S)
y = len(T)
ans = ""
while y > 0 and x > 0:
  if dp[x][y] == dp[x][y - 1] + 1 == dp[x - 1][y] + 1:
    ans += T[y - 1]
    y -= 1
    x -= 1
  else:
    if dp[x][y - 1] == dp[x][y]:
      y -= 1
    else:
      x -= 1
  
print(ans[::-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
l = 3010
def main():
    s = input().strip()
    t = input().strip()
    dp = [[0] * l for i in range(l)]
    rdp = [[0] * l for i in range(l)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i-1][j-1] + 1
                rdp[i][j] = (i-1, j-1)
            else:
                if dp[i-1][j] < dp[i][j-1]:
                    dp[i][j] = dp[i][j-1]
                    rdp[i][j] = (i, j-1)
                else:
                    dp[i][j] = dp[i-1][j]
                    rdp[i][j] = (i-1, j)

    # print(dp[len(s)-1][len(t)-1])
    ans = ''
    p, q = len(s)-1, len(t)-1
    while True:
        if p == -1 or q == -1:
            break
        nextp, nextq = rdp[p][q]
        if nextp != p and nextq != q:
            ans += s[p]
        p = nextp
        q = nextq

    print(''.join(reversed(ans)))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)

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

    # 復元パート 昔のコピペ
    res = ""
    while N > 0 and M > 0:
        if dp[N][M] == dp[N-1][M]:
            N -= 1
        elif dp[N][M] == dp[N][M-1]:
            M -= 1
        else:
            res = S[N-1] + res
            N -= 1
            M -= 1
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = input()
t = input()
dp = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]
for i in range(len(s) + 1):
    for j in range(len(t) + 1):
        if i < len(s):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j < len(t):
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])
        if i < len(s) and j < len(t) and s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
i, j = len(s), len(t)
now = dp[len(s)][len(t)]
ans = []
while now:
    if dp[i-1][j] == now:
        i -= 1
    elif dp[i][j-1] == now:
        j -= 1
    else:
        i -= 1
        j -= 1
        ans.append(s[i])
        now -= 1
print(''.join(reversed(ans)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:

S=input()
T=input()

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


for i in range(1,t+1):
  for j in range(1,s+1):
    if S[j-1]==T[i-1]:
      dp[i][j]=dp[i-1][j-1]+1
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
  
arr=[]
while(i>0 and j>0):
  if S[j-1]==T[i-1]:
    arr+=[j-1]
    j-=1
    i-=1
  else:
    if dp[i-1][j]>dp[i][j-1]:
      i-=1
    else:
      j-=1
arr.sort()
for i in arr:
  print(S[i],end="")

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):
    s = S[i-1]
    for j in range(1,M+1):
        t = T[j-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])
ans = []
while N and M:
    if dp[N][M] > max(dp[N-1][M],dp[N][M-1]):
        ans.append(S[N-1])
        N -= 1
        M -= 1
    elif dp[N][M] == dp[N-1][M]:
        N -= 1
    else:
        M -= 1

ans = ans[::-1]

ans = "".join(ans)
print(ans)

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

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

res = []

i = len(S)
j = len(T)

while i and j:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        res.append(S[i - 1])
        i -= 1
        j -= 1

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

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

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

res = []
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:
        res.append(S[x - 1])
        stack.append((x - 1, y - 1))

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
import re
"""
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)
"""

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)

def main():
    input = sys.stdin.readline
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

    S = input().strip()
    T = input().strip()
    lcs = solve(S, T)
    print(lcs)
    """
    s = [ord(c) - 97 for c in input()]
    t = [ord(c) - 97 for c in input()]
    dp = {}
    memo = {}
    for i in range(len(s)+1):
        for j in range(len(t)+1):
            if i == 0 or j == 0:
                dp[(i, j)] = 0
            else:
                if s[i - 1] == t[j - 1]:
                    dp[(i, j)] = dp[(i - 1, j - 1)] + 1
                    memo[(i, j)] = (i - 1, j - 1)
                else:
                    if dp[(i - 1, j)] < dp[(i, j - 1)]:
                        dp[(i, j)] = dp[(i, j - 1)]
                        memo[(i, j)] = (i, j - 1)
                    else:
                        dp[(i, j)] = dp[(i - 1, j)]
                        memo[(i, j)] = (i - 1, j)
   
    lcs = []
    while dp[i, j] > 0:
        i, j = memo[(i, j)]
        if s[i] == t[j]:
            lcs.insert(0, chr(s[i] + 97))

    print("".join(lcs))
    """


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def lcs(str1, str2):
    """文字列str1, str2の最長共通部分列(Longest Common Subsequence, LCS)を求める。
    計算量 O(|str1||str2|)
    """
    dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]
    for i in range(len(str1)):
        for j in range(len(str2)):
            if str1[i] == str2[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

    # 復元
    res = ''
    i, j = len(str1), len(str2)
    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 = str1[i - 1] + res
            i -= 1
            j -= 1

    return res


s = input()
t = input()
print(lcs(s, t))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f
from copy import *
from bisect import *	
from heapq import *
from math import *
from itertools import permutations 
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
def li():
	return [int(x) for x in input().split()]
def gi():	
	return [x for x in input().split()]
def fi():
	return int(input())
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())	
def gh():
	sys.stdout.flush()
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)
def bo(i):
	return ord(i)-ord('a')
		


tt=1



while tt>0:
	tt-=1
	s=si()
	t=si()
	n=len(s)
	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):
			#print(i,j,s[i-1],t[j-1])
			if i==1 and j==1:
					dp[i][j]=int(s[i-1]==t[j-1])
			elif i==1:
				
					dp[i][j]=max([dp[i][j],dp[i][j-1],int(s[i-1]==t[j-1])])
			elif j==1:
				dp[i][j]=max([dp[i][j],dp[i-1][j],int(s[i-1]==t[j-1])])
			else:
				dp[i][j]=max([dp[i][j],dp[i-1][j-1]+int(s[i-1]==t[j-1]),dp[i][j-1],\
					dp[i-1][j]])	
	i=n
	j=m
	ans=""
	tle=0
	#for ii in dp[:n+1]:
	#	print(*ii[:m+1])
	while i>0 or j>0:
		if dp[i][j]==0:
			break
		if i>0 and dp[i-1][j]==dp[i][j]:
			i-=1
		elif j>0 and dp[i][j-1]==dp[i][j]:
			j-=1		
		elif i>0 and j>0 and dp[i][j]-dp[i-1][j-1]==1:
			ans+=s[i-1]
			i-=1
			j-=1
		
		else:
			if i>0 and j>0:
				if dp[i-1][j]>dp[i][j-1]:
					i-=1
				else:
					j-=1	
				
			elif j>0:	
				j-=1
			else:
				i-=1	
		tle+=1
		#print(ans,i,j,tle)
		if tle>n+m:
			break
	if dp[i][j]>0:
		ans+=s[0]			
	print(ans[::-1])

Submission status: Accepted

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

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

    DP = [[0] * (len_t + 1) for _ in range(len_s + 1)]

    for i in range(len_s):
        for j in range(len_t):
            if s[i] == t[j]:
                DP[i + 1][j + 1] = DP[i][j] + 1
            else:
                DP[i + 1][j + 1] = max(DP[i + 1][j], DP[i][j + 1])

    ans = ""
    i = len_s
    j = len_t
    while DP[i][j]:
        if DP[i - 1][j] < DP[i][j] and DP[i][j - 1] < DP[i][j]:
            ans += s[i - 1]
            i -= 1
            j -= 1
        else:
            if DP[i - 1][j] ==  DP[i][j]:
                i -= 1
            if DP[i][j - 1] == DP[i][j]:
                j -= 1

    print(ans[::-1])


if __name__ == '__main__':
    main()

exit()

Submission status: Accepted

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

Submission status: Accepted

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

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

y = len(s)
x = len(t)

moji = ""

while(True):
  while(y > 0 and table[y-1][x] == table[y][x]):
    y -= 1
  
  while(x > 0 and table[y][x-1] == table[y][x]):
    x -= 1
  if(x > 0 and y > 0):
    moji = s[y-1] + moji
    x -= 1
    y -= 1
  else:
    break

print(moji)

Submission status: Accepted

Solution code:
# LCS
s = input()
t = input()
ls, lt = len(s), len(t)
dp = [[0 for i in range(ls + 1)] for j in range(lt + 1)]
prev = [[0 for i in range(ls + 1)] for j in range(lt + 1)]
for i in range(lt):
    for j in range(ls):
        dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
        if t[i] == s[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
# 復元
ans = []
x = lt
y = ls
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:
        x -= 1
        y -= 1
        ans.append(t[x])
ans = reversed(ans)
print("".join(ans))

Submission status: Accepted

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

from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x)


def solve(S, T):
    sizeS = len(S)
    sizeT = len(T)
    m = [[0] * (sizeT + 1) for _i in range(sizeS + 1)]
    for i in range(1, sizeS + 1):
        for j in range(1, sizeT + 1):
            m[i][j] = max(
                m[i - 1][j],
                m[i][j - 1],
                m[i - 1][j - 1] + 1 if S[i - 1] == T[j - 1] else 0
            )
    result = []
    i = sizeS
    j = sizeT
    while i > 0 and j > 0:
        if m[i][j] == m[i - 1][j]:
            i -= 1
        elif m[i][j] == m[i][j - 1]:
            j -= 1
        else:
            result.append(chr(S[i - 1]))
            i -= 1
            j -= 1
    print("".join(reversed(result)))


def main():
    S = input().strip()
    T = input().strip()
    solve(S, T)


def _test():
    """
    >>> solve("axyb", "abyxb")
    axb
    """
    global chr
    import doctest
    def chr(x): return x
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
### The code is worked in dp, with a 2D matrix technique.

s = input()
t = input()

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

q = []

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

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

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

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

def lcs(X,Y):
    m,n = len(X),len(Y)
    L = [[0]*(n+1) for i in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            if 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])
    size = L[m][n] 
    lcs = []
    i,j = m,n
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]: 
            lcs.append(X[i-1]) 
            i-=1
            j-=1
        elif L[i-1][j] > L[i][j-1]: 
            i-=1
        else: 
            j-=1
    return ''.join(lcs[::-1])

s = input().strip()
t = input().strip()
ans = lcs(s,t)
print(ans)

Submission status: Accepted

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

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

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

for i in range(m+1):
    for j in range(n+1):

        if i == 0 or j == 0:
            dp[i][j] = 0

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



final = dp[m][n]

lcs = [""] * (final + 1)
lcs[final] = ""

i = m
j = n

while i > 0 and j > 0:
    if s[i-1] == t[j-1]:
        lcs[final-1] = s[i-1]
        i -= 1
        j -= 1
        final -= 1

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


print("".join(lcs))

Submission status: Accepted

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

dp = [[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] = dp[i][j]+1
        else: #そうでないなら片方を削除
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
            
#復元
x = len(s)
y = len(t)
res = ''
while(dp[x][y]):
    if dp[x][y-1]==dp[x][y]: #行けるだけ左に
        y -= 1
    elif dp[x-1][y]==dp[x][y]: #行けるだけ上に
        x -= 1
    else:
        res = s[x-1] + res
        x -= 1
        y -= 1

print(res)

Submission status: Accepted

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

# DP
dp = [[0 for _ in range(lt + 1)] for j in range(ls + 1)]

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

Submission status: Accepted

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

dp = [[-1 for i in range(tlen + 1)] for j in range(slen + 1)]

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


ans = ""
i, j = 0, 0

while i < slen and j < tlen:
    if dp[i][j] == dp[i + 1][j]:
        i += 1
    elif dp[i][j] == dp[i][j + 1]:
        j += 1
    else:
        ans += s[i]
        i += 1
        j += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    s1, s2 = input(), input()
    n, m = len(s1), len(s2)

    dp, previous = [], []
    for i in range(n + 1):
        dp.append([0] * (m + 1))
        previous.append([0] * (m + 1))

    for row in range(1, n + 1):
        for column in range(1, m + 1):
            if s1[row - 1] == s2[column - 1]:
                dp[row][column] = 1 + dp[row - 1][column - 1]
                previous[row][column] = (row - 1, column - 1)
            else:
                dpUp = dp[row - 1][column]
                dpLeft = dp[row][column - 1]

                if dpUp > dpLeft:
                    dp[row][column] = dpUp
                    previous[row][column] = (row - 1, column)
                else:
                    dp[row][column] = dpLeft
                    previous[row][column] = (row, column - 1)

    lcs = ''
    curr = (n, m)

    while True:
        row, column = curr
        if previous[row][column] == 0: break

        if s1[row - 1] == s2[column - 1]:
            lcs = f'{s1[row - 1]}{lcs}'

        curr = previous[row][column]

    print(lcs)

main()

Submission status: Accepted

Solution code:
import sys
def main():
    s=list(sys.stdin.readline().strip())
    t=list(sys.stdin.readline().strip())
    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]=dp[i][j]+1
            dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j],dp[i][j+1])
    res=''
    i,j=S,T
    while i>0 and j>0:
        if dp[i][j]==dp[i-1][j]:i-=1
        elif dp[i][j]==dp[i][j-1]:j-=1
        else:
            res=s[i-1]+res
            i,j=i-1,j-1
    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)]

for i, ei in enumerate(s, 1):
    for j, ej in enumerate(t, 1):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1], (dp[i-1][j-1] + 1) * (ei == ej))

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

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

Submission status: Accepted

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

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

res = ""
i = n
j = m
while i > 0 and j > 0:
  if s[j-1] == t[i-1]:
    res = s[j-1] + res
    i -= 1
    j -= 1
  
  else:
    if dp[i-1][j] > dp[i][j-1]:
      i -= 1
    else:
      j -= 1

print(res)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


s = input()
t = input()

def sub(s,t):
    """共通部分文字列長
    """
    ls = len(s)
    lt = len(t)
    dp = [[0]*(lt+1) for _ in range(ls+1)]
    ###
    prev = [[None]*(lt+1) for _ in range(ls+1)]
    ###
    for i in range(1,ls+1):
        for j in range(1,lt+1):
            if dp[i][j-1]>dp[i-1][j]:
                v = dp[i][j-1]
                pp = (i,j-1)
            else:
                v = dp[i-1][j]
                pp = (i-1,j)
            if s[i-1]==t[j-1] and dp[i-1][j-1] + 1 > v:
                v = dp[i-1][j-1] + 1
                pp = (i-1,j-1)
            dp[i][j] = v
            ###
            prev[i][j] = pp
            ###
    return dp, prev

dp, prev = sub(s,t)
ans = []
i,j = len(s), len(t)
while prev[i][j] is not None:
    if prev[i][j]==(i-1, j-1):
        ans.append(s[i-1])
    i,j = prev[i][j]
print("".join(ans[::-1]))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



s = input()
t = input()

def sub(s,t):
    """共通部分文字列長
    """
    ls = len(s)
    lt = len(t)
    dp = [[0]*(lt+1) for _ in range(ls+1)]
    ###
    prev = [[None]*(lt+1) for _ in range(ls+1)]
    ###
    for i in range(1,ls+1):
        for j in range(1,lt+1):
            vals = [dp[i][j-1], dp[i-1][j]]
            if s[i-1]==t[j-1]:
                vals.append(dp[i-1][j-1] + 1)
            m = max(vals)
            dp[i][j] = m
            ###
            ind = vals.index(m)
            if ind==0:
                prev[i][j] = (i,j-1)
            elif ind==1:
                prev[i][j] = (i-1,j)
            else:
                prev[i][j] = (i-1,j-1)
            ###
    return dp, prev

dp, prev = sub(s,t)
ans = []
i,j = len(s), len(t)
while prev[i][j] is not None:
    if prev[i][j]==(i-1, j-1):
        ans.append(s[i-1])
    i,j = prev[i][j]
print("".join(ans[::-1]))

Submission status: Accepted

Solution code:
a = input()
b = input()
na = len(a)
nb = len(b)

dp = [[0]*(nb+1) for _ in range(na+1)]

for i in range(na):
    for j in range(nb):
        if a[i] == b[j]:
            dp[i+1][j+1] = dp[i][j]+1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
ans = []
num = dp[na][nb]
x = na
y = nb
while num:
    if dp[x][y] == dp[x-1][y]:
        x -= 1
    elif dp[x][y] == dp[x][y-1]:
        y -= 1
    else:
        ans.append(a[x-1])
        x -= 1
        y -= 1
        num -= 1

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