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

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	s = IS()
	t = IS()
	n = len(s)
	m = len(t)
	dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
	for i in range(n):
		for j in range(m):
			if(s[i]==t[j]):
				dp[i+1][j+1] = max(dp[i+1][j],dp[i][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 dp[n][m] == dp[n-1][m]:
	        n -= 1
	    elif dp[n][m] == dp[n][m-1]:
	        m -= 1
	    else:
	        ans += s[n-1]
	        n -= 1
	        m -= 1
	print(ans[::-1])

if __name__ == '__main__':
	main()

Solution (Python):
import math


def main():
    s1 = input()   
    s2 = input()
    
    dp = [[0]*(len(s2)+1) for x in range(len(s1)+1)]
    for x in range(len(s1)):
        dp[x][0] = 0
    for x in range(len(s2)):
        dp[0][x] = 0
    
    for x in range(1,len(s1)+1):
        for y in range(1,len(s2)+1):
            if s1[x-1]==s2[y-1]:
                dp[x][y] = dp[x-1][y-1]+1
            else:
                dp[x][y] = max(dp[x][y-1],dp[x-1][y])
    x = len(s1)
    y = len(s2)
    s = ""
    while x > 0 and y > 0:
        if(s1[x-1]==s2[y-1]):
            s+=s1[x-1]
            x-=1
            y-=1
        elif dp[x-1][y] > dp[x][y-1]:
            x-=1
        else:
            y-=1
    print(s[::-1])
    
main()

Solution (Python):
from itertools import product
from collections import deque
import sys
sys.setrecursionlimit(100000)


def read():
    s = input()
    t = input()
    return s, t


def lcs(s, t):
    S = len(s)
    T = len(t)
    dp = [[0 for j in range(T+1)] for i in range(S+1)]
    for i, j in product(range(S), range(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] = max(dp[i+1][j], dp[i][j])
            dp[i][j+1] = max(dp[i][j+1], dp[i][j])
    maxpos = (0, 0)
    maxv = dp[0][0]
    for i, j in product(range(S), range(T)):
        if maxv < dp[i+1][j+1]:
            maxpos = (i, j)
            maxv = dp[i+1][j+1]
    return maxpos, dp


def retrieve(s, t, i, j, dp):
    x = list()
    while i >= 0 and j >= 0:
        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:
            x.append(s[i])
            i -= 1
            j -= 1
    return ''.join(reversed(x))


def solve(s, t):
    maxpos, dp = lcs(s, t)
    i, j = maxpos
    ans = retrieve(s, t, i, j, dp)
    return ans


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def solve():

    S = input()
    T = input()

    LS = len(S)
    LT = len(T)

    dp = [[0] * (LT + 1) for _ in range(LS + 1)]
    pre = [[None] * (LT + 1) for _ in range(LS + 1)]
    for i in range(LS):
        for j in range(LT):
            now = 0
            if S[i] == T[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
                pre[i+1][j+1] = 1
            else:
                if dp[i + 1][j] < dp[i][j + 1]:
                    dp[i + 1][j + 1] = dp[i][j + 1]
                    pre[i+1][j+1] = 2
                else:
                    dp[i + 1][j + 1] = dp[i + 1][j]
                    pre[i+1][j+1] = 3

    

    
        

    si = LS
    ti = LT
    ans = []

    while not ((si == 0) and (ti == 0)):
        frm = pre[si][ti]
        if frm == 1:
            si -= 1
            ti -= 1
            ans.append(S[si])
        elif frm == 2:
            si -= 1
        elif frm == 3:
            ti -= 1
        elif frm == None:
            break

    return ans[::-1]


ans = solve()
print("".join(ans))

Solution (Python):
input = raw_input
s = input().strip()
t = input().strip()

NS = len(s)
NT = len(t)

dp = [[0] * (NT+2) for i in range(NS+2)]
dp2 = [[""] * (NT+2) for i in range(NS+2)]

for i in range(1,NS+1):
    for j in range(1,NT+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = max(dp[i-1][j-1]+1, dp[i-1][j], dp[i][j-1])
            if dp[i-1][j-1]+1 > dp[i-1][j] and dp[i-1][j-1]+1 > dp[i][j-1]:
                dp2[i][j] = dp2[i-1][j-1] + s[i-1]
            elif dp[i-1][j] > dp[i][j-1]:
                dp2[i][j] = dp2[i-1][j]
            else:
                dp2[i][j] = dp2[i][j-1]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            if dp[i-1][j] > dp[i][j-1]:
                dp2[i][j] = dp2[i-1][j]
            else:
                dp2[i][j] = dp2[i][j-1]
print(dp2[NS][NT])

Solution (Python):
s=input()
t=input()
dp=[[0]*(len(s)+1) for i in range(len(t)+1)]
for i in range(1,len(t)+1):
  for j in range(1,len(s)+1):
    if s[j-1]==t[i-1]:
      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])
ans=[]
a=dp[len(t)][len(s)]
i=len(t)
j=len(s)
while i>0 and j>0:
  if s[j-1]==t[i-1]:
    ans.append(s[j-1])
    i=i-1
    j=j-1
  else:
    if dp[i][j]==dp[i][j-1]:
      j=j-1
    else:
      i=i-1
ans=ans[::-1]
for i in range(len(ans)):
  print(ans[i],end="")
print()

Solution (Python):











def resolve():
    s = str(input())
    t = str(input())


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

        
        

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

        return lcs_str[::-1]

    print(lcs(s, t))


resolve()

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

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

i, j = M, N
lcs = ""
while i>0 and j>0:
    if T[i-1]==S[j-1]:
        lcs += T[i-1]
        i -= 1
        j -= 1
    else:
        if dp[i-1][j]>dp[i][j-1]:
            i -= 1
        else:
            j -= 1
print(lcs[::-1])

Solution (Python):

s=input()
t=input()
ns=len(s)
nt=len(t)
dp=[[0]*(nt+1) for i in range(ns+1)]

for i in range(ns):
    for j in range(nt):
        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,j=ns,nt
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()
S = len(s)
T = len(t)
dp = [[0 for i in range(T+1)] for j in range(S+1)]

for i in range(S):
    for j in range(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 = ""
while S > 0 and T > 0:
    if dp[S][T] == dp[S-1][T]:
        S -= 1
    elif dp[S][T] == dp[S][T-1]:
        T -= 1
    else:
        ans = s[S-1] + ans
        S -= 1
        T -= 1

print(ans)

Solution (Python):
a = input()
b = input()
n, m = len(a), 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 + 1][j], dp[i][j + 1])


c, d = n, m
ans = ""
while c > 0 and d > 0:
    if dp[c - 1][d] == dp[c][d]:
        c -= 1
    elif dp[c][d - 1] == dp[c][d]:
        d -= 1
    else:
        ans = a[c - 1] + ans
        c -= 1
        d -= 1
print(ans)

Solution (Python):
from collections import deque

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


dp = [[0] * (m+1) for _ 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 = deque()
i, j = n, m
while i and j:
    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.appendleft(s[i])

print("".join(ans))

Solution (Python):
def rr(): return input().rstrip()
def rri(): return int(rr())
def rrl(): return list(map(int, rr().split()))
def rrt(): return tuple(map(int, rr().split()))
from collections import defaultdict
def mus(d=lambda: 0): return defaultdict(lambda: defaultdict(d))
def dd0(d=lambda: 0): return defaultdict(d)
def ms(x, y, d=0): return [[0]*y for i in range(x)]
def ar(x, d=0): return [d]*x
def ppm(m, n=0, x=0, y=0): print("\n".join(("\t".join((str(m[j][i]) for j in range(y or n))) for i in range(x or n))))
def ppa(a, n): print("\t".join(map(str, a[0:n])))
def ppl(a=0, x=[1]): x[0]=a or (x[0]+1); print("-"+"- -"*14+"-
def fltn(a): (i for sub in a for i in sub)
def yn(x): return "YES" if x else "NO"
from itertools import accumulate
from itertools import groupby
def grp(x): return ((i, sum(1 for _ in g)) for i, g in groupby(x))
import math


def dpp(a, b=""): print(")

def read():
    
    return (rr(), rr())

def solve(s, t):
    dp = ms(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][j-1], dp[i-1][j])
    tl = dp[len(s)][len(t)]
    

    if tl == 0: return ''
    
    i = len(s); j = len(t)
    ts = []
    while (i > 0) and (j > 0):
        if s[i-1] == t[j-1]:
            ts.append(s[i-1])
            i -= 1; j -= 1;
        else:
            if dp[i-1][j] == dp[i][j]:
                i -= 1
            else:
                j -= 1

    ts = "".join(reversed(ts))

    return ts

if __name__ == "__main__":
    
    test_count = 1
    for _ in range(test_count):
        input_data = read()
        result = solve(*input_data)
        print(result)

Solution (Python):
tmp1 = input()
tmp2 = input()
s = ""
t = ""
if (len(tmp1)<=len(tmp2)):
    s = tmp1
    t = tmp2
else:
    t = tmp1
    s = tmp2

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

ret = ""
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
    elif(dp[i][j] != dp[i-1][j-1]):
        ret = s[i-1] + ret
        i -= 1
        j -= 1

print(ret)

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

Solution (Python):
def lcs(s1,s2):
    dp = [[0 for i in range(1+len(s1))] for j in range(1+len(s2))]
    for i in range(len(s1)):
        for j in range(len(s2)):
            lis = [dp[j][i+1],dp[j+1][i]]
            if s1[i] == s2[j]:
                lis.append(dp[j][i]+1)
            dp[j+1][i+1] = max(lis)
    ans=[]
    i=len(s1)
    j=len(s2)
    while i>0 and j>0:
        if s1[i-1]==s2[j-1]:
            ans.append(s1[i-1])
            i-=1
            j-=1
        elif dp[j][i]==dp[j-1][i]:
            j-=1
        else:
            i-=1
    print(''.join(ans[::-1]))

s=input()
t=input()

lcs(s,t)

Solution (Python):
S = input()
T = input()
dp = [[-1 for i in range(len(S)+1)] for j in range(len(T)+1)]
sub = [["" for i in range(len(S)+1)] for j in range(len(T)+1)]
for a in range(len(S)+1):
	dp[0][a] = 0
for b in range(len(T)+1):
	dp[b][0] = 0
for p in range(1, len(T)+1):
	for q in range(1, len(S)+1):
		if T[p-1] == S[q-1]:
			dp[p][q] = 1 + dp[p-1][q-1]
			sub[p][q] = "c"
		else:
			if dp[p-1][q] > dp[p][q-1]:
				dp[p][q] = dp[p-1][q]
				sub[p][q] = "u"
			else:
				dp[p][q] = dp[p][q-1]
				sub[p][q] = "l"
t = len(T)
s = len(S)
out = ""
while sub[t][s] != "":
	if sub[t][s] == "c":
		out = S[s-1] + out
		t -= 1
		s -= 1
	elif sub[t][s] == "u":
		t -= 1
	else:
		s -= 1
print(out)

Solution (Python):
from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce


def input():
    return sys.stdin.readline().strip()


def iinput():
    return int(input())


def tinput():
    return input().split()


def rinput():
    return map(int, tinput())


def rlinput():
    return list(rinput())


mod = int(1e9)+7


def factors(n):
    return set(reduce(list.__add__,
                      ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))




if __name__ == "__main__":
    a = input()
    b = input()
    n, m = len(a), len(b)
    lcs = [[0 for i in range(n+1)] for j in range(m+1)]


    for i in range(1,m+1):
        for j in range(1,n+1):
            if b[i-1] == a[j-1]:
                lcs[i][j] = 1 + lcs[i-1][j-1]
            else:
                lcs[i][j] = max(lcs[i][j-1],lcs[i-1][j])
    
    s=""
    i=m
    j=n
    
    while i>0 and j>0:
        if b[i-1] == a[j-1]:
            s+=b[i-1]
            i-=1
            j-=1
        elif lcs[i-1][j] > lcs[i][j-1]:
            i-=1
        else:
            j-=1

    print(s[::-1])

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):
        char = s[i-1]
        if char == 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])

answer = ''
i, j = len(s), len(t)
now = dp[i][j]
while i > 0 and j > 0:
    if dp[i-1][j] == now:
        i -= 1
        continue
    if dp[i][j-1] == now:
        j -= 1
        continue
    answer += s[i-1]
    i -= 1
    j -= 1
    now -= 1

print(answer[::-1])

Solution (Python):
s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0 for i in range(m+1)] for j in range(n+1)]
lcs = [[(0,0) for i in range(m+1)] for j in range(n+1)]
for i in range(1,n+1):
  for j in range(1,m+1):
    if dp[i-1][j]>=dp[i][j-1]:
      dp[i][j] = dp[i-1][j]
      lcs[i][j] = (i-1,j)
    else:
      dp[i][j] = dp[i][j-1]
      lcs[i][j] = (i,j-1)
    if s[i-1] == t[j-1] and dp[i-1][j-1]+1>=dp[i][j]:
      dp[i][j] = dp[i-1][j-1]+1
      lcs[i][j] = (i,j)
ans = []
x = dp[n][m]
a = n
b = m
while x:
  if dp[a][b] == dp[a-1][b-1]+1 and dp[a][b] > max(dp[a-1][b],dp[a][b-1]):
    ans.append(s[lcs[a][b][0]-1])
    a -= 1
    b -= 1
    x -= 1
  elif dp[a][b] == dp[a-1][b]:
    a -= 1
  else:
    b -= 1
ans = ans[::-1]
print(*ans,sep="")

Solution (Python):
s = str(input())
t = str(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][j]+1, DP[i+1][j+1])
        else:
            DP[i+1][j+1] = max(DP[i+1][j], DP[i+1][j+1])
            DP[i+1][j+1] = max(DP[i][j+1], DP[i+1][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] + ans
        i -= 1
        j -= 1
print(ans)

Solution (Python):
from copy import deepcopy
s = ['_']
s.extend(list(input()))
t = ['.']
t.extend(list(input()))
N = len(s)
M = len(t)
DP = [[0]*(M+1) for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,M+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])

i = N
j = M
ans = []
while i != 0 and j != 0:
    if DP[i-1][j] < DP[i][j] and DP[i][j-1] < DP[i][j]:
        ans.append(s[i-1])
        i -= 1
        j -= 1
    elif DP[i-1][j] == DP[i][j]:
        i -= 1
    elif DP[i][j-1] == DP[i][j]:
        j -= 1

print(*reversed(ans),sep="")

Solution (Python):
s = input()
t = input()
m, n = len(s), len(t)
dp = [[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 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 = ''
i, j = m, n
while i > 0 and j > 0:
  if dp[i][j] == dp[i-1][j]:
    i -= 1
  elif dp[i][j] == dp[i][j-1]:
    j -= 1
  else:
    i -= 1
    j -= 1
    res = s[i] + res
print(res)

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

print(ans)

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

dp = [[0]*(3001) for j in range(3001)]

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



res = ""
s_len = len(s)
t_len = len(t)
while s_len > 0 and t_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:
        res = s[s_len-1] + res
        s_len -= 1
        t_len -= 1
print(res)

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

"""
dp[s][t]: Sのs文字目までとTのt文字目までの解
"""

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

for s in range(1, len(S)+1):
    for t in range(1, len(T)+1):
        if S[s-1] == T[t-1]:
            dp[s][t] = dp[s-1][t-1] + 1
        else:
            dp[s][t] = max(dp[s-1][t], dp[s][t-1])

result = ""
s = len(S)
t = len(T)
while s > 0 and t > 0:
    if dp[s][t] == dp[s-1][t]:
        s -= 1
    elif dp[s][t] == dp[s][t-1]:
        t -= 1
    elif dp[s][t] == dp[s-1][t-1] + 1:
        result = S[s-1] + result
        s -= 1
        t -= 1
print(result)

Solution (Python):
s=input()
t=input()
ls=len(s)
lt=len(t)
dp=[[0 for i in range(ls)] for i in range(lt)]
a=0
for i in range(ls):
    if t[0]==s[i]:
        a=1
    dp[0][i]=a
a=0
for i in range(lt):
    if s[0]==t[i]:
        a=1
    dp[i][0]=a
for i in range(1,lt):
    for j in range(1,ls):
        if s[j]==t[i]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
ans=[]
x=ls-1
y=lt-1
while x>0 or y>0:
    if x==0:
        y-=1
        if dp[y][0]!=dp[y+1][0]:
            ans.append(t[y+1])
    elif y==0:
        x-=1
        if dp[0][x]!=dp[0][x+1]:
            ans.append(s[x+1])
    elif dp[y][x]==dp[y-1][x]:
        y-=1
    elif dp[y][x]==dp[y][x-1]:
        x-=1
    else:
        x-=1
        y-=1
        ans.append(s[x+1])
if dp[y][x]==1:
    ans.append(s[0])
print(''.join(ans[::-1]))

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

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    

    S = input().rstrip()
    T = input().rstrip()
    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])

    
    res = ''
    while s != 0 and t != 0:
        if dp[s][t] == dp[s-1][t]:
            s -= 1
        elif dp[s][t] == dp[s][t-1]:
            t -= 1
        else:
            s -= 1
            t -= 1
            res = S[s] + res
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
S = input()
T = input()
dp = [[-1 for i in range(len(S)+1)] for j in range(len(T)+1)]
sub = [["" for i in range(len(S)+1)] for j in range(len(T)+1)]
for a in range(len(S)+1):
	dp[0][a] = 0
for b in range(len(T)+1):
	dp[b][0] = 0
for p in range(1, len(T)+1):
	for q in range(1, len(S)+1):
		if T[p-1] == S[q-1]:
			dp[p][q] = 1 + dp[p-1][q-1]
			sub[p][q] = "c"
		else:
			if dp[p-1][q] > dp[p][q-1]:
				dp[p][q] = dp[p-1][q]
				sub[p][q] = "u"
			else:
				dp[p][q] = dp[p][q-1]
				sub[p][q] = "l"
t = len(T)
s = len(S)
out = ""
while sub[t][s] != "":
	if sub[t][s] == "c":
		out = S[s-1] + out
		t -= 1
		s -= 1
	elif sub[t][s] == "u":
		t -= 1
	else:
		s -= 1
print(out)

Solution (Python):
import sys
sys.setrecursionlimit(3000*3000)

A = input()
B = input()




















dp = [[None] * (len(B) + 1) for _ in range(len(A) + 1)]
for a in reversed(range(len(A) + 1)):
    for b in reversed(range(len(B) + 1)):
        if a >= len(A) or b >= len(B):
            dp[a][b] = 0
            continue

        match = A[a] == B[b]
        if match:
            r = dp[a + 1][b + 1] + 1
        else:
            r = max(dp[a + 1][b], dp[a][b + 1])
        dp[a][b] = r





def or_inf(v):
    return float('inf') if v is None else v

def reconst(a=0, b=0):
    if a >= len(A) or b >= len(B):
        return ''

    match = A[a] == B[b]
    if match:
        return reconst(a + 1, b + 1) + A[a]
    else:
        if or_inf(dp[a + 1][b]) >= or_inf(dp[a][b + 1]):
            return reconst(a + 1, b)
        else:
            return reconst(a, b + 1)
print(reconst()[::-1])

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

        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j],dp[i][j+1])




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

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

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



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

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

i = n; j = m

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] + res
    i-=1;j-=1

print(res)

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

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


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

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

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

Solution (Python):
def main():
    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])
    i=len(s)
    j=len(t)
    result=[]
    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
        elif dp[i][j]==dp[i-1][j-1]+1:
            result.append(s[i-1])
            i-=1
            j-=1
    s="".join(result)
    s=s[::-1]
    print(s)
if __name__=="__main__":
    main()

Solution (Python):
def LCS(s,t,restore=False):
    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])
    if restore:
        lcs = []
        stack = [(len(s),len(t))]
        while stack:
            x,y = stack.pop()
            if dp[x][y] == 0:
                break
            if x-1 >= 0 and dp[x][y] == dp[x-1][y]:
                stack.append((x-1,y))
            elif y-1 >= 0 and dp[x][y] == dp[x][y-1]:
                stack.append((x,y-1))
            else:
                lcs.append(s[x-1])
                stack.append((x-1,y-1))
        lcs = ''.join(lcs)[::-1]
        return dp[-1][-1],lcs
    return dp[-1][-1]
  
S = input()
T = input()

print(LCS(S,T,True)[1])

Solution (Python):
s = input() + "!"
t = input() + "@"
len_s = len(s)
len_t = len(t)

dp=[[0 for _ in range(3100)] for _ in range(3100)]



ans = ''
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])

j= len_t - 1
for i in range(len_s)[::-1]:
    while(dp[i][j - 1] == dp[i][j] and j >= 1):
        j -= 1
    if dp[i - 1][j] == dp[i][j]:
        continue
    ans += s[i -1]
print(ans[::-1])

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

A = len(S)
B = len(T)

dp = [[0] * (B+1) for _ in range(A+1)]
    
for i in range(1, A+1):
    for j in range(1, B+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])

lcs_len = dp[A][B]
i = A
j = B
ans = ""
while lcs_len > 0:
    if S[i-1] == T[j-1]:
        ans = S[i-1] + ans
        i -= 1
        j -= 1
        lcs_len -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        i -= 1
        
print(ans)

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

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



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

for i in range(n+1):
  dp[i][0] = 0
  
for j in range(m+1):
  dp[0][j] = 0
  
for i in range(1,n+1):
  for j in range(1,m+1):
    if s[i-1] == t[j-1]:
      dp[i][j] = 1 + dp[i-1][j-1]
    else:
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])
   
def path():
    ans=""
    ls=n;lt=m
    while ls>0 and lt>0:
        if dp[ls][lt]==dp[ls-1][lt]:
            ls-=1
        elif dp[ls][lt]==dp[ls][lt-1]:
            lt-=1
        else:
            ans=s[ls-1]+ans
            ls-=1
            lt-=1
 
    print(ans)
    
path()

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

x = input().rstrip()
y = input().rstrip()

lx = len(x)
ly = len(y)
c1 = [[0 for _ in range(lx+1)] for _ in range(ly+1)]
for i in range(1,ly+1):
    e1 = y[i-1]
    for j in range(1,lx+1):
        if (e1 == x[j-1]):
            c1[i][j] = c1[i-1][j-1] + 1
        else:
            c1[i][j] = max(c1[i-1][j],c1[i][j-1])
i = ly
j = lx
s = ''
m = c1[i][j]
di = -1
dj = 0
while c1[i][j] > 0:
    if c1[i][j] > c1[i-1][j] and c1[i][j] > c1[i][j-1] and c1[i][j] > c1[i-1][j-1]:
        s = x[j-1] + s
        m = m - 1
        i = i - 1
        j = j - 1
    else:
        ni = i + di
        nj = j + dj
        if c1[ni][nj] == m:
            i = ni
            j = nj
        else:
            di, dj = dj, di

print (s)

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

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

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

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

i = ls
j = lt
ans = ""
while i>=1 and j>=1:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
        continue
    if dp[i][j] == dp[i-1][j]:
        i -= 1
        continue
    ans = s[i-1] + ans
    i -= 1
    j -= 1
print(ans)

Solution (Python):
S = input()
T = input()
dp = [[ 0] * (len(S) + 1 ) for _ in range(len(T) + 1)]
ma = 0
for i in range(len(dp)-1):
    for j in range(len(dp[0])-1):
        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) - 1
j = len(S) - 1 
ans = ""
while i >=0 and j >= 0:
    if dp[i][j+1] == dp[i + 1][j + 1]:
        i-=1
    elif dp[i + 1][j] == dp[i + 1][j + 1]:
        j-=1
    else:
        
        ans = S[j] + ans
        i-=1
        j-=1
print(ans)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

s = input()
t = input()

MAXV = 3100
dp = [[0] * MAXV for _ in range(MAXV)]

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

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