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

"""
Created on Sun Mar 17 09:02:00 2019
DPF3
@author: maezawa
"""

s = input()
t = input()

ns = len(s)
nt = len(t)

dp = [[0 for _ in range(nt+1)] for _ in range(ns+1)]

for si in range(ns):
    for ti in range(nt):
        if s[si] == t[ti]:
            dp[si+1][ti+1] = max(dp[si][ti]+1, dp[si+1][ti], dp[si][ti+1])
        else:
            dp[si+1][ti+1] = max(dp[si+1][ti], dp[si][ti+1])

ans = ''
si = ns
ti = nt
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]*(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])

Solution (Python):
import sys

def solve():
    
    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())

Solution (Python):
import sys

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


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

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

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

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

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



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)

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

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

ind_x = len(T)
ind_y = len(S)

while ind_x * ind_y :
    if S[ind_y-1] == T[ind_x-1] :
        ans = S[ind_y-1] + ans
        ind_x -= 1
        ind_y -= 1
    elif dp[ind_y][ind_x] == dp[ind_y-1][ind_x] :
        ind_y -= 1
    else :
        ind_x -= 1
    

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

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

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

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

Solution (Python):
a = input()
b = input()

aa = len(a)

bb = len(b)

dp = [[0]*(bb+1) for i in range(aa+1)]

for i in range(aa):
	for j in range(bb):
		if a[i] == b[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 = ""

while aa > 0 and bb > 0:
	if a[aa-1] == b[bb-1]:
		aa -= 1
		bb -= 1
		ans += a[aa]
	elif dp[aa][bb-1] > dp[aa-1][bb]:
		bb -= 1
	else:
		aa -= 1
print(ans[::-1])

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

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

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)

Solution (Python):

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

Solution (Python):

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

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



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

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


main()

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

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

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

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

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

Solution (Python):

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

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

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

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
 

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

 
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

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

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

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

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


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


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


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

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


res=[]
j=len(s)-1
i=len(t)-1
while i>=0 and j>=0:
    if s[j]==t[i]: 
        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



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

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

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


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

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


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)

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



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

print(ans)

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

H = len(s)
W = len(t)
dp = [[0 for x in range(W+1)] for y in range(H+1)]

for y in range(H) :
    for x in range(W) :
        if s[y] == t[x] :
            dp[y+1][x+1] = dp[y][x]+1
        else :
            dp[y+1][x+1] = max(dp[y+1][x], dp[y][x+1])

ans = ""

while (H > 0) and (W > 0) :
    if dp[H][W] == dp[H-1][W] :
        H -= 1
    elif dp[H][W] == dp[H][W-1] :
        W -= 1
    else :
        H -= 1
        W -= 1
        ans = s[H] + ans

print(ans)

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

Solution (Python):
s = input()
t = input()
ls = len( s)
lt = len( t)
CNT = [ [0]*(ls+1) for _ in range(lt+1)]
for i in range(1,lt+1):
    for j in range(1,ls+1):
        if s[j-1] == t[i-1]:
            CNT[i][j] = CNT[i-1][j-1]+1
        else:
            if CNT[i][j-1] >= CNT[i-1][j]:
                CNT[i][j] = CNT[i][j-1]
            else:
                CNT[i][j] = CNT[i-1][j]
i = lt
j = ls
ans = ""
while i > 0 and j > 0:
    if t[i-1] == s[j-1]:
        ans += t[i-1]
        i -= 1
        j -= 1
    else:
        if CNT[i-1][j] > CNT[i][j-1]:
            i -= 1
        else:
            j -= 1
print( ans[::-1])

Solution (Python):



S,T = input(), input()
S,T = list(map(lambda x: ord(x)-97, S)), list(map(lambda x: ord(x)-97, 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)))

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


i = 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)