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


s = input()
t = input()

DP = [[0]*(len(t)+1) for i in range(len(s)+1)]

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

Solution (Python):
S=input()
T=input()
memo = [[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]:
            memo[i][j] = memo[i-1][j-1] + 1
        else:
            memo[i][j] = max(memo[i-1][j], memo[i][j-1])
 
ans = ''
i = len(S)
j = len(T)
while i > 0 and j > 0:
    if memo[i][j] == memo[i-1][j]:
        i-=1
    elif memo[i][j] == memo[i][j-1]:
        j-=1
    else:
        i-=1
        j-=1
        ans = ans + S[i]

ans = ''.join(reversed(ans))
print(ans)

Solution (Python):
import sys

input = sys.stdin.readline

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

N = len(s) + 1
M = len(t) + 1



dp = [[0]*M for _ in range(N)]


for i in range(1, N):
    for j in range(1, M):
        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])

"""
復元
もしdp[i][j] == dp[i][j-1]ならt[j-1]は使われていないことがわかる
もしdp[i][j] == dp[i-1][j]ならs[i-1]は使われていないことがわかる
それ以外の場合、s[i-1], t[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:
        ans = s[i-1] + ans  
        i -= 1
        j -= 1
print(ans)

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

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

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

n, m = len(s), 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)

Solution (Python):
s=input()
l1=len(s)
t=input()
l2=len(t)
arr=[[0]*(l2+1) for _ in range(l1+1)]
for i in range(l1):
  for j in range(l2):
    if s[i]==t[j]:
      arr[i+1][j+1]=1
for i in range(1,l1+1):
  for j in range(1,l2+1):
    if arr[i][j]==1:
      arr[i][j]+=arr[i-1][j-1]
    else:
      arr[i][j]=max(arr[i-1][j],arr[i][j-1])
check=arr[l1][l2]
pos=0
ans=''
for i in range(l1,-1,-1):
  for j in range(l2-pos,-1,-1):
    if j==0:
      continue
    if arr[i][j]==check and arr[i][j-1]==check-1 and arr[i-1][j]==check-1:
      ans+=t[j-1]
      pos=l2-j+1
      check-=1
      break
print(ans[::-1])

Solution (Python):
s = input()
s_len = len(s)
t = input()
t_len = len(t)
dp = [[0] * (t_len + 1) for _ in range(s_len + 1)]

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

string = ""
cnt = dp[s_len][t_len]

while t_len > 0 and s_len > 0:
    if dp[s_len][t_len] == dp[s_len - 1][t_len]:
        s_len -= 1
    elif dp[s_len][t_len] == dp[s_len][t_len - 1]:
        t_len -= 1
    else:
        string += s[s_len - 1]
        s_len -= 1
        t_len -= 1


print(string[::-1])

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

    '''復元を実行
    最長の長さを求めるなら return dp[len(str1)][len(str2)] をするとよい'''
    res = ''
    i, j = len(str1), len(str2)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            res = str1[i-1] + res
            i -= 1
            j -= 1
    return res

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

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

    '''復元を実行
    最長の長さを求めるなら return dp[len(str1)][len(str2)] をするとよい
    '''
    res = ''
    i, j = len(str1), len(str2)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            res = str1[i-1] + res
            i -= 1
            j -= 1
    return res

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

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

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

Solution (Python):
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) 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 MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))


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

ans = []
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
        ans.append(s[x])
print(''.join(ans[::-1]))

Solution (Python):
def main():
    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] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
    ans = ''
    while ls > 0 and lt > 0:
        if s[ls - 1] == t[lt - 1]:
            ls -= 1
            lt -= 1
            ans += s[ls]
            continue
        if dp[ls - 1][lt] > dp[ls][lt - 1]:
            ls -= 1
        else:
            lt -= 1
    print(ans[::-1])


main()

Solution (Python):
import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())



def lcs(s, t):
    '''s,tは文字列をリスト化したもの'''
    n = len(s)
    m = len(t)
    s.append('$')
    t.append('%')
    dp = [[0 for _j in range(m + 2)] for _i in range(n + 2)]
    dp[0][0] = 0
    for i in range(n+1):
        for j in range(m+1):
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
            dp[i][j + 1] = max(dp[i][j + 1], dp[i][j])
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + (s[i] == t[j]))
    
    '''復元する'''
    length = dp[n][m]
    ans = ['']*(length+1)
    while(length > 0):
        if(s[n] == t[m]):
            ans[length] = s[n]
            n-=1
            m-=1
            length-=1
        elif(dp[n+1][m+1] == dp[n][m+1]):
            n-=1
        else:
            m-=1
    return ''.join(ans[1:])


def ALDS1_10_C():
    q = ii()
    for _ in range(q):
        s = li()
        t = li()
        print(lcs(s, t))

def EDPC_F():
    s = li()
    t = li()
    print(lcs(s,t))


if __name__ == '__main__':
    
    EDPC_F()

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


dp = [[0] * (len(T) + 1) for i in range(len(S) + 1)]
dp2 = [[(0, 0)] * (len(T) + 1) for i in range(len(S) + 1)]
for i, s in enumerate(S, start=1):
    for j, t in enumerate(T, start=1):
        if s == t:
            dp[i][j] = dp[i - 1][j - 1] + 1
            dp2[i][j] = (i - 1, j - 1)
        elif dp[i - 1][j] > dp[i][j - 1]:
            dp[i][j] = dp[i - 1][j]
            dp2[i][j] = (i - 1, j)
        else:
            dp[i][j] = dp[i][j - 1]
            dp2[i][j] = (i, j - 1)

ans = ''
s, t = len(S), len(T)
while (s > 0) and (t > 0):
    if S[s - 1] == T[t - 1]:
        ans += S[s - 1]
    ns, nt = dp2[s][t]
    s, t = ns, nt

print(ans[::-1])

Solution (Python):
s = input()
t = input()
S = len(s)
T = len(t)
dp = [[0]*(T+1) for _ in range(S+1)]
revans = ''

for i in range(1, S+1):
    for j in range(1, 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])

while dp[i][j] > 0:
    if dp[i-1][j] == dp[i][j]:
        i -= 1
    elif dp[i][j-1] == dp[i][j]:
        j -= 1
    else:
        revans += s[i-1]
        i -= 1
        j -= 1

print(revans[::-1])

Solution (Python):
import fileinput

def lcs(a, b):
    lcs_table = []

    def get_lcs(a_idx, b_idx):
        if a_idx < 0 or b_idx < 0:
            return 0
        else:
            return lcs_table[a_idx][b_idx] 

    for a_idx, last_a in enumerate(a):
        lcs_table.append([0] * len(b))
        for b_idx, last_b in enumerate(b):
            if last_a == last_b:
                new_lcs = get_lcs(a_idx - 1, b_idx - 1) + 1
            else:
                new_lcs = max(get_lcs(a_idx - 1, b_idx), get_lcs(a_idx, b_idx - 1))
            lcs_table[a_idx][b_idx] = new_lcs

    result = []
    current_a_idx = len(a) - 1
    current_b_idx = len(b) - 1
    while current_a_idx >= 0 and current_b_idx >= 0:
        if a[current_a_idx] == b[current_b_idx]:
            result.append(a[current_a_idx])
            current_a_idx -= 1
            current_b_idx -= 1
        else:
            if get_lcs(current_a_idx, current_b_idx) == 0:
                break
            if get_lcs(current_a_idx - 1, current_b_idx) > get_lcs(current_a_idx, current_b_idx - 1):
                current_a_idx -= 1
            else:
                current_b_idx -= 1

    return "".join(result[::-1])

inp = fileinput.FileInput()

a = inp.readline()
b = inp.readline()
print(lcs(a, b))

Solution (Python):

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

cnt=dp[-1][-1]
ans=[]
ct,cs=nt,ns
while cnt>0:
    while dp[ct][cs]==dp[ct-1][cs] and ct>0:
        ct-=1
        
    while dp[ct][cs]==dp[ct][cs-1] and cs>0:
        cs-=1

    ans.append(t[ct-1])
    cnt-=1
    
    ct-=1
    cs-=1

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

Solution (Python):

import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def lcs(xs, ys):
    dp = [([0] * (len(ys) + 1)) for _ in range(len(xs) + 1)]
    for i, x in enumerate(xs):
        for j, y in enumerate(ys):
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j], dp[i][j] + int(x == y))

    s = []
    p = (-1, -1)
    while 0 < dp[p[0]][p[1]]:
        if dp[p[0]][p[1]] == dp[p[0]-1][p[1]]:
            p = (p[0]-1, p[1])
        elif dp[p[0]][p[1]] == (dp[p[0]-1][p[1]-1] + int(xs[p[0]] == ys[p[1]])):
            s.append(xs[p[0]])
            p = (p[0]-1, p[1]-1)
        else:
            p = (p[0], p[1]-1)

    return ''.join(reversed(s))


def solve(s: str, t: str):
    return lcs(s, t)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  
    t = next(tokens)  
    result = solve(s, t)
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):
S = input()
T = input()
len_S = len(S)
len_T = len(T)

dp = {i: {j: 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, j = len_S, len_T
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans = S[i-1] + ans
        i, j = i - 1, j - 1
    else:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        else:
            j -= 1
print(ans)

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

	Z = 3010
	dp = [[0] * Z for _ in range(Z)]
	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, j, result = len(S), len(T), ""
	while 0 < i and 0 < j:
		if dp[i][j] == dp[i - 1][j]:
			i -= 1
		elif dp[i][j] == dp[i][j - 1]:
			j -= 1
		else:
			result = S[i - 1] + result
			i -= 1
			j -= 1
	print(result)

main()

Solution (Python):

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):
        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 = ''
n, m = len(s), len(t)
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)

Solution (Python):
def LCS(S, T):
    ls = len(S)
    lt = len(T)
    S = [-1] + [ord(s) for s in S]
    T = [-2] + [ord(t) for t in T]
    dp = [0]*((ls+1)*(lt+1))
    geta = ls + 1
    for j in range(1, lt+1):
        for i in range(1, ls+1):
            if S[i] == T[j]:
                dp[geta*j + i] = dp[geta*(j-1) + i-1] + 1
            else:
                dp[geta*j + i] = max(dp[geta*(j-1) + i], dp[geta*j + i-1])
    if not dp[-1]:
        return ''
    ans = [0]*dp[-1]
    i, j = ls, lt
    ctr = -1
    for _ in range(ls + lt):
        if i == 0 or j == 0:
            break
        if S[i] == T[j]:
            ans[ctr] = S[i]
            i -= 1
            j -= 1
            ctr -= 1
        elif dp[(j-1)*geta + i] >= dp[j*geta + i-1]:
            j -= 1
        else:
            i -= 1
    return ''.join([chr(a) for a in ans])
s = input().strip()
t = input().strip()
print(LCS(s, t))

Solution (Python):
import sys
input  =  sys.stdin.readline

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



s = input()
t = input()

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

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

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

L=dp[ls][lt]
ans = [0]*L
idx=L-1
while idx >= 0:

    if i>0 and dp[i-1][j] == dp[i][j]:
        i -= 1
    elif j>0 and dp[i][j-1] == dp[i][j]:
        j-=1
    else:
        i-=1
        j-=1
        ans[idx] = s[i]
        idx -= 1


print(''.join(ans))

Solution (Python):



s = input()
t = input()

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

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

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

L=dp[ls][lt]
ans = [0]*L
idx=L-1
i=ls
j=lt
while idx >= 0:

    if i>0 and dp[i-1][j] == dp[i][j]:
        i -= 1
    elif j>0 and dp[i][j-1] == dp[i][j]:
        j-=1
    else:
        i-=1
        j-=1
        ans[idx] = s[i]
        idx -= 1


print(''.join(ans))

Solution (Python):
def f():
    s = input()
    t = input()
    ls, lt = len(s), len(t)
    dp = [[0] * (ls + 1) for _ in range(lt + 1)]
    for i in range(lt):
        for j in range(ls):
            if s[j] == t[i]:
                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])
    r = ''
    i += 1
    j += 1
    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:
            r = s[j - 1] + r
            j -= 1
            i -= 1
    return r
 
 
if __name__ == '__main__':
    ans = f()
    print(ans)

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


cdp = [[None for _ in range(len(S)+1)] for _ in range(len(T)+1)]
ddp = [[None for _ in range(len(S)+1)] for _ in range(len(T)+1)]

cdp[0] = [0 for _ in range(len(S)+1)]
ddp[0] = [0 for _ in range(len(S)+1)]

for i in range(1,len(T)+1):
    for j in range(len(S)+1):
        if j == 0:
            
            cdp[i][j] = 0
            ddp[i][j] = 0
            continue
        if S[j-1] == T[i-1]:
            
            cdp[i][j] = cdp[i-1][j-1] + 1
            ddp[i][j] = 2
        else:
            if cdp[i][j-1] > cdp[i-1][j]:
                
                cdp[i][j] = cdp[i][j-1]
                ddp[i][j] = 1
            else:
                
                cdp[i][j] = cdp[i-1][j]
                ddp[i][j] = 0



i, j = len(T), len(S)
L = ''
while i > 0 and j > 0:
    if ddp[i][j] == 2:
        i -= 1
        j -= 1
        L += T[i]
    elif ddp[i][j] == 1:
        j -= 1
    elif ddp[i][j] == 0:
        i -= 1

print(L[::-1])

Solution (Python):
s = input().rstrip()
t = input().rstrip()
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])


h, w = len_s, len_t
ans = ""
while dp[h][w] != 0:
    while dp[h][w] == dp[h-1][w]:
        h -= 1
    while dp[h][w] == dp[h][w-1]:
        w -= 1
    h -= 1
    w -= 1
    ans += t[w]

print(ans[::-1])

Solution (Python):
def lcs(a, b):
    n = len(a)
    m = len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
 
    for i in range(n):
        for j in range(m):
            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])
 
    lcs_str = ''
    i, j = n, m
    while i >= 1 and j >= 1:
        if a[i - 1] == b[j - 1]:
            lcs_str += a[i - 1] 
            i -= 1
            j -= 1
        else:
            if dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1
 
    return lcs_str[::-1]
 
 
s = input()
t = input()
print(lcs(s, t))

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

    dp_table = [[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_table[i+1][j+1] = max(dp_table[i+1][j+1], dp_table[i][j]+1)
            dp_table[i+1][j+1] = max(dp_table[i+1][j+1], dp_table[i+1][j])
            dp_table[i+1][j+1] = max(dp_table[i+1][j+1], dp_table[i][j+1])

    
    mem_s = len(s)
    mem_t = len(t)
    ans = ""
    while True:
        if dp_table[mem_s][mem_t] == dp_table[mem_s][mem_t-1]:
            mem_t = mem_t - 1
        elif dp_table[mem_s][mem_t] == dp_table[mem_s-1][mem_t]:
            mem_s = mem_s - 1
        else:
        
            ans = s[mem_s-1] + ans
            mem_s = mem_s - 1
            mem_t = mem_t - 1
        if mem_s == 0 or mem_t == 0:
            break
    print(ans)

sub()

Solution (Python):
S = input()
T = input()
M = len(S)
N = len(T)
dp = [[0] * (N + 1) for i in range(M + 1)]

for i in range(M):
    for j in range(N):
        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])

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

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

S, T = len(s), len(t)

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

for i, SS in enumerate(s):
    for j, TT in enumerate(t):
        if SS == TT:
            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+1 and j+1:
    if dp[i+1][j+1] == dp[i][j+1]:
        i -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    else:
        ans = s[i] + ans
        i -= 1
        j -= 1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def mi(): return map(int, input().split())


def li(): return list(mi())


def li_(): return [int(x) - 1 for x in input().split()]


def lin(n: int): return [input() for _ in range(n)]


def llin(n: int): return [li() for _ in range(n)]


def llin_(n: int): return [li_() for _ in range(n)]


def lli(): return [list(map(int, l.split())) for l in input()]


def i(): return int(input())


def f(): return float(input())


def s(): return input().replace('\n', '')


def main():
    S = s()
    T = s()
    dp = [[0] * len(T) for _ in range(len(S))]
    dp[0][0] = int(S[0] == T[0])
    check = [[None] * len(T) for _ in range(len(S))]
    ok = (10, 10)
    check[0][0] = ok if dp[0][0] else (0, 0)
    for i in range(1, len(S)):
        if S[i] == T[0]:
            dp[i][0] = 1
            check[i][0] = ok
        else:
            dp[i][0] = dp[i - 1][0]
            check[i][0] = (-1, 0)
    for j in range(1, len(T)):
        if T[j] == S[0]:
            dp[0][j] = 1
            check[0][j] = ok
        else:
            dp[0][j] = dp[0][j-1]
            check[0][j] = (0, -1)
    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
                check[i][j] = (-1, -1)
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                if dp[i - 1][j] > dp[i][j - 1]:
                    check[i][j] = (-1, 0)
                else:
                    check[i][j] = (0, -1)

    ans = ""
    i = len(S)-1
    j = len(T)-1
    for _ in range(len(S) + len(T)):
        if check[i][j] == ok:
            ans = S[i] + ans
            break
        else:
            if check[i][j] == (-1, -1):
                ans = S[i] + ans
                tmp = i
                i += check[i][j][0]
                j += check[tmp][j][1]
            else:
                tmp = i
                i += check[i][j][0]
                j += check[tmp][j][1]
    
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

a = input()
b = input()
dp = [[0] * (len(b) + 1)  for i in range(len(a) + 1)]

for x in range(len(a)):
	for y in range(len(b)):
		if a[x] == b[y]:
			dp[x + 1][y + 1] = dp[x][y] + 1
		else:
			dp[x + 1][y + 1] = max(dp[x + 1][y], dp[x][y + 1])
		
x, y = len(a) - 1, len(b) - 1
s = ''
while (x >= 0 and y >= 0):
	if a[x] == b[y]:
		s = a[x] + s
		x -= 1
		y -= 1
	elif dp[x][y + 1] > dp[x + 1][y]:
		x -= 1
	else:
		y -= 1
		
print(s)

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

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

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] = 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
str = ''

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:
            str += s[i-1]
            i -= 1
            j -= 1
            
print(str[::-1])

Solution (Python):


s = input()
t = input()

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

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

ans_index = []

for i in range(1, lens+1):
    for j in range(1, lent+1):
        if s[i-1] == t[j-1]:
            candidate = max(dp[i-1][j-1]+1, dp[i-1][j], dp[i][j-1])
            if candidate == dp[i-1][j-1]+1:
                dp[i][j] = dp[i-1][j-1]+1
                continue
            elif candidate == dp[i-1][j]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
        else:
            candidate = max(dp[i-1][j], dp[i][j-1])
            if candidate == dp[i-1][j]:
                dp[i][j] = dp[i-1][j]
                continue
            else:
                dp[i][j] = dp[i][j-1]

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

Solution (Python):
"Template made by : https://codeforces.com/profile/c1729 , github repo : https://github.com/cheran-senthil/PyRival"
from __future__ import division, print_function
import bisect
import math
import itertools
import sys
from atexit import register

if sys.version_info[0] < 3:
    from io import BytesIO as stream
else:
    from io import StringIO as stream


if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip


def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new synchronization setting.

    """
    global input, flush

    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')

        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

def main():
    s=input()
    t=input()
    L=[ [0]*(len(t)+1) for _ in range(len(s)+1) ]
    
    def lcs(s,t):
        n=len(s)
        m=len(t)
        for i in range(0,n+1):
            for j in range(0,m+1):
                if i==0 or j==0:
                    L[i][j]=0
                elif s[i-1]==t[j-1]:
                    L[i][j]=L[i-1][j-1]+1
                else :
                    L[i][j]=max(L[i-1][j],L[i][j-1])
    lcs(s,t)
    ans=[]
    i=len(s)
    j=len(t)
    while L[i][j]!=0:
        if L[i][j]!=L[i-1][j] and L[i][j]!=L[i][j-1]:
            ans.append(s[i-1])
            i-=1
            j-=1
        else :
            if L[i][j]==L[i-1][j]:
                i-=1
                continue
            else :
                j-=1
                continue
    print(''.join(ans[::-1]))
if __name__ == '__main__':
    sync_with_stdio(False)
    main()

Solution (Python):
x = input()
y = input()
lx, ly = len(x), len(y)

length = [[0] * (ly + 1) for _ in range(lx + 1)]

for i_x in range(lx):
    for i_y in range(ly):
        if x[i_x] == y[i_y]:
            length[i_x+1][i_y+1] = length[i_x][i_y] + 1
        else:
            length[i_x+1][i_y+1] = max(length[i_x+1][i_y], length[i_x][i_y+1])

lcs = ''
i_x, i_y = lx, ly
while i_x and i_y:
    if x[i_x-1] == y[i_y-1]:
        lcs += x[i_x-1]
        i_x -= 1
        i_y -= 1
    elif length[i_x][i_y-1] > length[i_x-1][i_y]:
        i_y -= 1
    else:
        i_x -= 1

print(lcs[::-1])