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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

s = readline().rstrip().decode()
t = readline().rstrip().decode()
s_size = len(s)
t_size = len(t)
dp = [[0] * (t_size + 1) for _ in range(s_size + 1)]
ans = ''
for i in range(s_size):
    for j in range(t_size):
        if s[i] == t[j]:
            if dp[i + 1][j + 1] < dp[i][j] + 1:
                dp[i + 1][j + 1] = dp[i][j] + 1
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1])
while s_size > 0 and t_size > 0:
    if dp[s_size][t_size] == dp[s_size - 1][t_size]:
        s_size -= 1
    elif dp[s_size][t_size] == dp[s_size][t_size - 1]:
        t_size -= 1
    else:
        ans = s[s_size - 1] + ans
        s_size -= 1
        t_size -= 1
print(ans)

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

def solve(S,T):
    
    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+1][j],dp[i][j+1])
    ans = ''
    i,j = s,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
    return ans
print(solve(S,T))

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

            
if __name__ == '__main__':
    solve()

Solution (Python):


from pprint import pprint
from collections import deque, defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
inf = float("inf")

s = input()
t = input()


len_s, len_t = len(s), len(t)
max_len = max(len_s, len_t)
dp = [[0 for j in range(max_len + 1)] for i in range(max_len + 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])




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

print(res)

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


X = input()
Y = input()
x = len(X)
y = len(Y)

dp = [[0 for _ in range(y + 1)] for _ in range(x + 1)]
for i in range(x):
    for j in range(y):
        if X[i] == Y[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])



ans = ''
while x > 0 and y > 0:
    if dp[x][y] == dp[x][y - 1]:
        y -= 1
    elif dp[x][y] == dp[x - 1][y]:
        x -= 1
    else:
        ans += X[x - 1]
        x -= 1
        y -= 1

print(ans[::-1])

Solution (Python):
import numpy as np
s=np.array(list(input()))
t=np.array(list(input()))
is_eq=np.array(s[:,None]==t[None,])


ns=len(s)
nt=len(t)
dp=np.zeros((ns+1,nt+1),np.int64)



for i in range(ns): 
    dp[i+1][1:]=np.maximum(dp[i][:-1]+is_eq[i],dp[i][1:])
    dp[i+1]=np.maximum.accumulate(dp[i+1])
i=ns
j=nt
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.append(s[i-1])
            i-=1
            j-=1
a=''
for _ in range(len(ans)):
      a+=ans.pop()
print(a)

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

    """
    dp[i][j] := s[1] ... s[i] と t[1] ... t[j] に対するLCSの長さ
    
    s[i+1] == t[i+1]のとき、dp[i+1][j+1]は dp[i][j]+1, dp[i+1][j], dp[i][j+1]のいずれか  
    dp[i+1][j+1] = max(dp[i][j] + 1, dp[i+1][j], dp[i][j+1])

    それ以外の時
    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    """

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

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

    ans = ""
    x = len(s)
    y = len(t)
    while x >= 1 and y >= 1:
        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 = s[x] + ans

    print(ans)


if __name__ == "__main__":
    main()

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

ls=len(S)
lt=len(T)


DP=[[0]*(lt+1) for _ 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]:
            DP[i][j]=max(DP[i-1][j-1]+1,DP[i][j-1],DP[i-1][j])
        else:
            DP[i][j]=max(DP[i][j-1],DP[i-1][j])

lf=DP[ls][lt]

res=''
u=ls
v=lt
while u>0 and v>0:
    if DP[u][v]==DP[u-1][v]:
        u-=1
    elif DP[u][v]==DP[u][v-1]:
        v-=1
    else:
        res=S[u-1]+res
        u-=1
        v-=1

print(res)

Solution (Python):
s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
def al(str):
    return alphabetlist.index(str)+1

dp=[[0 for i in range(0,M+1)] for i in range(0,N+1)]

for i in range(0,N):
    for j in range(0,M):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            if dp[i+1][j]>dp[i][j+1]:
                dp[i+1][j+1]=dp[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]

ans=[]
i=N
j=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.append(s[i-1])
        i-=1
        j-=1

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

Solution (Python):
def solve():
    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] = 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)
if __name__ == '__main__':
    solve()

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

inf = pow(10, 4)
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
key = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)+1):
  for j in range(len(t)+1):
    if i == 0 and j == 0:
      continue
    if i == 0:
      dp[i][j] = dp[i][j-1]
      continue
    if j == 0:
      dp[i][j] = dp[i-1][j]
      continue
    if s[i-1] == t[j-1]:
      dp[i][j] = dp[i-1][j-1] + 1
      key[i][j] = (i-1)*inf+(j-1)
    else:
      if dp[i-1][j] > dp[i][j-1]:
        dp[i][j] = dp[i-1][j]
        key[i][j] = key[i-1][j]
      else:
        dp[i][j] = dp[i][j-1]
        key[i][j] = key[i][j-1]

ans = []
i, j = key[len(s)][len(t)]//inf, key[len(s)][len(t)]%inf
while True:
  if s[i] == t[j]:
    ans.append(s[i])
  if i == 0 or j == 0:
    break
  i, j = key[i][j]//inf, key[i][j]%inf

ans.reverse()
print("".join(ans))

Solution (Python):
import sys
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 li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]






S = input()
T = input()



ls, lt = len(S), len(T)
dp = dp2(0, ls+1, lt+1)

    

for i in range(lt):
    for j in range(ls):
        dp[i][j+1] = max(dp[i][j], dp[i][j+1])
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])
        if S[j] == T[i]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

'''

dp = dp2(0, ls+1, lt+1)
for i in range(1, lt+1):
    for j in range(1, ls+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 = lt, ls
ans = ''

while dp[i][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[j-1]
        i -= 1
        j -= 1

print(ans[::-1])

Solution (Python):
import sys
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 li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]






S = input()
T = input()



ls, lt = len(S), len(T)
dp = dp2(0, ls+1, lt+1)

    

for i in range(1, lt+1):
    for j in range(1, ls+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 = lt, ls
ans = ''

while dp[i][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[j-1]
        i -= 1
        j -= 1

print(ans[::-1])

Solution (Python):
import sys
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 li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]






S = input()
T = input()



ls, lt = len(S), len(T)
dp = dp2(0, ls+1, lt+1)

    

for i in range(lt+1):
    for j in range(ls+1):
        if (i < lt and j < ls) and S[j] == T[i]:
            dp[i+1][j+1] = dp[i][j] + 1
        if j < ls:
            dp[i][j+1] = max(dp[i][j], dp[i][j+1])
        if i < lt:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j])
if not dp[lt][ls]:
    dp[lt][ls] = max(dp[lt-1][ls], dp[lt][ls-1])




i, j = lt, ls
ans = ''

while dp[i][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[j-1]
        i -= 1
        j -= 1

print(ans[::-1])

Solution (Python):
a=str(input())
b=str(input())
dp=[[0 for i in range(len(a)+1)] for j in range(len(b)+1)]
ret=[]
for i in range(1,len(b)+1):
    for j in range(1,len(a)+1):
        if b[i-1]==a[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 i!=0 and j!=0:
    if dp[i][j]!=dp[i-1][j] and dp[i][j]!=dp[i][j-1]:
        ret.append(a[j-1])
        i-=1
        j-=1
    else:
        if dp[i][j]==dp[i-1][j]:
            i-=1
        else:
            j-=1

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

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

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

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

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

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

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

for t in range(1, t_len + 1):
    for s in range(1, s_len + 1):
        ans_array[t][s] = max(ans_array[t - 1][s], ans_array[t][s - 1])
        if T[t - 1] == S[s - 1]:
            ans_array[t][s] = ans_array[t - 1][s - 1] + 1


















ans_len = ans_array[-1][-1]
ans = [""] * ans_len
s_last = s_len
t_last = t_len
for i in range(ans_len - 1, -1, -1):
    s_next = 0
    t_next = 0
    for s in range(s_last, 0, -1):
        if ans_array[t_last][s] != ans_array[t_last][s - 1]:
            s_next = s
            break
    s_last = s_next
    for t in range(t_last, 0, -1):
        if ans_array[t][s_last] != ans_array[t - 1][s_last]:
            t_next = t
            break
    ans[i] = S[s_next - 1]
    s_last = s_next - 1
    t_last = t_next - 1

print("".join(ans))

Solution (Python):
import numpy as np

s = np.array(list(input()))
t = np.array(list(input()))
dp = np.zeros((len(s) + 1, len(t) + 1), dtype=int)

is_eq = s[:, None] == t[None,]
for i in range(len(s)):
    dp[i + 1, 1:] = np.maximum(dp[i, :-1] + is_eq[i], dp[i, 1:])
    dp[i + 1] = np.maximum.accumulate(dp[i + 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]
        i -= 1
        j -= 1
print(ans[::-1])

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

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

for t in range(1, t_len + 1):
    for s in range(1, s_len + 1):
        ans_array[t][s] = max(ans_array[t - 1][s], ans_array[t][s - 1])
        if T[t - 1] == S[s - 1]:
            ans_array[t][s] = ans_array[t - 1][s - 1] + 1

ans_r = []

s = s_len
t = t_len

while s > 0 and t > 0:
    if ans_array[t][s] == ans_array[t - 1][s]:
        t -= 1
    elif ans_array[t][s] == ans_array[t][s - 1]:
        s -= 1
    else:
        t -= 1
        s -= 1
        ans_r.append(S[s])

print("".join(reversed(ans_r)))

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

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

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

def main():
    s = input().strip()
    t = input().strip()
    n = len(s)
    m = len(t)
    dp = [[0] * (m+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            if s[i-1] == t[j-1]:
                dp[i][j] = max(dp[i-1][j-1] + 1, dp[i][j])
    
    ans_r = []
    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_r.append(s[n])
    print("".join(reversed(ans_r)))

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    s = input()
    t = input()
    dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]
    for i,x in enumerate(s):
        for j,y in enumerate(t):
            if x == y:
                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 = ''
    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
    print(ans[::-1])

if __name__ == '__main__':
    main()

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

s,t=len(S),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+1][j] , dp[i][j+1] ])


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)

Solution (Python):

import sys


def solve(s: str, t: str):
    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] = 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 m > 0 and n > 0:
        if s[n-1] == t[m-1]:
            ans = s[n-1] + ans
            n -= 1
            m -= 1
        elif dp[n][m] == dp[n-1][m]:
            n -= 1
        else:
            m -= 1
    print(ans)



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)  
    solve(s, t)


if __name__ == '__main__':
    main()

Solution (Python):
s = ["0"] + list(input())
t = ["0"] + list(input())
n, m = len(s), len(t)
dp = [[0] * m for _ in range(n)]
for i in range(1, n):
    for j in range(1, m):
        if s[i] == t[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
ans = []
c = dp[n - 1][m - 1]
for i in range(n - 1, 0, -1):
    if m == 0:
        break
    for j in range(m - 1, 0, -1):
        if s[i] == t[j] and dp[i][j] == c:
            ans.append(s[i])
            c -= 1
            m = j
            break
        elif dp[i][j] < c:
            break
ans.reverse()
print("".join(ans))

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

Solution (Python):






"""Module docstring
"""

import sys


def solve(s, t):
    v = [0] * (len(s) + 1)
    dp = [v]
    for _, ti in enumerate(t, 1):
        u, v = v, v.copy()
        dp.append(v)
        ll, ul = 0, 0
        for j, sj in enumerate(s, 1):
            uj = u[j]
            if sj == ti:
                v[j] = 1 + ul
                ll = 1 + ul
            else:
                if ll > uj:
                    v[j] = ll
                else:
                    ll = uj
            ul = uj
    i = len(t)
    j = len(s)
    k = dp[i][j]
    selected = []
    while k > 0:
        if dp[i - 1][j] == k:
            i -= 1
        elif dp[i][j - 1] == k:
            j -= 1
        else:
            selected.append(t[i - 1])
            k -= 1
            i -= 1
            j -= 1
    return "".join(selected[::-1])


def do_job():
    "Do the work"
    s = input()
    t = input()
    result = solve(s, t)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case 


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

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

    s = input().rstrip()
    t = input().rstrip()

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

    dp = []
    for _ in range(n + 1):
        dp.append([0] * (m + 1))

    for i in range(1, n + 1):
        s_ = s[i - 1]
        for j in range(1, m + 1):
            t_ = t[j - 1]
            if s_ != t_:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            else:
                dp[i][j] = dp[i - 1][j - 1] + 1
    ans = []
    while n > 0 and m > 0:
        if s[n - 1] == t[m - 1]:
            ans.append(s[n - 1])
            n -= 1
            m -= 1
        elif dp[n][m] == dp[n - 1][m]:
            n -= 1
        else:
            m -= 1
    print("".join(ans[::-1]))


if __name__ == '__main__':
    main()

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

    s = input().rstrip()
    t = input().rstrip()

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

    dp = []
    for _ in range(n + 1):
        dp.append([0] * (m + 1))

    for i in range(1, n + 1):
        s_ = s[i - 1]
        for j in range(1, m + 1):
            t_ = t[j - 1]
            if s_ != t_:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            else:
                dp[i][j] = dp[i - 1][j - 1] + 1
    ans = []
    while n > 0 and m > 0:
        if dp[n][m] == dp[n][m - 1]:
            m -= 1
        elif dp[n][m] == dp[n - 1][m]:
            n -= 1
        else:
            ans.append(s[n - 1])
            n -= 1
            m -= 1
    print("".join(ans[::-1]))


if __name__ == '__main__':
    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):
        dp[i][j] = max(dp[i][j], dp[i-1][j])
        dp[i][j] = max(dp[i][j], dp[i][j-1])
        if s[i-1] == t[j-1]:
            dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)

ans = []
i = len(s)
j = 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:
        i -= 1
        j -= 1
        ans.append(s[i])
print("".join(ans[::-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):
        dp[i][j] = max(dp[i][j], dp[i-1][j])
        dp[i][j] = max(dp[i][j], dp[i][j-1])
        if s[i-1] == t[j-1]:
            dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)

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

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

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

ans=str()
while sl>0 and tl>0:
    if dp[sl][tl]==dp[sl-1][tl]:
        sl-=1
    elif dp[sl][tl]==dp[sl][tl-1]:
        tl-=1
    else:
        ans+=s[sl-1]
        sl-=1
        tl-=1

print(ans[::-1])

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

if s[0]==t[0]:
    dp[0][0]=1

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

ans=str()
while sl>0 and tl>0:
    if dp[sl][tl]==dp[sl-1][tl]:
        sl-=1
    elif dp[sl][tl]==dp[sl][tl-1]:
        tl-=1
    else:
        ans+=s[sl-1]
        sl-=1
        tl-=1

print(ans[::-1])

Solution (Python):
def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)
    dp = [[0] * (M+1) for _ in range(N+1)]
    
    for i in range(1, N+1):
        for j in range(1, M+1):
            p = (S[i-1] == T[j-1])
            dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + p)
            
    ans = []
    x, y = N, M
    while x and y:
        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(reversed(ans)))


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)
    dp = [[0] * (M+1) for _ in range(N+1)]
    
    for i in range(1, N+1):
        for j in range(1, M+1):
            p = (S[i-1] == T[j-1])
            dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + p)
            
    ans = []
    x, y = N, M
    while x and y:
        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]))


if __name__ == "__main__":
    main()

Solution (Python):

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

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

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

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

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

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

Solution (Python):
S = input()
T = input()
ls = len(S)
lt = len(T)

dp = [[0]*(lt+1) for _ in range(ls+1)]
dp[0][0] = 0
for i, s in enumerate(S):
    for j, t in enumerate(T):
        if s == 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])
        dp[i+1][j+1] = max(dp[i+1][j+1], 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 backtrace(dp, col_str):
    res = []
    r, c = len(dp) - 1, len(dp[0]) - 1
    while dp[r][c] != 0:
        if dp[r-1][c] == dp[r][c]:
            r -= 1
        elif dp[r][c-1] == dp[r][c]:
            c -= 1
        elif dp[r-1][c-1] + 1 == dp[r][c]:
            res.append(col_str[c-1])
            r -= 1
            c -= 1

    if res == []:
        return ""
    else:
        return "".join(map(str, res[::-1]))

def solve(s, t):
    len_s, len_t = len(s), len(t)
    dp = [[0] * (len_t+1) for _ in range(len_s+1) ]

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

    return backtrace(dp, t)

s = input()
t = input()

print(solve(s, t))

Solution (Python):
def solve(s, t):
    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+1][j], dp[i][j+1])
    sol = []
    pr, pc = n, m
    while pr > 0 and pc > 0:
        if dp[pr][pc] > dp[pr-1][pc] and dp[pr][pc] > dp[pr][pc-1]:
            sol.append(s[pr-1])
            pr -= 1
            pc -= 1
        elif dp[pr][pc-1] > dp[pr-1][pc]:
            pc -= 1
        else:
            pr -= 1
    return ''.join(reversed(sol))
  
s = input()
t = input()
print(solve(s, t))

Solution (Python):

"""
Created on Mon Apr 13 22:34:56 2020

@author: ctiuser
"""

import numpy as np

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

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

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

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)

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

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

print(ans)

Solution (Python):
def solve(X,Y):
    res=''
    n,m=len(X),len(Y)
    dp=[[0]*(m+1) for i in range(n+1)]
    for i in range(n):
        for j in range(m):
            if(X[i]==Y[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][j+1],dp[i+1][j]])
    i,j=i+1,j+1
    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+=X[i]
    return res[::-1]

def main():
    X=input()
    Y=input()
    print(solve(X,Y))

if __name__=='__main__':
    main()