Problem:
 Score : 100 points    Problem Statement You are given strings s and t .
Find one longest string that is a subsequence of both s and t .      Notes A subsequence of a string x is the string obtained by removing zero or more characters from x and concatenating the remaining characters without changing the order.      Constraints  s and t are strings consisting of lowercase English letters.  1 \leq |s|, |t| \leq 3000         Input Input is given from Standard Input in the following format:  s  t       Output Print one longest string that is a subsequence of both s and t .
If there are multiple such strings, any of them will be accepted.        Sample Input 1 axyb
abyxb      Sample Output 1 axb  The answer is axb or ayb ; either will be accepted.       Sample Input 2 aa
xayaz      Sample Output 2 aa       Sample Input 3 a
z      Sample Output 3   The answer is (an empty string).       Sample Input 4 abracadabra
avadakedavra      Sample Output 4 aaadara

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

ans = ""


def main():
    S = input()
    T = input()
    LS = len(S)
    LT = len(T)
    dp = [[0 for j in range(LT+1)] for i in range(LS+1)]

    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if s == t:
                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]

    def rec(i, j):
        if i == 0 or j == 0:
            return

        if S[i-1] == T[j-1]:
            global ans
            ans += S[i-1]
            rec(i-1, j-1)
        elif dp[i-1][j] > dp[i][j-1]:
            rec(i-1, j)
        else:
            rec(i, j-1)

    rec(LS, LT)
    print(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(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-1][j] == dp[i][j]:
        i -= 1
    elif dp[i][j-1] == dp[i][j]:
        j -= 1
    else:
        ans = s[i-1] + ans
        i -= 1
        j -= 1
        
print(ans)

Solution (Python):
s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0]*(ls+1) for i in range(lt+1)]
ans = ""

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 = lt
j = ls
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[i-1] + ans
        i -= 1
        j -= 1

print(ans)

Solution (Python):
s = input()
t = input()
s_length = len(s)
t_length = len(t)

dp = [[0 for j in range(t_length+1)] for i in range(s_length+1)]

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

print(ans)

Solution (Python):
import sys
def main():
  S=list(sys.stdin.readline())[:-1]
  T=list(sys.stdin.readline())[:-1]
  lS=len(S)
  lT=len(T)
  dp=[[0]*(lS+1) for _ in range(lT+1)]
  for iT in range(lT):
    for iS in range(lS):
      if S[iS]==T[iT]:
        dp[iT+1][iS+1] = max(dp[iT+1][iS],dp[iT][iS+1],dp[iT][iS]+1)
      else:
        dp[iT+1][iS+1] = max(dp[iT+1][iS],dp[iT][iS+1])

  iS = lS
  iT = lT
  ans = ""
  while(iS>0 and iT>0):
    if dp[iT][iS]==dp[iT-1][iS-1]:
      iS -= 1
      iT -= 1
    elif dp[iT][iS]==dp[iT][iS-1]:
      iS -= 1
    elif dp[iT][iS]==dp[iT-1][iS]:
      iT -= 1
    else:
      ans = S[iS-1]+ans
      iS -= 1
      iT -= 1
  print(ans)

if __name__ == '__main__':
  main()

Solution (Python):
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline

class Solver(object):
    def __init__(self):
        pass

    def solve(self,s:str,t:str) -> int:
        
        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][j+1])
        
        ans = ""

        
        
        l,m = len(s),len(t)
        while l > 0 and m >0:
            if dp[l][m] == dp[l-1][m]:
                l -= 1
            elif dp[l][m] == dp[l][m-1]:
                m -= 1
            else:
                ans = t[m-1] + ans
                l -= 1
                m -= 1

        return ans

def main():
    s = input().rstrip()
    t = input().rstrip()
    solver = Solver()
    print(solver.solve(s,t))

if __name__ == "__main__":
    main()

Solution (Python):


def main():

    S = input()
    T = input()

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


    for i, s in enumerate(S):
        for j,t in enumerate(T):

            
            if s == t:
                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, j = len(S), len(T)
    substr = ""
    while i != 0 and j != 0:
        
        if S[i-1] == T[j-1]:
            substr += S[i-1]
            i,j = i-1, j-1
        else:
            
            if dp[i][j-1] >= dp[i-1][j]:
                j -= 1
            else:
                i -= 1
    print(substr[::-1])

if __name__ == "__main__":
    main()

Solution (Python):


def main():

    S = input()
    T = input()

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


    for i, s in enumerate(S):
        for j,t in enumerate(T):

            
            if s == t:
                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, j = len(S), len(T)
    substr = ""
    while i != 0 and j != 0:
        
        if S[i-1] == T[j-1]:
            substr += S[i-1]
            i,j = i-1, j-1
        else:
            
            if dp[i][j-1] >= dp[i-1][j]:
                j -= 1
            else:
                i -= 1
    print(substr[::-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(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])

ret_rev = []

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

ret = "".join(ret_rev[::-1])

print(ret)

Solution (Python):
文字列1 = list(input())
文字列2 = list(input())

テーブル = [[0]*(len(文字列2)+1) for _ in range(len(文字列1)+1)]

for 添字1 in range(len(文字列1)):
    for 添字2 in range(len(文字列2)):
        if 文字列1[添字1] == 文字列2[添字2]:
            テーブル[添字1+1][添字2+1] = テーブル[添字1][添字2] + 1
        else:
            テーブル[添字1+1][添字2+1] = max(テーブル[添字1+1][添字2], テーブル[添字1][添字2+1])

答え = []
添字1 = len(文字列1)
添字2 = len(文字列2)
while True:
    if テーブル[添字1][添字2] == テーブル[添字1][添字2-1]:
        添字2 -= 1
    elif テーブル[添字1][添字2] == テーブル[添字1-1][添字2]:
        添字1 -= 1
    else:
        答え.append(文字列1[添字1-1])
        添字1 -= 1
        添字2 -= 1

    if 添字1 == 0 or 添字2 == 0:
        break

答え.reverse()
print(''.join(答え))

Solution (Python):
文字列1 = list(input())
文字列2 = list(input())

テーブル = [[0]*(len(文字列2)+1) for _ in range(len(文字列1)+1)]

for i in range(len(文字列1)):
    for j in range(len(文字列2)):
        if 文字列1[i] == 文字列2[j]:
            テーブル[i+1][j+1] = テーブル[i][j] + 1
        else:
            テーブル[i+1][j+1] = max(テーブル[i+1][j], テーブル[i][j+1])

答え = []
i = len(文字列1)
j = len(文字列2)
while True:
    if テーブル[i][j] == テーブル[i][j-1]:
        j -= 1
    elif テーブル[i][j] == テーブル[i-1][j]:
        i -= 1
    else:
        答え.append(文字列1[i-1])
        i -= 1
        j -= 1

    if i == 0 or j == 0:
        break

答え.reverse()
print(''.join(答え))

Solution (Python):
s = list(str(input()))
t = list(str(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]:
            try:
                
                dp[i+1][j+1] = dp[i][j] + 1
            except IndexError:
                print(i, j)
        try:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1], dp[i+1][j+1])
        except IndexError:
            print(i,j)

"""
for i in range(len(s)+1):
    print(dp[i])
"""

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

print(str)

Solution (Python):
s = list(input())
t = list(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 = len(s)
j = len(t)
while True:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        ans.append(s[i-1])
        i -= 1
        j -= 1

    if i == 0 or j == 0:
        break

ans.reverse()
print(''.join(ans))

Solution (Python):
def main():
    s = input()
    t = input()
    s_len = len(s)
    t_len = len(t)

    dp_table = [[0] * (s_len+1) for _ in range(t_len+1)]

    for i in range(1, s_len+1):
        for j in range(1, t_len+1):
            if s[i-1] == t[j-1]:
                dp_table[j][i] = max(dp_table[j-1][i], dp_table[j][i-1], dp_table[j-1][i-1] + 1)
            else:
                dp_table[j][i] = max(dp_table[j-1][i], dp_table[j][i-1])
    
    ans = ''
    
    i = s_len
    j = t_len
    while(i != 0 and j != 0):
        if s[i-1] == t[j-1]:
            ans = s[i-1] + ans
            i -= 1
            j -= 1
        elif dp_table[j-1][i] > dp_table[j][i-1]:
            j -= 1
        else:
            i -= 1

    print(ans)
    
if __name__ == '__main__':
    main()

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

j = len(s)
k = len(t)
answer = ""
c = dp[len(s)][len(t)]
while c!=0:
    if s[j-1] == t[k-1]:
        answer += s[j-1]
        j -= 1
        k -= 1
        c = dp[j][k]
    elif dp[j][k] == dp[j-1][k]:
        j -= 1
    else:
        k -= 1
print(answer[::-1])

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

ans = ''


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

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

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

ans = ''

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

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

Solution (Python):
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

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

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

for si in range(n):
    for ti in range(m):
        if s[si]==t[ti]:
            dp[si+1][ti+1] = dp[si][ti]+1
        else:
            dp[si+1][ti+1] = max(dp[si+1][ti],dp[si][ti+1])

ans = ""
x = dp[-1][-1]
for i in range(n,-1,-1):
    for j in range(m,-1,-1):
        if dp[i][j]==x:
            if (dp[i-1][j]==x-1) and (dp[i][j-1]==x-1):
                ans = s[i-1]+ans
                x-=1
                break
print(ans)

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


def main():
    S = input().strip()
    T = input().strip()

    ls = len(S)
    lt = len(T)
    dp = [[0]*(lt+1) for _ in range(ls+1)]
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if s == t:
                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 = ""
    x = dp[-1][-1]
    for i in range(ls, -1, -1):
        for j in range(lt, -1, -1):
            if dp[i][j] == x:
                if dp[i-1][j] == x-1 and dp[i][j-1] == x-1:
                    ans = S[i-1] + ans
                    x -= 1
                    break
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import sys


def solve(s: str, t: str):
    N = len(s)
    W = len(t)
    dp = [[0] * (W+1) for i in range(N+1)]

    for i in range(N):
        for j in range(W):
            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 W > 0:
        if(dp[N][W] == dp[N-1][W]):
            N -= 1
        elif(dp[N][W] == dp[N][W-1]):
            W -= 1
        elif(dp[N][W] == dp[N-1][W-1]+1):
            ans = [s[N-1]] + ans
            N -= 1
            W -= 1


    print(''.join(ans))

    return



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 = input()
t = input()
Ls = len(s)
Lt = len(t)

dp = [[0]*(Ls+1) for i in range(Lt+1)]
Lans = 0

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])
    Lans = max(Lans,dp[i][j])
i = Lt
j = Ls
ans = [""]*Lans
count = 0
while Lans > 0:
  if dp[i][j] == dp[i-1][j]:
    i -= 1
  elif dp[i][j] == dp[i][j-1]:
    j -= 1
  else:
    ans[Lans-1] = s[j-1]
    i -= 1
    j -= 1
    Lans -= 1
print("".join(ans))

Solution (Python):
import sys
imput = sys.stdin.readline
def main():
    
    str_s = input()
    str_t = input()
    s_len = len(str_s)
    t_len = len(str_t)

    
    dp = [[0]*(t_len+1) for _ in range((s_len+1))]
    for i, s in enumerate(str_s):
        for j, t in enumerate(str_t):
            if s==t:
                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 = ""
    while True:
        if i<0 or j<0:
            break
        elif str_s[i]==str_t[j]:
            ans = str_s[i] + ans
            i -= 1
            j -= 1
        elif dp[i+1][j+1] == dp[i][j+1]:
            i -= 1
        elif dp[i+1][j+1] == dp[i+1][j]:
            j -= 1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def lcs(s,t):
    m,n = len(s),len(t)
    a = [[0 for j in range(n+1)]for i in range(m+1)]
    k,p = "",0
    for i in range(m+1):
        for j in range(n+1):
            if i==0 or j==0:
                a[i][j]=0
            elif s[i-1]==t[j-1]:
                a[i][j]=a[i-1][j-1]+1
            else:
                a[i][j] = max(a[i-1][j],a[i][j-1])
    i,j = m,n
    while i>0 and j>0:
        if s[i-1]==t[j-1]:
            k+=s[i-1]
            i-=1
            j-=1
        elif a[i-1][j]>a[i][j-1]:
            i-=1
        else:
            j-=1
    return k[::-1]
s = input()
t = input()
k = lcs(s,t)
print(k)

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

DP = [[0] * (3100) for i in range(3100)]


def chmax(a, b):
    if a < b:
        a = b
    return a


for i in range(len(s)):
    for j in range(len(t)):

        if s[i] == t[j]:
            DP[i + 1][j + 1] = chmax(DP[i + 1][j + 1], DP[i][j] + 1)
        DP[i + 1][j + 1] = chmax(DP[i + 1][j + 1], DP[i][j + 1])
        DP[i + 1][j + 1] = chmax(DP[i + 1][j + 1], DP[i + 1][j])

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

print(Str)

Solution (Python):
S = input()
T = input()
Slen = len(S) + 1
Tlen = len(T) + 1

DP = []
for _ in range(Tlen):
    DP.append([0] * Slen)


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


ans = ""
i = len(S)
j = len(T)
while i > 0 and j > 0:
    if DP[j][i] == DP[j-1][i]:
        j -= 1
    elif DP[j][i] == DP[j][i-1]:
        i -= 1
    else:
        i -= 1
        j -= 1
        ans += S[i]

print(ans[::-1])

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

ret_rev = []

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

ret = "".join(ret_rev[::-1])

print(ret)

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

ret_rev = ""

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

ret = ret_rev[::-1]

print(ret)

Solution (Python):
"""
Longest Common Subsequence
axyb
abyxb
-> axb or ayb
最長の共通部分文字列を取り出す
"""

S = input()
T = input()

N = 3300
dp = [[0] * N for i in range(N)]
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])

ns = len(S)
ts = len(T)



cnt = dp[ns][ts]
ans_r = ""
for i in range(ns,-1,-1):
    flg = True
    for j in range(ts,-1,-1):
        if flg and dp[i][j] == dp[i+1][j] == dp[i][j+1] == dp[i+1][j+1] -1 == cnt-1: 
            
            ans_r += S[i]
            flg = False
            cnt -= 1
print(ans_r[::-1])

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

s = input().split() 
s = list(s[0])
t = input().split() 
t = list(t[0])

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


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

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

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

for i in range(1,M+1):
  for j in range(1,N+1):
    if s[j-1] == t[i-1]:
      dp[i][j] = dp[i-1][j-1]+1
    else:
      dp[i][j] = max(dp[i-1][j],dp[i][j-1])
L = dp[-1][-1]
i = M
j = N
ans = [""]*L
cur = L-1
while i>=0 and j>=0:
  if dp[i][j] != dp[i-1][j] and dp[i][j] != dp[i][j-1]:
    ans[cur] = s[j-1]
    i -= 1
    j -= 1
    cur -= 1
  elif dp[i][j] == dp[i-1][j]:
    i -= 1
  else:
    j -= 1
print("".join(ans))

Solution (Python):
"""
https://qiita.com/drken/items/03c7db44ccd27820ea0d


"""
def main():
        
    S = input()
    T = input()

    """
    dp[i+1]][j+1]
    Sのi番目とtのｊ番目まで見たときの共通する部分列の最大長さ
    """
    dp = [[0 for _ in range(len(T)+1)] for _ in range(len(S)+1)]

    
    
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if s == t:
                
                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, j = len(S), len(T)
    """
    なんかi+1,j+1がどのDPノードから更新されてできたのかをたどって、S[i],T[j]が同じであればそれを部分列に加えられるから～みたいな感じで部分列の後ろから作って最後にひっくり返すといいらしい
    
    """

    substr = ""
    while i != 0 and j != 0:
        
        if S[i-1] == T[j-1]:
            substr += S[i-1]
            i,j = i-1, j-1
        else:
            i,j = (i, j-1) if dp[i][j-1] >= dp[i-1][j] else (i-1, j)


    
    """
    while i != 0 and j != 0:
        if S[i-1] == T[j-1]:
            substr +=S[i-1] 
        i,j = prev[(i,j)]
    """
    print(substr[::-1])

if __name__ == "__main__":
    main()

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

dp_list = [ [ 0 for i in range(ls+1) ] for j in range(lt+1) ]
index_list = [ [ None for i in range(ls) ] for j in range(lt) ]

for i in range(lt):
    for j in range(ls):
        if t[i] == s[j]:
            a = dp_list[i+1][j]
            b = dp_list[i][j+1]
            c = dp_list[i][j] + 1 
            p = [a,b,c].index(max(a,b,c))
            dp_list[i+1][j+1] = [a,b,c][p]
            index_list[i][j] = (1,p)

        else:
            a = dp_list[i+1][j]
            b = dp_list[i][j+1]
            p = [a,b].index(max(a,b))
            dp_list[i+1][j+1] = [a,b][p]
            index_list[i][j] = (0,p)

q = dp_list[-1][-1]
r = t   

a = 10**5

ans = ""
y, x = lt-1, ls-1
while y != -1 and x != -1:
    if index_list[y][x][1] == 2:
        x -= 1
        y -= 1
        ans += s[x+1]
    elif index_list[y][x][1] == 1:
        y -= 1
    elif index_list[y][x][1] == 0:
        x -= 1

print(ans[::-1])

Solution (Python):

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

Solution (Python):
import sys
s = sys.stdin.readline().rstrip()
t = sys.stdin.readline().rstrip()

sn = len(s)
tn = len(t)

dp =[[0 for _ in range(tn+1)] for _ in range(sn+1)]

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


L =[]
while sn>0 and tn>0:
    if dp[sn][tn] == dp[sn-1][tn]: 
        sn-=1
    elif dp[sn][tn] == dp[sn][tn-1]:
        tn-=1
    elif dp[sn][tn] == dp[sn-1][tn-1]+1:
        L.append(s[sn-1])
        sn-=1
        tn-=1
        
print(''.join(L[::-1]))

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

res = ''
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
    elif dp[n][m] == dp[n-1][m-1] + 1:
        res += s[n-1]
        n -= 1
        m -= 1
print(res[::-1])

Solution (Python):

strA = input()
strB = input()






dp = [[0] * (len(strA) + 1) for _ in range(len(strB) + 1)]

for i, A in enumerate(strA, 1):
    for j, B in enumerate(strB, 1):
        if A == B:
            dp[j][i] = dp[j - 1][i - 1] + 1
        else:
            dp[j][i] = max(dp[j - 1][i], dp[j][i - 1])
ans = ""
cnt = 1
lstAns = dp[-1]
x, y = len(strA), len(strB)
while x > 0 and y > 0:
    if dp[y][x] == dp[y - 1][x]:
        y -= 1
    elif dp[y][x] == dp[y][x - 1]:
        x -= 1
    else:
        x -= 1
        y -= 1
        ans = strA[x] + ans

print(ans)

Solution (Python):
def main():
  import sys
  input = sys.stdin.readline
  ans = []
  ans_append = ans.append
  s = input()
  t = input()
  a = len(s)
  b = len(t)
  dp = [[0]*(b+1) for _ in range(a+1)]
  prev_w = [[None]*(b+1) for _ in range(a+1)]
  for i in range(a):
    for j in range(b):
      if s[i]==t[j]:
        if dp[i][j]+1>dp[i+1][j+1]:
          dp[i+1][j+1] = dp[i][j]+1
          prev_w[i+1][j+1] = (i,j)
      else:
        if dp[i+1][j]>dp[i][j+1]:
          dp[i+1][j+1]=dp[i+1][j]
          prev_w[i+1][j+1] = (i+1,j)
        else:
          dp[i+1][j+1]=dp[i][j+1]
          prev_w[i+1][j+1] = (i,j+1)
  while a!=0 and b !=0:
    l = dp[a][b]
    a,b=prev_w[a][b]
    if l>dp[a][b]:
      ans_append(s[a])
  ans ="".join(ans)
  ans =ans[::-1]
  print(ans)
if __name__ == '__main__':
    main()

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

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

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

def checkdpn(x,y):
    if dp[x][y] == dp[x-1][y] + 1 and dp[x][y] == dp[x][y-1] + 1:
        return True
    else:
        return False

x = len(S)
y = len(T)
str = ''

while(True):
    if checkdpn(x,y):
        str = S[x-1] + str
        x -= 1
    else:
        if dp[x][y] == dp[x][y-1] + 1:
            x -= 1
        else:
            y -= 1
    if dp[x][y] == 0:
        break
print(str)

Solution (Python):
import sys
input = sys.stdin.readline
s = input()
t = input()
ans = ''
slen = len(s)
tlen = len(t)

dp = [[0 for i in range(tlen+1)] for j in range(slen+1)]

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


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

Solution (Python):
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

S = input()
T = input()
ls = len(S)
lt = len(T)
dp = [[0 for _ in range(lt+5)] for i in range(ls+5)]

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


i = ls
j = lt
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)

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

sn = len(s)
tn = len(t)

dp = tuple([0] * (tn + 1) for _ in range(sn + 1))

for si in range(sn):
    for ti in range(tn):
        if s[si] == t[ti]:
            dp[si + 1][ti + 1] = dp[si][ti] + 1
        else:
            dp[si + 1][ti + 1] = max(dp[si + 1][ti], dp[si][ti + 1])
        

rest = dp[sn][tn]

si = sn - 1
ti = tn - 1

res = ''
while rest > 0:
    if s[si] == t[ti]:
        res = s[si] + res
        si -= 1
        ti -= 1
        rest -= 1
    elif dp[si + 1][ti + 1] == dp[si + 1][ti]:
        ti -= 1
    else:
        si -= 1
print(res)