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

Solution (Python):


"""
参考：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])
        
        if 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-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)

Solution (Python):
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)

Solution (Python):
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

Solution (Python):
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(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])



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)

Solution (Python):
ss, ts = input(), input()

lenS, lenT = len(ss), len(ts)

dp = [[0]*(lenT+1) for _ in range(lenS+1)]
dp[0][0] = 0
for iS, s in enumerate(ss, 1):
    for jT, t in enumerate(ts, 1):
        if s == t:
            dp[iS][jT] = dp[iS-1][jT-1] + 1
        else:
            dp[iS][jT] = max(dp[iS-1][jT], dp[iS][jT-1])

ans = ''
iS, jT = lenS, lenT
while iS*jT:
    if ss[iS-1] == ts[jT-1]:
        ans += ss[iS-1]
        iS, jT = iS-1, jT-1
    elif dp[iS-1][jT] >= dp[iS][jT-1]:
        iS -= 1
    else:
        jT -= 1

print(ans[::-1])

Solution (Python):
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()

Solution (Python):
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])

Solution (Python):
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]))

Solution (Python):


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

st = []

x = len(S)
y = 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
        st += S[x]
print("".join(reversed(st)))

Solution (Python):
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)))

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

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

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


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)

Solution (Python):
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)

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


s = input()
t = input()



def solve(s, t):
    dp = makelist(len(s)+1, len(t)+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: 
            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))

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

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

Solution (Python):
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])
        

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)

Solution (Python):


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




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

Solution (Python):
def f_lcs(S, T):
    """
    文字列s, tが与えられる。sの部分列かつtの部分列であるような文字列のうち、
    最長のものを1つ求めよ。文字列xの部分列とは、xから0個以上の文字を除いたあと、
    残りの文字を元の順序で連結して得られる文字列のことである。
    """
    
    from itertools import product

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

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

S = input()
T = input()
print(f_lcs(S, T))

Solution (Python):
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())

Solution (Python):
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 = [c for c in S()]
    t = [c for c in S()]
    sl = len(s)
    tl = len(t)
    rr = [[0] * (tl) for _ in range(sl)]
    for i in range(sl):
        for j in range(tl):
            if s[i] == t[j]:
                if i > 0 and j > 0:
                    rr[i][j] = rr[i-1][j-1] + 1
                else:
                    rr[i][j] = 1
                continue

            m = 0
            if i > 0:
                m = rr[i-1][j]
            if j > 0 and m < rr[i][j-1]:
                m = rr[i][j-1]
            rr[i][j] = m

    i = sl-1
    j = tl-1
    r = []
    while i >= 0 and j >= 0:
        if s[i] == t[j]:
            r.append(s[i])
            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(r[::-1])


print(main())

Solution (Python):
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]))

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

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

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-1][j],DP[i][j-1])
            
        
x,y=len_s,len_t
ANS=""

while x>0 and y>0:
    if x>0 and DP[x-1][y]==DP[x][y]:
        x-=1
    elif y>0 and DP[x][y-1]==DP[x][y]:
        y-=1
    else:
        ANS+=s[x-1]
        x-=1
        y-=1

print(ANS[::-1])

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

dp = [[-1]*(LT+2) for i in range(LS+2)]
for i in range(LS-1, -1, -1):
    X = dp[i]; Y = dp[i+1]; si = S[i]
    r = X[LT]
    for j in range(LT-1, -1, -1):
        X[j] = r = max(Y[j+1] + 1, Y[j], r) if si == T[j] else max(Y[j], r)
i = j = 0
ans = []
X = dp[0]; Y = dp[1]
while i < LS and j < LT:
    if S[i] == T[j] and X[j] == Y[j+1] + 1:
        ans.append(S[i])
        i += 1; j += 1
        X = Y; Y = dp[i+1]
    elif X[j] == Y[j]:
        i += 1
        X = Y; Y = dp[i+1]
    else:
        j += 1
print(*map(chr, ans), sep='')

Solution (Python):
*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='')

Solution (Python):
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()

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

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

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

res = []
x,y = len(S),len(T)
v = dp[x][y]
while v > 0:
  if dp[x-1][y] == v:
    x -= 1
  elif dp[x][y-1] == v:
    y -= 1
  else:
    res.append(S[x-1])
    x -= 1
    y -= 1

  v = dp[x][y]

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

Solution (Python):
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))

Solution (Python):
def lcs(x, y):
    m = len(x)
    n = len(y)

    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])

    lcs_str = ''
    i, j = m, n
    while i > 0 and j > 0:
        if x[i-1] == y[j-1]:
            lcs_str += x[i-1]
            i -= 1
            j -= 1
        else:
            if c[i][j] == c[i-1][j]:
                i -= 1
            else:
                j -= 1

    return lcs_str[::-1]


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

Solution (Python):
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])

Solution (Python):
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))
解()

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


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



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

Solution (Python):
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])

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


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

Solution (Python):
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 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])

Solution (Python):
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

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
    
    H.append(t[x-1])
    N-=1
    y-=1
    x-=1
print(''.join(H[::-1]))

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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)

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

l_s = len(s)
l_t = len(t)

dp = [[0] * (l_t + 1) for i in range(l_s + 1)]

ans = ""
for j in range(l_s):
    for i in range(l_t):
        if s[j] == t[i]:
            dp[j + 1][i + 1] = dp[j][i] + 1
        else:
            dp[j + 1][i + 1] = max(dp[j][i + 1], dp[j + 1][i])

if dp[l_s][l_t] == 0:
    print(" ")
    exit()

ans = ""
i = l_t
j = l_s

while i > 0 and j > 0:
    if s[j - 1] == t[i - 1]:
        ans += s[j - 1]
        i -= 1
        j -= 1
    else:
        if dp[j - 1][i] > dp[j][i - 1]:
            j -= 1
        else:
            i -= 1

print(ans[::-1])

Solution (Python):
s = input()
t = input()
dp = [0]
lcs = ['']
for b in t:
    search_idx = 0
    ncs = lcs[:]
    for i, curr_idx in enumerate(dp):
        char_idx = s.find(b, search_idx)
        if char_idx == -1:
            break
        next_idx = char_idx + 1
        if next_idx < curr_idx:
            dp[i] = next_idx
            ncs[i] = lcs[i - 1] + b
        search_idx = curr_idx
    else:
        char_idx = s.find(b, search_idx)
        if char_idx > -1:
            dp.append(char_idx + 1)
            ncs.append(lcs[-1] + b)
    lcs = ncs
print(lcs[-1])

Solution (Python):
import sys

sys.setrecursionlimit(4000)
a = input()
b = input()
def print_lcs (a, b, lcs, i, j):
    global ans
    if (i == 0 or j == 0):
        return
    if (a[i-1] == b[j-1]):
        print_lcs(a, b, lcs, i - 1, j - 1)
        ans.append(a[i - 1])
    else:
        if lcs[i-1][j] >= lcs[i][j-1]:
            print_lcs(a, b, lcs, i - 1, j)
        else:
            print_lcs(a, b, lcs, i, j - 1)

lcs = [ [0 for j in range(len(b) + 1)] for i in range(len(a)+1) ]

for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        if a[i - 1] == b[j - 1]:
            x = 1
        else:
            x = 0
        lcs[i][j] = max(lcs[i-1][j-1] + x, lcs[i-1][j], lcs[i][j-1])

ans = []
print_lcs(a, b, lcs, len(a), len(b))
print("".join(ans))