Problem:


Score : 100 points

Problem Statement

You are given strings s and t.
Find one longest string that is a subsequence of both s and t.

Notes

A subsequence of a string x is the string obtained by removing zero or more characters from x and concatenating the remaining characters without changing the order.

Constraints

s and t are strings consisting of lowercase English letters.

1 \leq |s|, |t| \leq 3000

Input

Input is given from Standard Input in the following format:

s
t

Output

Print one longest string that is a subsequence of both s and t.
If there are multiple such strings, any of them will be accepted.

Sample Input 1

axyb
abyxb

Sample Output 1

axb

The answer is axb or ayb; either will be accepted.

Sample Input 2

aa
xayaz

Sample Output 2

aa

Sample Input 3

a
z

Sample Output 3

The answer is  (an empty string).

Sample Input 4

abracadabra
avadakedavra

Sample Output 4

aaadara



Sample input:
axyb
abyxb


Sample output:
axb

Submission status: Accepted

Solution code:
s=[ord(ch)-97 for ch in input()]
t=[ord(ch)-97 for ch in input()]
 
# minimize
mnmz={ch for ch in s} & {ch for ch in t}
if len(mnmz)==0:
    print("")
    exit()
s=[ z for z in s if z in mnmz ]
t=[ z for z in t if z in mnmz ]
if len(s)>len(t): s, t = t, s
 
# init
dp=[[0]*len(s) for _ in range(len(t))]
 
#dp frame
 
for i in range(len(s)): 
    if s[i]==t[0]:
        for j in range(i, len(s)):
            dp[0][j]=1
        break
for i in range(len(t)): 
    if s[0]==t[i]:
        for j in range(i, len(t)):
            dp[j][0]=1
        break
#dp
for i in range(1,len(t)):
    for j in range(1, len(s)):
        if s[j]==t[i]:
            dp[i][j]=dp[i-1][j-1]+1
        else: dp[i][j]=(dp[i][j-1] if dp[i][j-1]>dp[i-1][j] else dp[i-1][j])
 
#recover string
res=[]
j=len(s)-1
i=len(t)-1
while i>0 and j>0:
    if s[j]==t[i] and dp[i][j]==dp[i-1][j-1]+1:
        res.append(s[j])
        i=i-1
        j=j-1
        continue
    if dp[i][j]==dp[i][j-1]:
        j=j-1
    else: i=i-1
# last letter (first acually)
if i==0 and dp[i][j]>0:
    res.append(t[0])
elif j==0 and dp[i][j]>0:
    res.append(s[0])
 
 
print("".join(chr(i+97) for i in reversed(res)))

#print("\n".join(" ".join(str(el) for el in lst) for lst in dp ))

Submission status: Accepted

Solution code:
s=[ord(ch)-97 for ch in input()]
t=[ord(ch)-97 for ch in input()]

# minimize
mnmz={ch for ch in s} & {ch for ch in t}
if len(mnmz)==0:
    print("")
    exit()
s=[ z for z in s if z in mnmz ]
t=[ z for z in t if z in mnmz ]
if len(s)>len(t): s, t = t, s

# init
dp=[[0]*len(s) for _ in range(len(t))]

#dp frame init
for i in range(len(s)): 
    if s[i]==t[0]:
        for j in range(i, len(s)):
            dp[0][j]=1
        break
for i in range(len(t)): 
    if s[0]==t[i]:
        for j in range(i, len(t)):
            dp[j][0]=1
        break
#dp
for i in range(1,len(t)):
    for j in range(1, len(s)):
        if s[j]==t[i]:
            dp[i][j]=dp[i-1][j-1]+1
        else: dp[i][j]=(dp[i][j-1] if dp[i][j-1]>dp[i-1][j] else dp[i-1][j])

#recover string
res=[]
j=len(s)-1
i=len(t)-1
while i>=0 and j>=0:
    if s[j]==t[i]: #and dp[i][j]==dp[i-1][j-1]+1:
        res.append(s[j])
        i=i-1
        j=j-1
        continue
    if i==0 and j==0: break
    if j>0 and dp[i][j]==dp[i][j-1]:
        j=j-1
    else: i=i-1
# last letter (first acually)


print("".join(chr(i+97) for i in reversed(res)))

Submission status: Accepted

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

i, j = len(s)-1, len(t)-1
ret = ''
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:
        ret += s[i]; i -= 1; j -= 1
print(ret[::-1])

Submission status: Accepted

Solution code:
"""
https://atcoder.jp/contests/dp/tasks/dp_f
"""
from collections import defaultdict
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] = 1 + dp[i][j]
        else:
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

# print(dp[ls][lt])
N = dp[ls][lt]
y = ls
x = lt
ans = []
while N:
    if dp[y][x] == dp[y - 1][x]:
        y -= 1
        continue
    if dp[y][x] == dp[y][x - 1]:
        x -= 1
        continue
    else:
        ans.append(s[y - 1])
        N -= 1
        x -= 1
        y -= 1

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

Submission status: Accepted

Solution code:
"""
https://atcoder.jp/contests/dp/tasks/dp_f
"""
from collections import defaultdict
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] = 1 + dp[i][j]
        else:
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

# print(dp[ls][lt])
N = dp[ls][lt]
y = ls
x = lt
ans = ''
while N:
    if dp[y][x] == dp[y - 1][x]:
        y -= 1
        continue
    if dp[y][x] == dp[y][x - 1]:
        x -= 1
        continue
    else:
        ans = s[y - 1] + ans
        N -= 1
        x -= 1
        y -= 1

print(ans)

Submission status: Accepted

Solution code:
"""
https://atcoder.jp/contests/dp/tasks/dp_f
"""
from collections import defaultdict
s = input()
t = input()

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

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

pre = defaultdict(lambda: defaultdict(tuple))

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

# print(dp[ls][lt])

ans = ''
y = ls
x = lt
while pre[y][x]:
    ny, nx = pre[y][x]
    ans = s[ny] + ans
    y = ny
    x = nx

print(ans)

Submission status: Accepted

Solution code:
S,T = input(),input()
x,y = len(S),len(T)

dp = [[0]*(y+1) for _ in range(x+1)]

for i,s in enumerate(S):
  for j,t in enumerate(T):
    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j], dp[i][j] + int(s==t))
    
a = ""
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
    a += S[x]

print(a[::-1])

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM : https://atcoder.jp/contests/dp/submissions/4011183

S,T = input(), input()
S,T = list(map(lambda x: ord(x)-97, S)), list(map(lambda x: ord(x)-97, T))

# print(S,T)

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

for i,s in enumerate(S):
    for j,t in enumerate(T):
        dp[i+1][j+1] = max(
                dp[i][j+1], 
                dp[i+1][j],
                dp[i][j] + (s==t)
                )
res = []

x,y = len(S), len(T)

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
        res.append(chr(S[x]+97))
print(''.join(reversed(res)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
参考：https://qiita.com/drken/items/03c7db44ccd27820ea0d
・最長共通部分列問題
・i側とj側の両方向に配るDP
・復元
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

s = input()
t = input()

dp = [[0] * (len(t)+1) for i 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])
        # 今回増やす文字が一致するなら、LCSが1文字増える
        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)

# 復元(DPテーブルを遡る)
i = len(s)
j = len(t)
ans = ''
while i > 0 and 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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
参考：https://qiita.com/drken/items/03c7db44ccd27820ea0d
・最長共通部分列問題
・i側とj側の両方向に配るDP
・復元
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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)):
        # 下から右に送る
        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])
        # 今回増やす文字が一致するなら、LCSが1文字増える
        if s[i] == t[j]:
            # 左上から右下に送る
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)

# 復元(DPテーブルを遡る)
i = len(s)
j = len(t)
ans = ''
while i > 0 and 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)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
s=raw_input()
t=raw_input()

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

s="@"+s
t="_"+t


dp=[ [ 0 for j in range(len_t+1) ] for i in range(len_s+1)   ]
S=""
l=0

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


def lcs(i,j):
	ans=""
	if dp[i][j]==0:
		return ans
	else:
		if s[i]==t[j]:
			ans+=lcs( i-1, j -1)+s[i]
		else:
			if dp[i-1][j]>=dp[i][j-1]:
				ans+=lcs( i-1, j )
			else:
				ans+=lcs( i, j-1)
	return ans

print lcs(len_s, len_t)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
s=raw_input()
t=raw_input()

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

s="@"+s
t="_"+t


dp=[ [ 0 for j in range(len_t+1) ] for i in range(len_s+1)   ]
S=""
l=0

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


ans=""
def lcs(i,j):
	global ans
	if dp[i][j]==0:
		return
	else:
		if s[i]==t[j]:
			lcs(i-1,j-1)
			ans+=s[i]
		else:
			if dp[i-1][j]>=dp[i][j-1]:
				lcs( i-1, j )
			else:
				lcs( i, j-1)

lcs(len_s, len_t)
print ans

Submission status: Accepted

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

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

# dp[len(s)][len(t)]
# dp表をつくる
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][j-1],dp[i-1][j])
#print(dp)

#復元する
rev = ""
i = len_s
j = len_t
while (i>=1 and j>=1):
  if dp[i][j] == dp[i][j-1]:
    j -=1
  elif dp[i][j] == dp[i-1][j]:
    i -=1
  else:
    rev = t[j-1] + rev
    i -=1
    j -=1

print(rev)

Submission status: Accepted

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

  LS = len(s)
  LT = len(t)
      
  DP = [[0 for i in range(LT + 1)] for j in range(LS + 1)]
  L = [[0 for i in range(LT)] for j in range(LS)]
  for i in range(LS):
    for j in range(LT):
      a = DP[i+1][j]
      b = DP[i][j+1]
      if max(a, b) == a:
        DP[i+1][j+1] = a
        L[i][j] = 1
      else:
        DP[i+1][j+1] = b
        L[i][j] = 2
        a = b
      if s[i] == t[j]:
        c = DP[i][j] + 1
        if max(a, c) == c:
          DP[i+1][j+1] = c
          L[i][j] = 3       
        
  Ans = ""
  j = LS - 1
  k = LT - 1
  x = DP[LS][LT]
  for i in range(x, 0, -1):
    while True:
      if L[j][k] == 3:
        Ans += t[k]
        j -= 1
        k -= 1
        break
      elif L[j][k] == 2:
        j -= 1
      else:
        k -= 1
  print(Ans[::-1])
main()

Submission status: Accepted

Solution code:
from sys import stdin, stdout

INF = float('inf')
s = stdin.readline().strip()
f = stdin.readline().strip()

n, m = len(s), len(f)
dp = [[0 for i in range(m + 5)] for j in range(n + 5)]


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

n -= 1
m -= 1
ans = ''

while n >= 0 and m >= 0:
    if s[n] == f[m]:
        ans += s[n]
        n -= 1
        m -= 1
    elif dp[n - 1][m] > dp[n][m - 1]:
        n -= 1
    else:
        m -= 1
        
stdout.write(ans[::-1])

Submission status: Accepted

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

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

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

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

ans = []
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(s[x])

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

Submission status: Accepted

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

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

for i,s in enumerate(S):
  for j,t in enumerate(T):
    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j], dp[i][j] + int(s==t))

res = []

x,y = len(S),len(T)

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
    res.append(S[x])

print(''.join(reversed(res)))

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)]
# dp[si][ti] = si文字目までとti文字目までのLCS長

for si in range(ls):
    for ti in range(lt):
        if s[si] == t[ti]:
            dp[si + 1][ti + 1] = max(dp[si + 1][ti + 1], dp[si][ti] + 1)

        dp[si + 1][ti + 1] = max(dp[si + 1][ti + 1], dp[si + 1][ti])
        dp[si + 1][ti + 1] = max(dp[si + 1][ti + 1], dp[si][ti + 1])

ans = ''
si = ls
ti = lt
while si > 0 and ti > 0:
    if dp[si][ti] == dp[si - 1][ti]:
        si -= 1
    elif dp[si][ti] == dp[si][ti - 1]:
        ti -= 1
    else:
        ans = s[si - 1] + ans
        si -= 1
        ti -= 1
print(ans)

Submission status: Accepted

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

DP = [[0 for i in range(len(s)+1)] for i in range(len(t)+1)]
ans = ''
for i in range(len(t)):
    for j in range(len(s)):
        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)
j = len(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:
        i -= 1
        j -= 1
        ans = ans + t[i]
ans = ans[::-1]
print(ans)

Submission status: Accepted

Solution code:
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]


s = input()
t = input()


# str * str -> int
def solve(s, t):
    dp = makelist(len(s)+1, len(t)+1) # 何文字目かで index (offset=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])
    
    res = ""
    x, y = len(t), len(s)

    while dp[y][x] > 0:
        now = dp[y][x]
        u, lu, l = dp[y-1][x], dp[y-1][x-1], dp[y][x-1]
        if lu == now:
            x, y = x-1, y-1
        else: # lu = now - 1
            if u == lu and l == lu:
                res += s[y-1]
                x, y = x-1, y-1
            else:
                if u >= l:
                    y -= 1
                else:
                    x -= 1
                    
    return res[::-1]


print(solve(s, t))

Submission status: Accepted

Solution code:
s = input()
t = input()
a = len(s) + 1
b = len(t) + 1

X = [[0] * b for _ in range(a)]
for i in range(1, a):
    for j in range(1, b):
        X[i][j] = max(X[i-1][j], X[i][j-1])
        if s[i-1] == t[j-1]:
            X[i][j] = max(X[i-1][j-1]+1, X[i][j])
        
# print(X)
ans = ""
i = a-1
j = b-1
while i > 0 and j > 0:
    if X[i][j] == X[i-1][j]:
        i -= 1
    elif X[i][j] == X[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1
        
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys

INF = float('inf')
MOD = 10 ** 9 + 7

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


s = [ord(n) for n in S()]
t = [ord(n) for n in S()]

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

# 最長共通部分列の長さ
# print(dp[-1][-1])

ans = ''
i = len(s)
for j in range(len(t) + 1)[::-1]:
    if dp[i][j] != dp[i][j - 1]:
        if i == 0 or j == 0: break
        while dp[i][j] == dp[i - 1][j]:
            i -= 1
        ans += chr(t[j - 1])
        i -= 1

print(ans[::-1])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    s = [ord(c) - 97 for c in S()]
    t = [ord(c) - 97 for c in S()]
    sl = len(s)
    tl = len(t)
    rr = [[0] * (tl) for _ in range(sl)]
    t0 = t[0]
    for i in range(sl):
        if s[i] == t0:
            for k in range(i,sl):
                rr[k][0] = 1
            break

    rr0 = rr[0]
    s0 = s[0]
    for j in range(tl):
        if s0 == t[j]:
            for k in range(j,tl):
                rr0[k] = 1
            break

    ta = [(i,t[i]) for i in range(1, tl)]
    for i in range(1, sl):
        rri = rr[i]
        rri1 = rr[i-1]
        si = s[i]
        for j, tj in ta:
            if si == tj:
                rri[j] = rri1[j-1] + 1
            else:
                rri[j] = rri1[j]
                if rri[j] < rri[j-1]:
                    rri[j] = rri[j-1]

    i = sl-1
    j = tl-1
    r = []
    while i >= 0 and j >= 0:
        if s[i] == t[j]:
            r.append(s[i] + 97)
            i -= 1
            j -= 1
            continue
        if rr[i][j] == 0:
            break
        if i > 0 and rr[i-1][j] == rr[i][j]:
            i -= 1
        else:
            j -= 1

    return ''.join(map(chr,r[::-1]))


print(main())

Submission status: Accepted

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

Submission status: Accepted

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)]
for i in range(LS-1, -1, -1):
    for j in range(LT-1, -1, -1):
        if S[i] == T[j]:
            dp[i][j] = max(dp[i+1][j+1] + 1, dp[i+1][j], dp[i][j+1])
        else:
            dp[i][j] = max(dp[i+1][j], dp[i][j+1])
i = j = 0
ans = []
while i < LS and j < LT:
    if S[i] == T[j]:
        if dp[i][j] == dp[i+1][j+1] + 1:
            ans.append(S[i])
            i += 1; j += 1
        elif dp[i][j] == dp[i+1][j]:
            i += 1
        else:
            j += 1
    else:
        if dp[i][j] == dp[i+1][j]:
            i += 1
        else:
            j += 1
print(*map(chr, ans), sep='')

Submission status: Accepted

Solution code:
def main():
    s = input().strip()
    t = input().strip()
    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
            if dp[i][j] < dp[i-1][j]:
                dp[i][j] = dp[i-1][j]
            if dp[i][j] < dp[i][j-1]:
                dp[i][j] = dp[i][j-1]
    ans = ""
    i = len(s)
    j = len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            i -= 1
            j -= 1
            ans = s[i] + ans
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

dp=[[0 for x in range(len(t)+1)] for x in range(len(s)+1)] 
for i in range(len(s)+1): 
    for j in range(len(t)+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]) 
ans=dp[len(s)][len(t)]
lcs=[""]*(ans+1) 
lcs[ans]=""
i=len(s)
j=len(t) 
while i>0 and j>0: 
    if s[i-1]==t[j-1]: 
        lcs[ans-1]=s[i-1] 
        i-=1
        j-=1
        ans-=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]* len(s) for i in range(len(t))]
dp[0][0] = 0

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


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

while True:
    if j == 0:
        if dp[0][i] == 1:
            ans += t[0]
        break
    if i == 0:
        if dp[j][0] == 1:
            ans += s[0]           
        break
        
    else:
        if dp[j][i] == dp[j-1][i]:
            j -= 1
        elif dp[j][i] == dp[j][i-1]:
            i -= 1
        else:
            ans += t[j]
            j -= 1
            i -= 1

print(ans[::-1])

#for i in range(len(t)):
#    print(dp[i])

Submission status: Accepted

Solution code:
def 解():
    sS = input().rstrip()
    sT = input().rstrip()
    iS = len(sS)
    iT = len(sT)

    dp = [[0]*(iT+1) for _ in range(iS+1)]
    for i in range(iS):
        for j in range(iT):
            if sS[i] == sT[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])
    iC = dp[iS][iT]
    aR = [""]*iC
    i = iS
    j = iT
    while 0 < i and 0 < j:
        if sS[i-1] == sT[j-1]:
            aR[dp[i][j]-1]=sS[i-1]
            i -= 1
            j -= 1
        else:
            if dp[i][j] == dp[i][j-1] :
                j -= 1
            elif dp[i][j] == dp[i-1][j] :
                i -= 1
            else:
                break

    print("".join(aR))
    exit()

    def findS(i,j):
        iC = dp[i][j]
        if iC == 0 or aR[iC-1] != "":
            return False
        if dp[i][j] == dp[i-1][j] + 1 == dp[i][j-1] +1 :
            t = dp[i][j]
            aR[t-1] = sS[i-1]
            findS(i-1,j-1)
        else:
            findS(i-1,j)
            findS(i,j-1)
    findS(i,j)
    print("".join(aR))
解()

Submission status: Accepted

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

#　dpで最大の長さを求める
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])
    # print(dp)
# print(dp[S][T])

# 後ろから復元
m,n = S,T
ans = ""
while m>0 and n>0:
    if dp[m][n]==dp[m-1][n]:
        m -= 1
    elif dp[m][n]==dp[m][n-1]:
        n -= 1
    else:
        m -= 1
        n -= 1
        ans += s[m]
        # print(ans)
print(ans[::-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
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][j+1],dp[i+1][j])
                                                                                                    
ans=""
def rec(i,j):
  if i==0 or j==0:
    return 
  global ans
  if s[i-1]==t[j-1]:
    ans+=s[i-1]
    rec(i-1,j-1)
  elif dp[i-1][j]>=dp[i][j-1]:
    rec(i-1,j)
  else:
    rec(i,j-1)
rec(ls,lt)
print(ans[::-1])

Submission status: Accepted

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

# dp[i][j] := Sのi文字目, Tのj文字目まで見た場合のLCS
dp = [[0] * (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] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

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

print(ans[::-1])

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

ans = ""

i, j = len(s), len(t)

while i > 0 and j > 0:
	#if dp[i][j] == dp[i-1][j-1] + 1:
	if s[i-1] == t[j-1]:
		ans += s[i-1]
		i, j = i-1, j-1
	elif dp[i][j-1] >= dp[i-1][j]:
		j -= 1
	else:
		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 i in range(a+1)]
for j in range(1,a+1):
    for i in range(1,b+1):
        if s[j-1]==t[i-1]:
            dp[j][i]=dp[j-1][i-1]+1
        else:
            dp[j][i]=max(dp[j-1][i],dp[j][i-1])


N=dp[a][b]
y=a
x=b
#L=[]
H=[]
while N>0:
    if dp[y][x-1]-dp[y][x]==0:
        x-=1
        continue
    if dp[y-1][x]-dp[y][x]==0:
        y-=1
        continue
    #L.append((t[x-1],x-1))
    H.append(t[x-1])
    N-=1
    y-=1
    x-=1
print(''.join(H[::-1]))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def print_lcs (a, b, lcs, i, j, cur):
    if i==0 or j==0:
        return cur
    
    elif a[i] == b[j]:
        ans = print_lcs(a,b,lcs,i-1,j-1,cur+a[i])
        return ans
    
    else:
        if lcs[i-1][j] >= lcs[i][j-1]:
            return print_lcs(a,b,lcs,i-1,j,cur)
        else:
            return print_lcs(a,b,lcs,i,j-1,cur)
        


s = " " + ns()
t = " " + ns()

lens = len(s)
lent = len(t)

lcs = [[0]*lent for _ in range(lens)]
ans = ""
for i in range(1,lens):
    for j in range(1,lent):
        if s[i] == t[j]:
            lcs[i][j] = lcs[i-1][j-1] + 1

            
        else:
            if lcs[i-1][j] > lcs[i][j-1]:
                lcs[i][j] = lcs[i-1][j]
            else:
                lcs[i][j] = lcs[i][j-1]
                
print(print_lcs(s,t,lcs,lens-1,lent-1,"")[::-1])

Submission status: Accepted

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

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

ans = ''
def rec(i,j):
    if i==0 or j==0: return
    if S[i-1] == T[j-1]:
        global ans
        ans += S[i-1]
        rec(i-1,j-1)
    elif dp[i-1][j] >= dp[i][j-1]:
        rec(i-1,j)
    else:
        rec(i,j-1)

rec(N,M)
print(ans[::-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
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):
        indicator = 1 if S[i - 1] == T[j - 1] else 0
        dp[i][j] = max(dp[i - 1][j - 1] + indicator, dp[i - 1][j], dp[i][j - 1])

ans = ''


def print_lcs(s, t, dp_table, i, j):
    global ans
    if i == 0 or j == 0:
        return
    if S[i - 1] == T[j - 1]:
        print_lcs(s, t, dp, i - 1, j - 1)
        ans += S[i - 1]
    else:
        if dp[i - 1][j] >= dp[i][j - 1]:
            print_lcs(S, T, dp, i - 1, j)
        else:
            print_lcs(S, T, dp, i, j - 1)


print_lcs(S, T, dp, len(S), len(T))
print(ans)