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):
from sys import stdin, stdout
from collections import deque, defaultdict
import math as m

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	s = rll()[0]
	t = rll()[0]
	m, n = len(s), len(t)
	dp = [[0 for __ in range(n)] for _ in range(m)]

	

	def pprint(M):
		for row in M:
			print(row)
		print("~~~")
	
	dp[0][0] = 1 if s[0] == t[0] else 0
	for c in range(1, n):
		dp[0][c] = max(dp[0][c-1], 1 if s[0] == t[c] else 0)
	for r in range(1, m):
		dp[r][0] = max(dp[r-1][0], 1 if s[r] == t[0] else 0)

	for r in range(1, m):
		for c in range(1, n):
			dp[r][c] = max(dp[r][c], dp[r-1][c], dp[r][c-1])
			if s[r] == t[c]:
				dp[r][c] = max(dp[r][c], 1 + dp[r-1][c-1])

	ans = deque()
	i, j = m - 1, n - 1
	while i >= 0 and j >= 0:
		if s[i] == t[j]:
			ans.appendleft(s[i])
			i -= 1
			j -= 1
		else:
			up, left = NINF, NINF
			if i - 1 >= 0:
				up = dp[i-1][j]
			if j - 1 >= 0:
				left = dp[i][j-1]
			if up >= left:
				i -= 1
			else:
				j -= 1
	print("".join(x for x in ans))
	stdout.close()

if __name__ == "__main__":
	main()

Solution (Python):
s = input()
t = input()
lenS = len(s)
lenT = len(t)
dp = []
for i in range(lenS+1):
    dp.append([0]*(lenT+1))
for i in range(1,lenS+1):
    for j in range(1,lenT+1):
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
ans=""
i=lenS
j=lenT
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):
import numpy as np
S = np.array([ord(i)-97 for i in input()], dtype=int)
T = np.array([ord(i)-97 for i in input()], dtype=int)
Ns = len(S)
Nt = len(T)
equal = np.equal.outer(S, T).astype(int)
 
dp = [np.zeros(Nt + 1, dtype=int)]
for i in range(Ns):
    x = dp[-1].copy()
    newDP = x.copy()
    newDP[1:] = np.maximum(x[:-1] + equal[i], newDP[1:])
    np.maximum.accumulate(newDP, out=newDP)
    dp.append(newDP)
 
 
ans = ""
i, j = Ns, Nt
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans += chr(S[i-1]+97)
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1
 
print(ans[::-1])

Solution (Python):
s = input()
t = input()
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
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] = max(dp[i-1][j-1]+1, dp[i][j])
        else:
            dp[i][j]= max(dp[i-1][j], dp[i][j-1])

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

Solution (Python):
def lcs(s, t):
    n = len(s)
    m = 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+1][j], dp[i][j+1])
    res = ""
    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
            
            res = s[n] + res
    return res


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

Solution (Python):
s=input()
t=input()
l1=len(s)
l2=len(t)
dp=[[-1]*(l2+1) for i in range(l1+1)]   

for i in range(l1+1):
    for j in range(l2+1):
        if i==0 or j==0:
            dp[i][j]=0
            
        elif s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
            

size=dp[l1][l2]
i,j=l1,l2
ans=[0]*size
while i>0 and j>0:
    if s[i-1]==t[j-1]:
        ans[size-1]=(s[i-1])
        i-=1
        j-=1
        size-=1
    elif dp[i-1][j]>dp[i][j-1]:
        i-=1
    else:
        j-=1
        
    
print(''.join(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
        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)
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):




s1 = input()
s2 = input()

table = [[0 for _ in range(len(s1))] for _ in range(len(s2))]


f = 0
for i in range(len(s2)):
    if f or s2[i] == s1[0]:
        table[i][0] = 1
        f = 1


f = 0
for i in range(len(s1)):
    if f or s2[0] == s1[i]:
        table[0][i] = 1
        f = 1


for i in range(1, len(s2)):
    for j in range(1, len(s1)):
        
        if s2[i] == s1[j]:
            table[i][j] += table[i-1][j-1]+1
        else:
            if i == 0 or j == 0:
                continue
            else:
                table[i][j] = max(table[i-1][j], table[i][j-1])





lcs_str = ""
i, j = len(s2)-1, len(s1)-1

while i >= 0 and j >= 0:
    
    if s2[i] == s1[j]:
        
        lcs_str += s2[i] 
        i -= 1
        j -= 1
    else:
        if j == 0:
            i -= 1
        elif i == 0:
            j -= 1
        else:
            if table[i-1][j] > table[i][j-1]:
                i -= 1
            else:
                j -= 1
print(lcs_str[::-1])

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    s=input()
    len_s=len(s)
    t=input()
    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-1][j],dp[i][j-1])
    len_ans=dp[len_s][len_t]
    i,j=len_s,len_t
    ans=""
    while len_ans:
        if s[i-1]==t[j-1]:
            ans+=s[i-1]
            i-=1
            j-=1
            len_ans-=1
        elif dp[i][j]==dp[i-1][j]:
            i-=1
        else:
            j-=1
    print(ans[::-1])
if __name__=='__main__':
    main()

Solution (Python):
s,t=input(),input()
S,T=len(s),len(t)
dp=[[0]*(T+1) for _ in range(S+1)]
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])

i,j=S,T
ans=''
while min(i,j)>0:
        if dp[i][j]==dp[i][j-1]:
            j-=1
        elif dp[i][j]==dp[i-1][j]:
            i-=1
        else:
            ans+=s[i-1]
            i-=1 ; j-=1
print(ans[::-1])

Solution (Python):
from collections import deque
s1=input()
s2=input()
n=len(s1)
m=len(s2)
dp=[[0]*(m+1) for i in range(n+1)]
for i in range(n+1):
    for j in range(m+1):
        if(i==0 or j==0):
            dp[i][j]=0
        else:
            if(s1[i-1]==s2[j-1]):
                dp[i][j]=1+dp[i-1][j-1]
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
x=n
y=m
ans=""
while x>0 and y>0:
    if(s1[x-1]==s2[y-1]):
        ans+=s1[x-1]
        x-=1
        y-=1
    else:
        if(dp[x-1][y]>dp[x][y-1]):
            x-=1
        else:
            y-=1
            
'''
if(x==0):
    for i in range(y,-1,-1):
        if(s1[x]==s2[i]):
            ans+=s1[x]
            break
elif(y==0):
    for i in range(x,0,-1):
        if(s1[i]==s2[y]):
            ans+=s1[i]
            break
'''
'''
aabaaa
ababba
'''
print(ans[::-1])

Solution (Python):
s1 = list(input())
s2 = list(input())
n = len(s1)
m = len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
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 s1[i-1]==s2[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=n,m
while i> 0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        res.append(s1[i-1])
        i-=1
        j-=1
print("".join(res[::-1]))

Solution (Python):
import sys
sys.setrecursionlimit(1000000) 

def main():
    input = sys.stdin.readline  
    S = input().rstrip()
    T = input().rstrip()

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

    
    for i, s in enumerate(S, 1):
        for j, t in enumerate(T, 1):
            
            if s == t:
                
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)
            
            dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1])

    
    i, j = len(S), 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)

if __name__ == '__main__':
    main()

Solution (Python):
s1=input()
s2=input()
a=[[0]*(len(s2)+1) for i in range(len(s1)+1)]
res=''
for i in range(1,len(s1)+1):
  for j in range(1,len(s2)+1):
    if s1[i-1] == s2[j-1]:
      a[i][j] = a[i-1][j-1] + 1
    elif a[i-1][j] >= a[i][j-1]:
      a[i][j] = a[i-1][j]
    else:
      a[i][j] = a[i][j-1]
i=len(s1)
j=len(s2)
while i>0 and j>0:
  if a[i][j] == a[i-1][j]:
    i -= 1
  elif a[i][j] == a[i][j-1]:
    j -= 1
  else:
    res = s1[i-1] + res
    i -= 1
    j -= 1   
print(res)

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

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

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

nums = len(s)
numt = len(t)
d = dp[nums][numt]
ans = ""

while True:
    if d == 0:
        break
    if dp[nums][numt - 1] == d:
        numt -= 1
    elif dp[nums - 1][numt] == d:
        nums -= 1
    else:
        ans += s[nums - 1]
        nums -= 1
        numt -= 1
        d -= 1

print(ans[::-1])

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

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

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

nums = len(s)
numt = len(t)
d = dp[nums][numt]
ans = ""

while True:
    if d == 0:
        break
    if dp[nums - 1][numt] == d:
        nums -= 1
    elif dp[nums][numt - 1] == d:
        numt -= 1
    else:
        ans += s[nums - 1]
        nums -= 1
        numt -= 1
        d -= 1

print(ans[::-1])

Solution (Python):
def main():
    import sys
    input=sys.stdin.buffer.readline
    s=b' '+input()[:-1]
    t=b' '+input()[:-1]
    n,m=len(s),len(t)
    dp=[[0]*m for _ in range(n)]
    b=dp[0]
    for i,x in enumerate(s[1:],1):
        dpi=dp[i]
        for j,y in enumerate(t[1:],1):
            if x==y:
                dpi[j]=b[j-1]+1
            else:
                v,w=b[j],dpi[j-1]
                dpi[j]=v if v>w else w
        b=dpi
    ans=[]
    i,j=n-1,m-1
    while dp[i][j]:
        if dp[i][j]==dp[i-1][j]:
            i-=1
        elif dp[i][j]==dp[i][j-1]:
            j-=1
        else:
            ans.append(s[i])
            i-=1
            j-=1
    print(''.join(map(chr,ans))[::-1])
main()

Solution (Python):
s1 = list(input())
s2 = list(input())
n = len(s1)
m = len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1, m+1):
        if s1[i-1] == s2[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, j = n, 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.append(s1[i-1])
        i -= 1
        j -= 1
print(''.join(res[::-1]))

Solution (Python):
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    s = gete()
    t = gete()
    ans = ""

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

    for i, si in enumerate(s):
        for j, tj in enumerate(t):
            if si == tj:
                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, j = len(s), len(t)

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

    print(ans_r[::-1])


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    s = input()
    t = input()

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

    
    for i1 in range(1, s_len + 1):
        for i2 in range(1, t_len + 1):
            if s[i1 - 1] == t[i2 - 1]:
                dp[i1][i2] = dp[i1-1][i2-1] + 1
            else:
                dp[i1][i2] = max(dp[i1-1][i2], dp[i1][i2-1])
    
    
    
    
    j1 = s_len
    j2 = t_len
    r = ""
    while j1 > 0 and j2 > 0:
        
        if s[j1-1] == t[j2-1]:
            r += s[j1-1]
            j1 -= 1
            j2 -= 1
        elif dp[j1 - 1][j2] == dp[j1][j2]:
            j1 -= 1
        else:
            j2 -= 1
    print(r[::-1])


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
s = np.array(list(input()))
t = np.array(list(input()))
n = len(s)
m = len(t)
match = s.reshape(-1,1) == t.reshape(1,-1)
lcs = np.zeros((n+1, m+1), dtype='int32')
for i in range(n):
    lcs[i+1,1:] = np.fmax(lcs[i,:-1]+match[i],lcs[i,1:])
    lcs[i+1] = np.maximum.accumulate(lcs[i+1])
l = []
while n > 0 and m > 0:
    if lcs[n, m] == lcs[n-1, m]:
        n-=1
    elif lcs[n, m] == lcs[n, m-1]:
        m-=1
    else:
        l.append(s[n-1])
        n-=1
        m-=1
print(''.join(l[::-1]))

Solution (Python):
s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for x in range(n+1)] for y 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]=1+dp[i-1][j-1]
        else:
            temp=max(dp[i-1][j],dp[i][j-1])
            dp[i][j]=temp
i,j=m,n
ans=''
while (i>0 and j>0):
    if(s[j-1]==t[i-1]):
        ans+=s[j-1]
        i-=1
        j-=1
    else:
        if(dp[i-1][j]>dp[i][j-1]):
            i-=1
        else:
            j-=1
print(ans[::-1])

Solution (Python):
s,t='0'+input(),'0'+input()
ns,nt=len(s)+1,len(t)+1
dp=[[0 for i in range(nt)] for i in range(ns)]
for i in range(1,ns):
	for j in range(1,nt):
		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,j=ns-1,nt-1
ans=''
while i>0 or j>0:
	if dp[i][j]==dp[i][j-1]:j-=1
	elif dp[i][j]==dp[i-1][j]:i-=1
	else:
		ans=s[i-1]+ans
		i-=1;j-=1
print(ans[1:])

Solution (Python):
import numpy as np


def main():
    S = np.array(list(input()))
    LS = len(S)
    T = np.array(list(input()))
    LT = len(T)
    
    dp = np.zeros((LS + 1, LT + 1))
    match = S.reshape(-1, 1) == T.reshape(1, -1)
    for s in range(LS):
        dp[s + 1, 1:] = np.fmax(dp[s, :(-1)] + match[s], dp[s, 1:])
        dp[s + 1] = np.maximum.accumulate(dp[s + 1])
    
    s, t = LS, LT
    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)


if __name__ == '__main__':
    main()

Solution (Python):


"""
Created on Mon May 11 20:44:38 2020

@author: adarsh
"""


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

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):
    S = s[i]
    for j in range(t_len):
        T = t[j]
        ni = i + 1
        nj = j + 1
        if S == T:
            dp[ni][nj] = max(dp[ni][nj], dp[i][j] + 1, dp[i][nj], dp[ni][j])
        else:
            dp[ni][nj] = max(dp[ni][nj], dp[i][nj], dp[ni][j])

nagasa = dp[s_len][t_len]

a = s_len
b = t_len
ans = []
while nagasa > 0:
    if dp[a][b] == nagasa:
        a -= 1
    elif dp[a + 1][b] == nagasa:
        b -= 1
    else:
        ans.append(s[a])
        nagasa -= 1
ans = ans[::-1]
print(*ans, sep="")

Solution (Python):


def main():
    s = input()
    t = input()
    n, m = len(s), len(t)
    LCS = [[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]:
                LCS[i][j] = LCS[i-1][j-1] + 1
            else:
                LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
    ans = ""
    i, j = n, m
    while i > 0 and j > 0:
        if s[i-1] == t[j-1]:
            ans += s[i-1]
            i -= 1
            j -= 1
        elif LCS[i][j-1] > LCS[i-1][j]:
            j -= 1
        else:
            i -= 1
    print(ans[::-1])


if __name__ == "__main__":
    main()

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

    S = list(input().rsplit()[0])
    T = list(input().rsplit()[0])

    NS = len(S)
    NT = len(T)

    
    dp = [[0]*(NT+1) for _ in range(NS+1)]

    for i in range(NS):
        for j in range(NT):
            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 = NS
    j = NT
    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:
            ans = S[i-1]+ans
            j -= 1
            i -= 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

t = np.array(list(input()), dtype='U1')
s = np.array(list(input()), dtype='U1')

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

eq = s[:, None] == t[None, :]
dp = [np.zeros(lt + 1, dtype=np.int16)]


for i in range(ls):
    prev = dp[-1].copy()
    np.maximum(prev[1:], prev[:-1] + eq[i], out=prev[1:])
    np.maximum.accumulate(prev, out=prev)
    dp.append(prev)




res = ''
i, j = ls, lt
while i > 0 and j > 0:
    if eq[i - 1][j - 1]:
        res += s[i - 1]
        i, j = i - 1, j - 1
        continue

    if dp[i - 1][j] > dp[i][j - 1]:
        i -= 1
    else:
        j -= 1

print(res[::-1])

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

hassame = False
for i, s_ in enumerate(s):
    if hassame or s_ == t[0]: dp[i+1][1]=1; hassame=True
hassame = False
for i, t_ in enumerate(t):
    if hassame or t_ == s[0]: dp[1][i+1]=1; hassame=True

lcs = 0
for i, s_ in enumerate(s):
    if i==0: continue
    for j, t_ in enumerate(t):
        if j==0: continue
        if s_!=t_:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
        else:
            dp[i+1][j+1] = dp[i][j]+1
        lcs = max(lcs, dp[i+1][j+1])

ans = ''
i, j = len(s), len(t)
while 0<i and 0<j:
        if s[i-1] == t[j-1]: ans+=s[i-1]; i-=1; j-=1
        else:
            if dp[i-1][j] > dp[i][j-1]: i-=1
            else: j-=1
print(ans[::-1])


for i in range(len(s)):
    dp+=s[i]

Solution (Python):
s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0] * 3100 for _ in range(3100)]
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 + 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 = n, m
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        ans = s[i - 1] + ans
        i -= 1
        j -= 1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    S = input()
    T = input()
    m = len(S)
    n = len(T)
    dp = [[-INF] * (n + 1) for _ in range(m + 1)]
    prev = [[(-1, -1)] * (n + 1) for _ in range(m + 1)]

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

    for i in range(m):
        for j in range(n):
            if S[i] == T[j]:
                if dp[i + 1][j + 1] < dp[i][j] + 1:
                    dp[i + 1][j + 1] = dp[i][j] + 1
                    prev[i + 1][j + 1] = (i, j)
            else:
                if dp[i + 1][j + 1] < dp[i + 1][j]:
                    dp[i + 1][j + 1] = dp[i + 1][j]
                    prev[i + 1][j + 1] = (i + 1, j)
                if dp[i + 1][j + 1] < dp[i][j + 1]:
                    dp[i + 1][j + 1] = dp[i][j + 1]
                    prev[i + 1][j + 1] = (i, j + 1)

    i, j = m, n
    res = []
    cnt = 0
    while 1:
        pi, pj = prev[i][j]
        if (pi, pj) == (-1, -1):
            break
        if i - pi == 1 and j - pj == 1:
            res.append(S[pi])
        i, j = pi, pj

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

Solution (Python):
from collections import deque

s = input()
t = input()
ls = len(s)
lt = len(t)
DP_len = [[0] * (lt + 1) for i in range(ls + 1)]
Prev =[[0] * (lt + 1) for i in range(ls + 1)]
for i in range(1, ls + 1):
    for j in range(1, lt + 1):
        if s[i - 1] == t[j - 1]:
            if max(DP_len[i - 1][j - 1] + 1, DP_len[i][j - 1], DP_len[i - 1][j]) == DP_len[i-1][j-1] + 1:
                DP_len[i][j] = DP_len[i-1][j-1] + 1
                Prev[i][j] = (i-1, j-1)
            else:
                if DP_len[i][j - 1] >= DP_len[i - 1][j]:
                    DP_len[i][j] = DP_len[i][j - 1]
                    Prev[i][j] = (i, j - 1)
                else:
                    DP_len[i][j] = DP_len[i - 1][j]
                    Prev[i][j] = (i - 1, j)

        else:
            if DP_len[i][j - 1] >= DP_len[i - 1][j]:
                DP_len[i][j] = DP_len[i][j - 1]
                Prev[i][j] = (i, j-1)
            else:
                DP_len[i][j] = DP_len[i - 1][j]
                Prev[i][j] = (i - 1, j)

x = ls
y = lt
ans = ''
while True:
    if x == 0 or y == 0:
        break
    nx, ny = Prev[x][y]
    if (nx != x) and (ny != y):
        ans = s[x-1] + ans
    x = nx
    y = ny
print(ans)

Solution (Python):
s=str(input())
t=str(input())
len_s=len(s)
len_t=len(t)
ans=""
dp=[[0 for i in range(len_t+1)] for j in range(len_s+1)]
for i in range(len_s):
    for j in range(len_t):
        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])

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

Solution (Python):
S = input()
T = input()
dp = [[0 for i in range(len(T)+1)] for j in range(len(S)+1)]
for i in range(1,len(S)+1):
    for j in range(1,len(T)+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]) 

length = dp[len(S)][len(T)]
LCS = [0]*length
i = len(S)
j = len(T)
while i > 0 and j > 0: 
    if S[i-1] == T[j-1]: 
        LCS[length-1] = S[i-1]
        i-=1
        j-=1
        length-=1
    elif dp[i-1][j] > dp[i][j-1]: 
        i-=1
    else: 
        j-=1
print("".join(LCS))

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

"""
dp[i][j] = 長さ
i : sのi文字目まで見た状態
j : tのj文字目まで見た状態

遷移
dp[i+1][j+1] = max(dp[i-1][j-1],dp[i][j])
if s[i] == t[j]:
    dp[i+1][j+1] = max(dp[i-1][j-1]+1,dp[i][j])
dp[i][j+1] = max(dp[i][j+1],dp[i][j])
dp[i+1][j] = max(dp[i+1][j],dp[i][j])
"""

dp = [[0]*3001 for i in range(3001)]
res = ""
for i in range(len(s)):
    for j in range(len(t)):
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j+1])
        dp[i+1][j+1] = max(dp[i+1][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)

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)

Solution (Python):
s=input()
t=input()
n1,n2=len(s),len(t)
dp=[[0]*(n1+1) for i in range(n2+1)]
st=''
for i in range(1,n2+1):
    for j in range(1,n1+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])
while i>0 and j>0:
    if t[i-1]==s[j-1]:
        st=s[j-1]+st
        i-=1
        j-=1
    elif dp[i][j-1]>dp[i-1][j]:
        j-=1
    else:
        i-=1
print(st)

Solution (Python):
s = [""]+list(input())
t = [""]+list(input())
dp = [[0 for x in range(len(s))] for x in range(len(t))]
for y in range(1,len(t)):
    for x in range(1,len(s)):
        if(t[y] == s[x]):
            dp[y][x] = dp[y-1][x-1]+1
        else:
            dp[y][x] = max(dp[y-1][x],dp[y][x-1])
y,x = len(t)-1,len(s)-1
ans = []
while(dp[y][x] > 0):
    if(dp[y][x] == dp[y-1][x]):
        y -= 1
    elif(dp[y][x] == dp[y][x-1]):
        x -= 1
    else:
        ans.append(s[x])
        y -= 1
        x -= 1
ans.reverse()
print("".join(ans))

Solution (Python):
s=input()
t=input()
a=len(s)
b=len(t)
n_list=  ['' for i in range(a)]
b_list=['' for j in range(b)]
for i in range(b) :
  if s[0] in t[:i+1] :
    b_list[i]=s[0]
for i in range(a) :
  if t[0] in s[:i+1] :
    n_list[i]=t[0]

import copy
for i in range(1,b) :
  n_list1=copy.copy(n_list)
  n_list[0]=b_list[i]
  for j in range(1,a) :

    if len(n_list1[j])>len(n_list[j]) :
      n_list[j]=n_list1[j]
    if len(n_list[j-1])>len(n_list[j]) :
      n_list[j]=n_list[j-1]
    if t[i]==s[j] and len(n_list1[j-1])+1>len(n_list[j])  :
      n_list[j] = n_list1[j - 1]+t[i]

print(n_list[-1])

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

s = input()
t = input()

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

for i in range(1,len(t)+1):
    for j in range(1,len(s)+1):
        dp[i][j] = max(dp[i][j-1],dp[i-1][j] ,dp[i-1][j-1] + (s[j-1]==t[i-1]))
i = len(t)
j = len(s)
x = dp[i][j]
ans = ''
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:
        ans = ''.join([s[j-1],ans])
        i -= 1
        j -= 1
print(ans)

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

ls, lt = len(s), len(t)
dp = [[0] * (lt + 1) for _ in range(ls + 1)]
dp[0][0], dp[1][0], dp[0][1] = 0, 0, 0
for i in range(ls):
    for j in range(lt):
        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][j] + 1, dp[i + 1][j + 1])

ans = []
tmp_i, tmp_j = ls, lt
while tmp_i * tmp_j > 0:
    if dp[tmp_i][tmp_j] == dp[tmp_i - 1][tmp_j]:
        tmp_i -= 1
    elif dp[tmp_i][tmp_j] == dp[tmp_i][tmp_j - 1]:
        tmp_j -= 1
    else:
        tmp_i, tmp_j = tmp_i - 1, tmp_j - 1
        ans.append(s[tmp_i])
print(''.join(ans[::-1]))

Solution (Python):
s, t = str(input()), str(input())
ls, lt = len(s), len(t)

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

ans = []
tmp_i, tmp_j, cnt = ls, lt, dp[ls][lt]
while tmp_i * tmp_j > 0:
    if dp[tmp_i][tmp_j] == dp[tmp_i - 1][tmp_j]:
        tmp_i -= 1
    elif dp[tmp_i][tmp_j] == dp[tmp_i][tmp_j - 1]:
        tmp_j -= 1
    else:
        tmp_i, tmp_j = tmp_i - 1, tmp_j - 1
        ans.append(s[tmp_i])
print(''.join(ans[::-1]))

Solution (Python):
import numpy as np
def resolve():
    s = np.array(list(input()))
    t = np.array(list(input()))

    dp = np.zeros([len(s) + 1, len(t) + 1], dtype=np.int64)

    match = s.reshape(-1, 1) == t.reshape(1, -1)

    for i in range(len(s)):
        dp[i + 1][1:] = np.maximum(dp[i][:-1] + match[i], dp[i][1:])
        dp[i + 1] = np.maximum.accumulate(dp[i + 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
        elif dp[i][j] == dp[i - 1][j - 1] + 1:
            res = s[i - 1] + res
            i -= 1
            j -= 1

    print(res)
    
resolve()

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

    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
        elif dp[i][j] == dp[i - 1][j - 1] + 1:
            res = s[i - 1] + res
            i -= 1
            j -= 1

    print(res)
resolve()