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):
def main():
    s1, s2 = input(), input()
    n, m = len(s1), len(s2)

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

    for row in range(1, n + 1):
        for column in range(1, m + 1):
            if s1[row - 1] == s2[column - 1]:
                dp[row][column] = 1 + dp[row - 1][column - 1]
                previous[row][column] = (row - 1, column - 1)
            else:
                dpUp = dp[row - 1][column]
                dpLeft = dp[row][column - 1]

                if dpUp > dpLeft:
                    dp[row][column] = dpUp
                    previous[row][column] = (row - 1, column)
                else:
                    dp[row][column] = dpLeft
                    previous[row][column] = (row, column - 1)

    lcs = ''
    curr = (n, m)

    while True:
        row, column = curr
        if previous[row][column] == 0: break

        if s1[row - 1] == s2[column - 1]:
            lcs = f'{s1[row - 1]}{lcs}'

        curr = previous[row][column]

    print(lcs)

main()

Solution (Python):
import sys
def main():
    s=list(sys.stdin.readline().strip())
    t=list(sys.stdin.readline().strip())
    S,T=len(s),len(t)
    dp=[[0 for _ in range(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
            dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j],dp[i][j+1])
    res=''
    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:
            res=s[i-1]+res
            i,j=i-1,j-1
    print(res)
if __name__=='__main__':main()

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


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

for i, ei in enumerate(s, 1):
    for j, ej in enumerate(t, 1):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1], (dp[i-1][j-1] + 1) * (ei == ej))

i = len(s)
j = len(t)
ans = []
while i and j:
    if dp[i-1][j] == dp[i][j]:
        i -= 1
    elif dp[i][j-1] == dp[i][j]:
        j -= 1
    else:
        ans.append(s[i-1])
        i -= 1
        j -= 1

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

Solution (Python):
s = input()
t = input()
m = len(s)
n = len(t)

dp = [[0 for i in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
  for j in range(1, m+1):
    if s[j-1] == t[i-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 s[j-1] == t[i-1]:
    res = s[j-1] + res
    i -= 1
    j -= 1
  
  else:
    if dp[i-1][j] > dp[i][j-1]:
      i -= 1
    else:
      j -= 1

print(res)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


s = input()
t = input()

def sub(s,t):
    """共通部分文字列長
    """
    ls = len(s)
    lt = len(t)
    dp = [[0]*(lt+1) for _ in range(ls+1)]
    
    prev = [[None]*(lt+1) for _ in range(ls+1)]
    
    for i in range(1,ls+1):
        for j in range(1,lt+1):
            if dp[i][j-1]>dp[i-1][j]:
                v = dp[i][j-1]
                pp = (i,j-1)
            else:
                v = dp[i-1][j]
                pp = (i-1,j)
            if s[i-1]==t[j-1] and dp[i-1][j-1] + 1 > v:
                v = dp[i-1][j-1] + 1
                pp = (i-1,j-1)
            dp[i][j] = v
            
            prev[i][j] = pp
            
    return dp, prev

dp, prev = sub(s,t)
ans = []
i,j = len(s), len(t)
while prev[i][j] is not None:
    if prev[i][j]==(i-1, j-1):
        ans.append(s[i-1])
    i,j = prev[i][j]
print("".join(ans[::-1]))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



s = input()
t = input()

def sub(s,t):
    """共通部分文字列長
    """
    ls = len(s)
    lt = len(t)
    dp = [[0]*(lt+1) for _ in range(ls+1)]
    
    prev = [[None]*(lt+1) for _ in range(ls+1)]
    
    for i in range(1,ls+1):
        for j in range(1,lt+1):
            vals = [dp[i][j-1], dp[i-1][j]]
            if s[i-1]==t[j-1]:
                vals.append(dp[i-1][j-1] + 1)
            m = max(vals)
            dp[i][j] = m
            
            ind = vals.index(m)
            if ind==0:
                prev[i][j] = (i,j-1)
            elif ind==1:
                prev[i][j] = (i-1,j)
            else:
                prev[i][j] = (i-1,j-1)
            
    return dp, prev

dp, prev = sub(s,t)
ans = []
i,j = len(s), len(t)
while prev[i][j] is not None:
    if prev[i][j]==(i-1, j-1):
        ans.append(s[i-1])
    i,j = prev[i][j]
print("".join(ans[::-1]))

Solution (Python):
a = input()
b = input()
na = len(a)
nb = len(b)

dp = [[0]*(nb+1) for _ in range(na+1)]

for i in range(na):
    for j in range(nb):
        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])
ans = []
num = dp[na][nb]
x = na
y = nb
while num:
    if dp[x][y] == dp[x-1][y]:
        x -= 1
    elif dp[x][y] == dp[x][y-1]:
        y -= 1
    else:
        ans.append(a[x-1])
        x -= 1
        y -= 1
        num -= 1

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

Solution (Python):
s1=input()
s2=input()
n1,n2=len(s1),len(s2)
dp=[[-1 for j in range(n2+1)] for i in range(n1+1)]
for i in range(n1,-1,-1):
    for j in range(n2,-1,-1):
        if i==n1 or j==n2:
            dp[i][j]=0
        else:
            if s1[i]==s2[j]:
                dp[i][j]=1+dp[i+1][j+1]
            else:
                dp[i][j]=max(dp[i][j+1],dp[i+1][j])
n=""
i,j=0,0
while i<n1 and j<n2:
    if dp[i][j]==dp[i+1][j]:
        i+=1
    elif dp[i][j]==dp[i][j+1]:
        j+=1
    else:
        n+=s1[i]
        i+=1
        j+=1
print(n)

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

Solution (Python):
def solve(S, T):
    L1 = len(S)
    L2 = len(T)
    dp = [[0]*(L2+1) for i in range(L1+1)]

    for i in range(L1-1, -1, -1):
        for j in range(L2-1, -1, -1):
            r = max(dp[i+1][j], dp[i][j+1])
            if S[i] == T[j]:
                r = max(r, dp[i+1][j+1] + 1)
            dp[i][j] = r

    

    
    res = []
    i = 0; j = 0
    while i < L1 and j < L2:
        if S[i] == T[j]:
            res.append(S[i])
            i += 1; j += 1
        elif dp[i][j] == dp[i+1][j]:
            i += 1
        elif dp[i][j] == dp[i][j+1]:
            j += 1
    return "".join(res)

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

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

S, T = len(s), len(t)
dp = [[0]*(T+1) for _ in range(S+1)]
prev = [[(-1,-1)]*(T+1) for _ in range(S+1)]

for i in range(S):
    for j in range(T): 
        r = max(dp[i][j-1], dp[i-1][j])
        p = (i, j-1) if r == dp[i][j-1] else (i-1, j)
        if s[i] == t[j]:
            r = max(dp[i-1][j-1] + 1, r) 
            p = (i-1, j-1) if r == dp[i-1][j-1] + 1 else p
        dp[i][j] = r
        prev[i][j] = p


ans = ''
i, j = S - 1, T - 1
while i >= 0 and j >= 0:
    if prev[i][j] == (i-1, j-1):
        ans += s[i]
    i, j = prev[i][j]

print(ans[::-1])

Solution (Python):



s = input()
t = input()


def main():
    sn, tn = len(s), len(t)
    dp = [[0] * (tn + 1) for _ in range(sn + 1)]
    w = [[None] * (tn + 1) for _ in range(sn + 1)]
    for i in range(1, sn + 1):
        for j in range(1, tn + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                w[i][j] = s[i - 1]
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
    ans = []
    i, j = sn, tn
    while i != 0 and j != 0:
        if s[i - 1] == t[j - 1]:
            ans.append(w[i][j])
            i, j = i - 1, j - 1
        else:
            if dp[i][j - 1] < dp[i - 1][j]:
                i -= 1
            else:
                j -= 1
    print("".join(ans[::-1]))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import numpy as np

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

def longest_common_subsequence(S, T):
    """compute table dp satisfying: 
    dp[i,j] = LCS(S[:i], T[:j])"""
    LS, LT = len(S), len(T)
    dp = np.zeros((LS + 1, LT + 1), np.int32)
    for n in range(1, LS + 1):
        dp[n, 1:] = dp[n - 1, :-1] + (S[n - 1] == T)  
        np.maximum(dp[n], dp[n - 1], out=dp[n])  
        np.maximum.accumulate(dp[n], out=dp[n])  
    return dp

def reconstruct_LCS(S, T, dp):
    tmp = []
    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if S[i - 1] == T[j - 1]:
            i, j = i - 1, j - 1
            tmp.append(S[i])
        elif dp[i, j] == dp[i - 1, j]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(tmp))

S = np.array(list(readline().decode()), 'U1')[:-1]
T = np.array(list(readline().decode()), 'U1')[:-1]

dp = longest_common_subsequence(S, T)

print(reconstruct_LCS(S, T, dp))

Solution (Python):
import sys
import numpy as np

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

def longest_common_subsequence(S, T):
    """compute table dp satisfying: 
    dp[i,j] = LCS(S[:i], T[:j])"""
    LS, LT = len(S), len(T)
    dp = np.zeros((LS + 1, LT + 1), np.int32)
    for n in range(1, LS + 1):
        dp[n, 1:] = dp[n - 1, :-1] + (S[n - 1] == T)  
        np.maximum(dp[n], dp[n - 1], out=dp[n])  
        np.maximum.accumulate(dp[n], out=dp[n])  
    return dp


def reconstruct_LCS(S, T, dp):
    tmp = []
    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if S[i - 1] == T[j - 1]:
            i, j = i - 1, j - 1
            tmp.append(S[i])
        elif dp[i, j] == dp[i - 1, j]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(tmp))

S = np.array(list(readline().decode()), 'U1')[:-1]
T = np.array(list(readline().decode()), 'U1')[:-1]
dp = longest_common_subsequence(S, T)

print(reconstruct_LCS(S, T, dp))

Solution (Python):
import sys
import numpy as np

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

S = np.array(list(readline().decode()), 'U1')[:-1]
T = np.array(list(readline().decode()), 'U1')[:-1]

def longest_common_subsequence(S, T):
    """compute table dp satisfying: 
    dp[i,j] = LCS(S[:i], T[:j])"""
    LS, LT = len(S), len(T)
    dp = np.zeros((LS + 1, LT + 1), np.int32)
    for n in range(1, LS + 1):
        dp[n, 1:] = dp[n - 1, :-1] + (S[n - 1] == T)  
        np.maximum(dp[n], dp[n - 1], out=dp[n])  
        np.maximum.accumulate(dp[n], out=dp[n])  
    return dp

dp = longest_common_subsequence(S, T)

answer = []
i, j = len(S), len(T)
while i > 0 and j > 0:
    if dp[i, j] == dp[i - 1, j - 1] + (S[i - 1] == T[j - 1]):
        i, j = i - 1, j - 1
        if S[i] == T[j]:
            answer.append(S[i])
    elif dp[i, j] == dp[i - 1, j]:
        i -= 1
    elif dp[i, j] == dp[i, j - 1]:
        j -= 1
    else:
        raise ValueError

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

Solution (Python):
s=input()
t=input()
dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)):
  for j in range(len(t)):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
len_=dp[len(s)][len(t)]
s_now=len(s)
t_now=len(t)
ans=''
if len_==0:
  print(ans)
  exit()
while len_>0:
  if s[s_now-1]==t[t_now-1]:
    ans=ans+s[s_now-1]
    len_+=-1
    s_now+=-1
    t_now+=-1
    
  else:
    if dp[s_now][t_now]==dp[s_now][t_now-1]:
      t_now=t_now-1
    elif dp[s_now][t_now]==dp[s_now-1][t_now]:
      s_now=s_now-1
ans=ans[::-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])

x=len(s)
y=len(t)
ans=""
while x!=0 and y!=0:
    if dp[x-1][y]==dp[x][y]:
        x-=1
    elif dp[x][y-1]==dp[x][y]:
        y-=1
    else:
        ans=t[y-1]+ans
        x-=1
        y-=1
print(ans)

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

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


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


ans = ""
i, j = len(s), len(t)

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

print(ans)

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

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):
def solve():
    Ss = input().rstrip()
    Ts = input().rstrip()

    lenS, lenT = len(Ss), len(Ts)

    dp = [[0]*(lenT+1) for _ in range(lenS+1)]
    for iS, S in enumerate(Ss, start=1):
        dp0 = dp[iS-1]
        dpi = dp[iS]
        for jT, T in enumerate(Ts, start=1):
            if S == T:
                dpi[jT] = dp0[jT-1] + 1
            else:
                dpi[jT] = dpi[jT-1]
                if dp0[jT] > dpi[jT]:
                    dpi[jT] = dp0[jT]

    anss = ''
    iS, jT = lenS, lenT
    while True:
        if Ss[iS-1] == Ts[jT-1]:
            anss += Ss[iS-1]
            iS, jT = iS-1, jT-1
        elif dp[iS-1][jT] >= dp[iS][jT-1]:
            iS -= 1
        else:
            jT -= 1
        if iS == 0 or jT == 0:
            break

    print(anss[::-1])


solve()

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


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

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

i=len(s)-1
j=len(t)-1

L=dp[i][j]

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


print(result[::-1])

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

S = readline().rstrip()
T = readline().rstrip()











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:
      if dp[i][j + 1] > dp[i + 1][j]:
        dp[i + 1][j + 1] = dp[i][j + 1]
      else:
        dp[i + 1][j + 1] = dp[i + 1][j]


ans = ""
x = len(S)
y = len(T)
while x != 0 and y != 0:
  if dp[x][y] == dp[x - 1][y]: 
    x -= 1
  elif dp[x][y] == dp[x][y - 1]: 
    y -= 1
  else:
    ans += S[x - 1]
    x -= 1
    y -= 1

print(ans[::-1])

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

S = readline().rstrip()
T = readline().rstrip()











dp = [[0] * (len(T) + 1) for i in range(len(S) + 1)]
route = [[(0,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
      route[i + 1][j + 1] = (i,j)
    else:
      if dp[i][j + 1] > dp[i + 1][j]:
        dp[i + 1][j + 1] = dp[i][j + 1]
        route[i + 1][j + 1] = (i,j + 1)
      else:
        dp[i + 1][j + 1] = dp[i + 1][j]
        route[i + 1][j + 1] = (i + 1,j)


x,y = len(S),len(T)
ans = ""
while x != 0 and y != 0:
  if S[x - 1] == T[y - 1]:
    ans += S[x - 1]
  x,y = route[x][y]

print(ans[::-1])

Solution (Python):
s=input()
t=input()
n = len(s)
m = len(t)
dp=[]
for i in range(n+1):
    dp.append([0]*(m+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])
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+=s[i-1]
        i-=1
        j-=1
print(ans[::-1])

Solution (Python):
s=input()
t=input()
n=len(s)
m=len(t)

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

for i in range(n):
  for j in range(m):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1

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



ans=''
while n>=0 and m>=0:
  if dp[n][m]==dp[n-1][m]:
    n-=1

  elif dp[n][m]==dp[n][m-1]:
    m-=1

  else:
    n-=1
    m-=1
    ans+=s[n]

print(ans[::-1])

Solution (Python):










import numpy as np

def main():
    S = np.array(list(input()), dtype='unicode')
    T = np.array(list(input()), dtype='unicode')
    ls = len(S)
    lt = len(T)

    equal = S[:, None] == T[None,:]


    dp = np.zeros((ls + 1, lt + 1), dtype=int)

    for i in range(ls):
        dp[i + 1][1:] = np.maximum(dp[i][1:], dp[i][:-1] + equal[i])
        dp[i + 1] = np.maximum.accumulate(dp[i + 1])








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

if __name__ == '__main__':
    main()

Solution (Python):










import numpy as np

def main():
    S = np.array(list(input()), dtype='unicode')
    T = np.array(list(input()), dtype='unicode')
    ls = len(S)
    lt = len(T)

    equal = S[:, None] == T[None,:]


    dp = np.zeros((ls + 1, lt + 1), dtype=int)

    for i in range(ls):
        dp[i + 1][1:] = np.maximum(dp[i][1:], dp[i][:-1] + equal[i])
        dp[i + 1] = np.maximum.accumulate(dp[i + 1])








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

if __name__ == '__main__':
    main()

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

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

for i,c in enumerate(s):
    for j,d in enumerate(t):
        if c==d:
            dp[i+1][j+1]=dp[i][j]+1
            ans[i+1][j+1]=(i,j)
        else:
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
            ans[i+1][j+1]=ans[i][j+1] if dp[i+1][j+1]==dp[i][j+1] else ans[i+1][j]

i=len(s)
j=len(t)
ss=['']*dp[i][j]
l=dp[i][j]-1
while i>0 and j>0:
    i,j=ans[i][j]
    if i>-1:
        ss[l]=s[i]
        l-=1

print(''.join(ss))

Solution (Python):
s1=input()
s2=input()
l1=len(s1)
l2=len(s2)
dp=[[0 for i in range(l2+1)] for j in range(l1+1)]
for i in range(1,l1+1):
    for j in range(1,l2+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])
i=l1;j=l2
ans=""
while(i>0 and j>0):
    if s1[i-1]==s2[j-1]:
        ans=s1[i-1]+ans
        i-=1
        j-=1
    else:
        if dp[i-1][j]>dp[i][j-1]:
            i-=1
        else:
            j-=1
print(ans)

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

a=len(s)
b=len(t)

dp=[ [0 for _ in range(a+1)] for _ in range(b+1)]

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



ans=""
x=a
y=b
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 += s[x-1]
        y -=1
        x -=1
print(ans[::-1])

Solution (Python):
import numpy
s = numpy.array(list(input()))
t = numpy.array(list(input()))
ns = len(s)
nt = len(t)
match = s.reshape(-1,1) == t.reshape(1,-1)
memo = numpy.zeros([ns+1, nt+1], dtype = int)
for i in range(ns):
    memo[i+1, 1:] = numpy.fmax(memo[i, :-1]+match[i], memo[i, 1:])
    
    memo[i+1] = numpy.maximum.accumulate(memo[i+1])
ans = []
while ns >0 and nt>0:
    if memo[ns, nt] == memo[ns-1, nt]:
        ns -= 1
    elif memo[ns, nt] == memo[ns, nt-1]:
        nt -= 1
    else:
        ans.append(s[ns-1])
        
        nt-=1
        ns -=1
print("".join(ans[::-1]))

Solution (Python):
s=input()
t=input()
n=len(t)
m=len(s)
dp=[[0]*(n+1) for i in range(m+1)]
for i in range(m):
  for j in range(n):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1

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

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


kotae.reverse()
kotae = "".join(kotae)
print(kotae)

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

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

ans = []
s_i = len(s)
t_i = len(t)
while s_i > 0 and t_i > 0:
    if dp[s_i][t_i] == dp[s_i][t_i-1]:
        t_i -= 1
    elif dp[s_i][t_i] == dp[s_i-1][t_i]:
        s_i -= 1
    else: 
        s_i -= 1
        t_i -= 1
        if t_i >= 0:
            ans.append(t[t_i])


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

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 = []
while lenS!=0 and lenT!=0:
    if dp[lenS][lenT]==dp[lenS-1][lenT]:
        lenS-=1
    elif dp[lenS][lenT]==dp[lenS][lenT-1]:
        lenT-=1
    else:
        ans.append(S[lenS-1])
        lenS-=1
        lenT-=1
ans = ans[::-1]
print("".join(ans))

Solution (Python):
s = input()
t = input()
dp = [[0] * (len(s)+1) for _ in range(len(t)+1)]
for i in range(1, len(t)+1):
    ti = t[i-1]
    dp[i] = dp[i-1][:]
    for j in range(1, len(s)+1):
        if ti == s[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

ans = ''
sl = len(s)
tl = len(t)
while sl > 0 and tl > 0:
    if s[sl-1] == t[tl-1]:
        sl -= 1
        tl -= 1
        ans = s[sl] + ans
        continue
    if dp[tl][sl] == dp[tl][sl-1]:
        sl -= 1
    elif dp[tl][sl] == dp[tl-1][sl]:
        tl -= 1
print(ans)

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

Solution (Python):

s = input()
t = input()

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

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

kotae = []

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
        kotae.append(s[i])

kotae.reverse()
kotae = "".join(kotae)
print(kotae)

Solution (Python):


s = input()
t = input()

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

ans = []

for i,_s in enumerate(s):
    for j,_t in enumerate(t):
        dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
        if _s == _t:
            dp[i+1][j+1] = max(dp[i][j]+1,dp[i+1][j+1])

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

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

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

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

revlst = []

lt -= 1
ls -= 1
while dp[lt][ls] != 0:
    while dp[lt][ls] == dp[lt-1][ls]:
        lt -= 1
    while dp[lt][ls] == dp[lt][ls-1]:
        ls -= 1
    revlst.append(lt)
    lt -= 1
    ls -= 1

ans = ''.join([t[_-1] for _ in reversed(revlst)])
print(ans)

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

lim = dp[-1][-1]

i = n
j = m
ans = [None] * (lim)
while i > 0 and j > 0:

    if a[i - 1] == b[j - 1]:
        ans[lim-1] = a[i - 1]
        i -= 1
        j -= 1
        lim -= 1

    else:
        if dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
if ans:
    print("".join(ans))
else:
    print(' ')

Solution (Python):
s = list(input())
t = list(input())
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]=max(dp[i+1][j+1], dp[i][j]+1)
        else:
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
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
    elif dp[i][j]==dp[i-1][j-1]+1:
        ans=[s[i-1]]+ans
        i-=1
        j-=1
print(''.join(ans))

Solution (Python):
def solve(s1,s2):
    rows=len(s1)
    cols=len(s2)
    dp=[[0]*(cols+1) for i in range(rows+1)]
    for i in range(1,rows+1):
        for j in range(1,cols+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])
                
    max_len=dp[rows][cols]
    result=[""]*(max_len+1)
    result[max_len]=""
    i=rows
    j=cols
    while i>0 and j>0:
        if s1[i-1]==s2[j-1]:
            result[max_len-1]=s1[i-1]
            max_len -=1
            i -=1
            j -=1
        elif dp[i-1][j]>dp[i][j-1]:
            i -=1
        else:
            j -=1
    return "".join(result)
            
                










        
        
s1=input()
s2=input()
n=len(s1)
m=len(s2)
result=""
print(solve(s1,s2))

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

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

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

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

i = len(t)
j = len(s)
st = ""

while dp[i][j] != 0:
    if s[j-1] == t[i-1]:
        st += s[j-1]
        i -= 1
        j -= 1
    else:
        if dp[i][j-1] > dp[i-1][j]:
            j -= 1
        else:
            i -= 1
            
print(st[::-1])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

		
s = input()
t = input()

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



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


y = len(s)
x = len(t)
ans = ""
while 1:
	
	if x*y == 0:
		break
	elif s[y-1] == t[x-1]:
		ans += s[y-1]
		x -= 1
		y -= 1
	else:
		if dp[y][x] == dp[y-1][x]:
			y -= 1
		elif dp[y][x] == dp[y][x-1]:
			x -= 1

lcs  = dp[len(s)][len(t)]

q = deque([(len(s), len(t))])
common = [set() for _ in range(lcs)]

while q:
	
	y, x =q.popleft()
	if x*y != 0 :
		if s[y-1] == t[x-1]:
			common[dp[y][x]-1].add(t[x-1])
			y -= 1
			x -= 1
			q.append((y, x))
		else:
			if dp[y][x] == dp[y-1][x]:
				q.append((y-1, x))

			elif dp[y][x] == dp[y][x-1]:
				q.append((y, x-1))

print(*[list(common[i])[0] for i in range(lcs)], sep="")