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:
import sys
sys.setrecursionlimit(3003)
def main():
    s = " "+input()
    N = len(s)-1

    t = " "+input()
    M = len(t)-1
    if N < M:
        N, M = M, N
        s, t = t, s
    # dp[i][j] := sのi文字目, tのj文字目までを使ったLCSの長さ
    dp = [[-1]*(M+1) for i in range(N+1)]
    dp[0] = [0]*(N+1)
    for i in range(N+1):
        dp[i][0] = 0
    for i in range(1, N+1):
        for j in range(1, M+1):
            
            if s[i] == t[j]:
                dp[i][j] = dp[i-1][j-1]+1
            elif s[i] != t[j]:
                if dp[i-1][j] > dp[i][j-1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1]
    print(get(s, t, N, M, dp))

def get(s, t, i, j, dp):
    if i == 0 or j == 0:
        return ""

    if s[i]==t[j]:
        return get(s, t, i-1, j-1, dp) + s[i]
    elif s[i] != t[j]:
        if dp[i-1][j] > dp[i][j-1]:
            return get(s, t, i-1, j, dp)
        else:
            return get(s, t, i, j-1, dp)


if __name__ == "__main__":
    main()

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,t=input(),input()
a,b=len(s),len(t)
DP=[[0]*(b+1) for _ in range(a+1)]
for i in range(a):
    for j in range(b):
        if s[i]==t[j]:
            DP[i+1][j+1]=DP[i][j]+1
        else:
            DP[i+1][j+1]=max(DP[i+1][j],DP[i][j+1])
ans=''
while a and b:
    if DP[a][b]==DP[a-1][b]:
        a-=1
    elif DP[a][b]==DP[a][b-1]:
        b-=1
    else:
        ans=s[a-1]+ans
        a-=1
        b-=1
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    """
    N個の足場があります。足場には1,2,…,Nと番号が振られています。 
    各i (1≤i≤N) について、足場 i の高さは hi です。
    最初、足場 1 にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 N まで辿り着こうとしています。
    足場 i にいるとき、足場 i+1 または i+2 へジャンプする。
    このとき、ジャンプ先の足場を j とすると、コスト |hi−hj| を支払う。
    カエルが足場 N に辿り着くまでに支払うコストの総和の最小値を求めてください。

    制約
        入力はすべて整数である。
    2≤N≤10**5
    1≤hi≤10**4
    """
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]))
    print(dp[n-1])
    return

#B
def B():
    n, K = LI()
    h = LI()
    dp = [float("INF") for i in range(n + K + 1)]
    dp[0] = 0
    for i in range(n):
        for k in range(1, K + 1):
            if i + k >= n:
                break
            dp[i + k] = min(dp[i + k], dp[i] + abs(h[i] - h[i + k]))
    print(dp[n-1])
    return

#C
def C():
    n = II()
    abc = LIR(n)
    dp = [0 for i in range(3 * n + 1)]
    dp[0] = abc[0][0]
    dp[1] = abc[0][1]
    dp[2] = abc[0][2]
    for i in range(1,n):
        dp[3 * i] = max(dp[3 * i], dp[3 * (i - 1) + 1] + abc[i][0], dp[3 * (i - 1) + 2] + abc[i][0])
        dp[3 * i + 1] = max(dp[3 * i + 1], dp[3 * (i - 1) + 2] + abc[i][1], dp[3 * (i - 1)] + abc[i][1])
        dp[3 * i + 2] = max(dp[3 * i + 2], dp[3 * (i - 1) + 1] + abc[i][2], dp[3 * (i - 1)] + abc[i][2])
    dp[3 * n] = max(dp)
    print(dp[3*n])

    return

#D
def D():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**5
    1≤wi≤W
    1≤vi≤10**9"""
    n, w = LI()
    wv = LIR(n)
    dp = [[0 for k in range(w + 1)] for i in range(n + 2)]
    for i in range(1,n + 1):
        for j in range(w + 1):
            if j < wv[i-1][0]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i - 1][0]] + wv[i - 1][1])
    print(dp[n+1][w])

    
    return

#E
def E():
    """N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 
    各 i (1≤i≤N) について、品物i の重さはwi で、価値はvi です。
    太郎君は、N 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 
    ナップサックの容量は W であり、持ち帰る品物の重さの総和は W以下でなければなりません。
    太郎君が持ち帰る品物の価値の総和の最大値を求めてください
    
    入力はすべて整数である。
    1≤N≤100
    1≤W≤10**9
    1≤wi≤W
    1≤vi≤10**3"""
    n, w = LI()
    wv = LIR(n)
    dp = [[float("INF") for i in range(10 ** 5 + 1)] for k in range(n + 1)]
    dp[0][0] = 0
    for i in range(n):
        for k in range(10 ** 5 + 1):
            if k < wv[i][1]:
                dp[i + 1][k] = dp[i][k]
            else:
                dp[i + 1][k] = min(dp[i][k], dp[i][k - wv[i][1]] + wv[i][0])
    ans = 0
    for i in range(10 ** 5 + 1):
        if dp[n][i] <= w:
            ans = i
    print(ans)

    return

#F
def F():
    s = S()
    t = S()
    dp = [[0 for i in range(len(t)+1)] for k 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:
                if dp[i][j + 1] < dp[i + 1][j]:
                    dp[i + 1][j + 1] = dp[i + 1][j]
                else:
                    dp[i + 1][j + 1] = dp[i][j + 1]
    ss = len(s)
    tt = len(t)
    ans = ""
    si = ss
    ti = tt
    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:
            si -= 1
            ti -= 1
            ans = s[si]+ans


    print(ans)
    return

#G
def G():
    n, m = LI()
    xy = LIR_(m)
    edge = [[] for i in range(n)]
    for x,y in xy:
        edge[x].append(y)
    dp = [0 for i in range(n)]
    def ans(dp, i):
        #print(dp, i)
        if dp[i] != 0:
            return dp[i]
        else:
            if len(edge[i]) == 0:
                return 0
            ansb = 0
            for k in edge[i]:
                #print(dp, k , i)
                ansb = max(ansb, ans(dp, k) + 1)
                dp[i] = max(ansb, dp[i])
                #print(dp)
            return ansb
            
    for i in range(n):
        dp[i] = ans(dp, i)
    print(max(dp))
    return

#H
def H():
    h, w = LI()
    a = SR(h)
    dp = [[0 for i in range(w)] for k in range(h)]
    for i in range(w):
        if a[0][i] == "#":
            break
        dp[0][i] = 1
    for i in range(h):
        if a[i][0] == "#":
            break
        dp[i][0] = 1
    for i in range(1,w):
        for k in range(1, h):
            #print(i,k, dp)
            if a[k - 1][i] == ".":
                if a[k][i - 1] == ".":
                    dp[k][i] = dp[k - 1][i] + dp[k][i - 1] % mod
                else:
                    dp[k][i] = dp[k - 1][i]
            else:
                if a[k][i - 1] == ".":
                    dp[k][i] = dp[k][i - 1]
    print(dp[h-1][w-1] % mod)

    return

#I
def I():
    n = II()
    p = LF()
    dp = [[0 for k in range(n+1)] for i in range(n+1)]
    dp[1][1] = p[0]
    dp[1][0] = 1-p[0]
    for i in range(2,n+1):
        for k in range(i + 1):
            if k == 0:
                
                dp[i][k] = dp[i-1][k] * (1 - p[i-1])
            else:
                dp[i][k] = dp[i - 1][k - 1] * p[i - 1] + dp[i - 1][k] * (1 - p[i - 1])
    #print(dp)
    print(sum(dp[n][n//2+1:]))
    return 
#J
def J():
    n = II()
    a = LI()


#K


#L

#M
#N
# O
# P
# Q
# R
# S
# T
# U
# V
# W
# X
# Y
# Z


#Solve
if __name__ == '__main__':
    F()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#syakyo https://atcoder.jp/contests/dp/submissions/3956913
s=input()
t=input()

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

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

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

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(1,len(dp)):
    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])
out=''
i=len(s)
j=len(t)
while i!=0 and j!=0:
    if s[i-1]==t[j-1]:
        out+=s[i-1]
        i-=1
        j-=1
    elif dp[i][j-1]>dp[i-1][j]:
        j-=1
    else:
        i-=1
print(out[::-1])

Submission status: Accepted

Solution code:
import sys

def solve():
    # dp[i][j] = LCS(s[:i+1],t[:j+1])
    sLen, tLen = len(s),len(t),
    dp = [ [( 0 , -1 )]*(tLen+1)  for _ in range(sLen+1) ]
    for i in range(1,sLen+1):
        for j in range(1,tLen+1):
            comp = [ dp[i][j-1][0],dp[i-1][j-1][0]+int(s[i-1]==t[j-1]),dp[i-1][j][0]]
            argmax = comp.index(max(comp))
            dp[i][j] = ( comp[argmax] , argmax )

    ans = ""
    i,j = sLen, tLen
    for _ in range(sLen+tLen):
        if dp[i][j][1] == 0:
            j -= 1
        elif dp[i][j][1] == 1:
            ans += s[i-1]
            i -= 1
            j -= 1
        elif dp[i][j][1] == 2:
            i -= 1
        else:
            break
    return ans[::-1]

if __name__ == '__main__':
    s = sys.stdin.readline()
    t = sys.stdin.readline()
    print(solve())

Submission status: Accepted

Solution code:
import sys

s = sys.stdin.readline()
t = sys.stdin.readline()

# dp[i][j] = LCS(s[:i],t[:j])
sLen, tLen = len(s),len(t),
dp = [ [( 0 , -1 )]*(tLen+1)  for _ in range(sLen+1) ]
for i in range(1,sLen+1):
    for j in range(1,tLen+1):
        comp = [ dp[i][j-1][0],dp[i-1][j-1][0]+int(s[i-1]==t[j-1]),dp[i-1][j][0]]
        argmax = comp.index(max(comp))
        dp[i][j] = ( comp[argmax] , argmax )

ans = ""
i,j = sLen, tLen
for _ in range(sLen+tLen):
    if dp[i][j][1] == 0:
        j -= 1
    elif dp[i][j][1] == 1:
        ans += s[i-1]
        i -= 1
        j -= 1
    elif dp[i][j][1] == 2:
        i -= 1
    else:
        break

print(ans[::-1])

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)]
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])
#back trace
ans = []
while i >= 0 and j >= 0:
    if dp[i+1][j+1] == dp[i][j] + 1 and s[i] == t[j]:
        ans.append(s[i])
        i -= 1
        j -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    else: i -= 1
ans.reverse()
print(''.join(ans))

Submission status: Accepted

Solution code:
def lcs(a, b):
    lengths = [[0] * (len(b) + 1) for i in range(len(a) + 1)]

    for i, x in enumerate(a):
        for j, y in enumerate(b):
            if x == y:
                lengths[i + 1][j + 1] = lengths[i][j] + 1
            else:
                lengths[i + 1][j + 1] = max(lengths[i + 1][j], lengths[i][j + 1])

    result = []
    x, y = len(a), len(b)
    while x != 0 and y != 0:
        if lengths[x][y] == lengths[x - 1][y]:
            x -= 1
        elif lengths[x][y] == lengths[x][y - 1]:
            y -= 1
        else:
            result.append(a[x - 1])
            x -= 1
            y -= 1

    return result[::-1]


print(''.join(lcs(input(), input())))

Submission status: Accepted

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

# dp[i][j] : 文字列Sのi文字目までと文字列Tのj文字目まででの値(len, 例)

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

dp[0][0] = 0

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

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

print(st)

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] = 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 i * j :
    if S[i-1] == T[j-1] :
        ans = S[i-1] + ans
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j] :
        i -= 1
    else :
        j -= 1
    
print(ans)

Submission status: Accepted

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

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

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

i = len_s
j = len_t
res = ""
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]
        i -= 1
        j -= 1

print(res[::-1])

Submission status: Accepted

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

len_s = len(s)
len_t = len(t)
INF = float('inf')

dp = [[-INF] * (len_t+1) for _ in range(len_s+1)]

dp[0][0] = 0

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

i = len_s
j = len_t
ans = ""
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans += s[i - 1]
        i -= 1
        j -= 1

print(ans[::-1])

Submission status: Accepted

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

len_s = len(s)
len_t = len(t)
INF = float('inf')

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

dp[0][0] = 0

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

i = len_s
j = len_t
ans = ""
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans += s[i - 1]
        i -= 1
        j -= 1

print(ans[::-1])

Submission status: Accepted

Solution code:
S = input()
T = input()
n = len(S)
m = len(T)

DP = [[0] * (m+1) for i in range(n+1)]
for i in range(n):
    for j in range(m):
        if S[i] == T[j]:
            DP[i+1][j+1] = DP[i][j] + 1
        else:
            DP[i+1][j+1] = max(DP[i+1][j], DP[i][j+1])

ans = ''
while n > 0 and m > 0:
    if S[n-1] == T[m-1]:
        n -= 1
        m -= 1
        ans += S[n]
    elif DP[n][m-1] > DP[n-1][m]:
        m -= 1
    else:
        n -= 1

print(ans[::-1])

Submission status: Accepted

Solution code:
def dump(dp, i1_max, i2_max):
    for i1 in range(0, i1_max + 1):
        for i2 in range(0, i2_max + 1):
            print('%4d' % dp[i1][i2], end='')
        print()


s = input()
t = input()
s_len = len(s)
t_len = len(t)
inf = 1 << 60

# dp[i][j] = sのi文字目、tのj文字目までの最大長の部分文字列
dp = [[-inf for j in range(t_len + 1)] for i in range(s_len + 1)]
dp[0][0] = 0
for si in range(0, s_len + 1):
    for ti in range(0, t_len + 1):
        if si >= 1 and ti >= 1:
            if s[si - 1] == t[ti - 1]:
                dp[si][ti] = max(dp[si][ti], dp[si - 1][ti - 1] + 1)
        if si >= 1:
            dp[si][ti] = max(dp[si][ti], dp[si - 1][ti])
        if ti >= 1:
            dp[si][ti] = max(dp[si][ti], dp[si][ti - 1])

ans = ''
si = s_len
ti = t_len
#dump(dp, si, ti)
while si != 0 and ti != 0:
    if si >= 1 and ti >= 1:
        if (dp[si - 1][ti - 1] == dp[si][ti] - 1) and s[si - 1] == t[ti - 1]:
            ans = s[si - 1] + ans
            si -= 1
            ti -= 1
            continue
        if dp[si - 1][ti - 1] == dp[si][ti]:
            si -= 1
            ti -= 1
            continue
    if si >= 1:
        if dp[si - 1][ti] == dp[si][ti]:
            si -= 1
            continue
    if ti >= 1:
        if dp[si][ti - 1] == dp[si][ti]:
            ti -= 1
            continue

print(ans)

Submission status: Accepted

Solution code:

S = input()
T = input()
N = len(S)
M = len(T)

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

i = N
j = M
cnt = dp[N][M]

# while i > 0 and j > 0:
#     if dp[i][j] == dp[i-1][j]:
#         i -= 1
#     elif dp[i][j] == dp[i][j-1]:
#         j -= 1
#     else:
#         i -= 1 ; j -= 1
#         res.append(S[i])
while cnt :
    while cnt == dp[i][j]:
        i -= 1
    i += 1
    while cnt == dp[i][j]:
        j -= 1
    j += 1
    res.append(S[i-1])
    cnt -= 1
    i -= 1; j -= 1
print("".join(reversed(res)))

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

s = input()[:-1]
t = input()[:-1]

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


def solve():
    for i, cs in enumerate(s):
        for j, ct in enumerate(t):
            if cs == ct:
                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 i >= 0 and j >= 0:
        if s[i] == t[j]:
            ans += s[i]
            i -= 1
            j -= 1
        else:
            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:
                break
    print("".join(reversed(ans)))


solve()

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor

import heapq
import itertools
import operator


inf = float('inf')


def get_int():
    return int(input())


def get_str():
    return input().strip()


def get_list_of_int():
    return [int(i) for i in input().split()]


def get_char_list():
    return list(input().strip())


# inputs
S, T = "", ""


def set_inputs():
    global S, T
    S = get_str()
    T = get_str()
    return


def main():
    set_inputs()
    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][j-1], dp[i-1][j])

    i = len(S)
    j = len(T)
    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-1]
            i -= 1
            j -= 1
    print(''.join(reversed(ret)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import sys
sys.setrecursionlimit(4000)


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)


s = ''
dp = []
def main():
    global s
    global dp
    s = input()
    t = input()

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

    dp = [[0 for j in range(m+1)] for i in range(n + 1)]

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

    #  print(t)
    #  v = 0
    #  result = ''
    #  print('dp[-1]', dp[-1])
    #  for idx, i in enumerate(dp[-1]):
    #      print(idx, i)
    #      if i == v + 1:
    #          result += t[idx-1]
    #          v += 1

    #  print(result)

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

    #  print(lcs_str[::-1])
    print_lcs(n, m)
    global ans
    print("".join(ans))

ans = []

def print_lcs(i, j):
    global s, dp, ans
    if not i or not j:
        return ''

    ret = dp[i][j]
    if ret == dp[i-1][j]:
        print_lcs(i - 1, j)
    elif ret == dp[i][j-1]:
        print_lcs(i, j-1)
    else:
        print_lcs(i - 1, j - 1)
        ans.append(s[i-1])
        #  print(s[i-1], end='', flush=True)


main()

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(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])
            
i=len(s)
j=len(t)
ans=""

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

Submission status: Accepted

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

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

i = len(s)
j = len(t)
res = ""
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]
        i -= 1
        j -= 1

ans = ""
for i in reversed(range(len(res))):
    ans += res[i]

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**7) 
 
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())

s = ns()
t = ns()

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

dp = [[0]*(lent+1) for _ in range(lens+1)]

for idx in range(lens):
    for jdx in range(lent):
        dp[idx+1][jdx+1] = max(dp[idx][jdx] + bool(s[idx] == t[jdx]),
                               dp[idx+1][jdx],
                               dp[idx][jdx+1])
    
def lcs(spos: int, tpos: int, cur: str, s:str, t:str, dp: list) -> str:

    if spos == 0 or tpos == 0:
        return cur
    
    else:
        nrth = dp[spos-1][tpos]
        west = dp[spos][tpos-1]
        ntws = dp[spos-1][tpos-1]

        mx = max(nrth, west, ntws)
        
        if mx == ntws and ntws+1 == dp[spos][tpos]:
            return lcs(spos-1, tpos-1, cur+s[spos-1], s,t,dp)
 
        
        elif mx == nrth:
            return lcs(spos-1, tpos, cur, s, t, dp)
        
        else:
            return lcs(spos, tpos-1, cur, s, t, dp)
            
           

            
            
print(lcs(lens, lent, "", s, t, dp)[::-1])

Submission status: Accepted

Solution code:
s, t = raw_input().strip(), raw_input().strip()
n, m = len(s), len(t)

dp = [[0 for i in xrange(m)] for j in xrange(n)]

dp[0][0] = int(s[0] == t[0])

i = 0
for j in xrange(1, m):
    if s[i] == t[j]: dp[i][j] = 1
    else: dp[i][j] = dp[i][j - 1]

j = 0
for i in xrange(1, n):
    if s[i] == t[j]: dp[i][j] = 1
    else: dp[i][j] = dp[i - 1][j]

for i in xrange(1, n):
    for j in xrange(1, m):
        if i == 0 and j == 0: continue
        if s[i] == t[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])

c = [0 for i in xrange(dp[n - 1][m - 1])]

st = len(c) - 1
i, j = n - 1, m - 1
while st >= 0:
    if s[i] == t[j]:
        c[st] = s[i]
        i -= 1
        j -= 1
        st -= 1
    else:
        if i >= 1 and j >= 1:
            if dp[i][j - 1] < dp[i - 1][j]: i -= 1
            else: j -= 1
        else:
            if i >= 1: i -= 1
            else: j -= 1

print ''.join(c)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

s = raw_input()
t = raw_input()

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

l = dp[len(s)][len(t)]
resp = []
inds = len(s)
indt = len(t)
while len(resp) < l:
    if s[inds - 1] == t[indt - 1] and dp[inds][indt] == 1 + dp[inds - 1][indt - 1]:
        resp.append(s[inds - 1])
        inds -= 1
        indt -= 1
        continue
    if dp[inds][indt] == dp[inds - 1][indt - 1]:
        inds -= 1
        indt -= 1
        continue
    if dp[inds][indt] == dp[inds - 1][indt]:
        inds -= 1
        continue
    if dp[inds][indt] == dp[inds][indt - 1]:
        indt -= 1
        continue
resp.reverse()
print(''.join(resp))

Submission status: Accepted

Solution code:
 # all credits to iehn submission #3972219 - how the duck did he manage to fit in time?..
def main():
    s = [ord(c) - 97 for c in input()]
    t = [ord(c) - 97 for c in input()]
    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())