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



Sample input:
axyb
abyxb


Sample output:
axb

Submission status: Accepted

Solution code:
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-1][j], dp[i][j-1])
#print(dp)

str = ''
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)

Submission status: Accepted

Solution code:
s = input()
n = len(s)

t = input()
m = len(t)

dp = tuple([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])

rest = dp[n][m]
ans = ''

i = n
j = m
while rest > 0:
    if s[i - 1] == t[j - 1]:
        ans = s[i - 1] + ans
        rest -= 1
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1
print(ans)

Submission status: Accepted

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

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

# dp[i][j] = longest substring of S[:i] and T[:j]

for i in range(1,len(S)+1):
    for j in range(1,len(T)+1):
        sc = S[i-1]
        tc = T[j-1]

        c = 0

        if dp[i-1][j] > dp[i][j]:
            dp[i][j] = dp[i-1][j]
            c = 1
        if dp[i][j-1] > dp[i][j]:
            dp[i][j] = dp[i][j-1]
            c = 2
        if sc == tc and 1 + dp[i-1][j-1] > dp[i][j]:
            dp[i][j] = 1 + dp[i-1][j-1]
            c = 3
        moves[i][j] = c

s = ""

cur = [len(S), len(T)]
while cur != [0, 0]:
    
    move = moves[cur[0]][cur[1]]
    if move == 3:
        s += S[cur[0]-1]
        cur[0] -= 1
        cur[1] -= 1
    elif move == 2:
        cur[1] -= 1
    elif move == 1:
        cur[0] -= 1
    else:
        break


print(s[::-1])

Submission status: Accepted

Solution code:
s,t=input(),input()
ls,lt=len(s),len(t)
dp=[[0 for _ in range(lt+1)] for _ in range(ls+1)]
for i in range(ls):
    for j in range(lt):
        if s[i]==t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j],dp[i+1][j+1])
        dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j+1])
#print(dp[ls][lt])

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

Submission status: Accepted

Solution code:
s,t =input(),input()
inf = float('inf')
dp =[[0 for _ in range(3100)] for _ in range(3100)]
#DPループ
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):
    # (i - 1, j) -> (i, j)と更新されていた場合
    if (dp[i][j] == dp[i - 1][j]):
        i -= 1  # DP の遷移を遡る
    # (i, j - 1) -> (i, j)と更新されていた場合
    elif (dp[i][j] == dp[i][j - 1]):
        j -= 1  # DP の遷移を遡る
    # (i - 1, j - 1) -> (i, j)と更新されていた場合
    else:
        res = s[i - 1] + res  # このときs[i - 1] == t[j - 1]なので、t[j - 1] + resでもOK
        i -= 1
        j -= 1  # DPの遷移を遡る
print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

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

    # そこまでの最大の長さ
    dp_table_2 = [[0 for _ in range(len(s))] for _ in range(len(t))]
    # init:
    ume = 0
    for i in range(len(s)):
        if t[0] == s[i]:
            ume = 1
        dp_table_2[0][i] = ume
    ume = 0
    for i in range(len(t)):
        if t[i] == s[0]:
            ume = 1
        dp_table_2[i][0] = ume

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

    # print(dp_table_2)

    # print(dp_table_2[len(t)-1][len(s)-1])

    # 復元
    i = len(t) - 1
    j = len(s) - 1
    ans = ''
    while i >= 0 and j >= 0:
        if i == 0 and j == 0:
            if dp_table_2[0][0] > 0:
                ans += s[0]
            break
        if j == 0:
            if dp_table_2[i][j] != dp_table_2[i-1][j]:
                ans += t[i]
            i -= 1
            continue
        if i == 0:
            if dp_table_2[i][j] != dp_table_2[i][j-1]:
                ans += s[j]
            j -= 1
            continue
        if dp_table_2[i][j] != dp_table_2[i][j-1] and dp_table_2[i][j] != dp_table_2[i-1][j]:
            ans += t[i]
            i -= 1
            j -= 1
        elif dp_table_2[i][j] != dp_table_2[i][j-1]: 
            i -= 1
        elif dp_table_2[i][j] != dp_table_2[i-1][j]: 
            j -= 1
        else:
            j -= 1

    print(ans[::-1])

main()

Submission status: Accepted

Solution code:
def main():

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

    for i in range(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][j+1], dp[i+1][j])

    i, j = m, n
    ans = ""
    while i > 0 and j > 0:
        if s[i-1] == t[j-1]:
            ans += s[i-1]
            i -= 1
            j -= 1
        elif dp[i][j-1] > dp[i-1][j]:
            j -= 1
        else:
            i -= 1
    return ans[::-1]


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

Submission status: Accepted

Solution code:
from io import StringIO


UP = 0
LEFT = 1
LEFTUP = 2


def lcs(s, t):
    m = len(s)
    n = len(t)
    # dp[i][j] = LCS-length of (s[:i], t[:j])
    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[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])
    buf = StringIO()
    i = m
    j = n
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        elif dp[i][j] == dp[i - 1][j - 1] + 1:
            buf.write(s[i - 1])
            i -= 1
            j -= 1
    buf.seek(0)
    ans = buf.read()[::-1]
    return ans


if __name__ == "__main__":
    print(lcs(input(), input()))

Submission status: Accepted

Solution code:
import numpy as np
 
t = np.array(list(input()), dtype='U1')
s = np.array(list(input()), dtype='U1')
 
ls = len(s)
lt = len(t)
 
eq = s[:, None] == t[None, :]
dp = [np.zeros(lt+1, dtype=np.int16)]
 
# solve
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)
 
# print([list(line) for line in dp])
 
# restore
l = dp[-1][-1]
res = ''
i, j = ls, lt
while i > 0 and j > 0:
    if eq[i-1][j-1]:
        res += s[i-1]
        i, j = i-1, j-1
        continue
    
    if dp[i-1][j] > dp[i][j-1]:
        i -= 1
    else:
        j -= 1
 
print(res[::-1])

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
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]=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,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:
        i-=1
        j-=1
        ans.append(s[i])
ans.reverse()
print("".join(ans))

Submission status: Accepted

Solution code:
s = 'S' + input()
t = 'T' + input()

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

Submission status: Accepted

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


dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]
#dp[s][t]はs文字とt文字までのやつ

for sx in range(len(s)):
    for ty in range(len(t)):
        #sx+1文字目とty+1文字目が同じなら
        if s[sx]==t[ty]:dp[sx+1][ty+1]=dp[sx][ty]+1
        #違うならどっちか一つ削ったのと同じ
        else:dp[sx+1][ty+1]=max(dp[sx+1][ty],dp[sx][ty+1])


ans=''
i=len(s)
j=len(t)
while(i>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]+ans
        i-=1
        j-=1
print(ans)

Submission status: Accepted

Solution code:
s=input()
t=input()
S=len(s)
T=len(t)
dp=[[0]*(T+1) for _ in range(S+1)]
for i in range(1,S+1):
    for j in range(1,T+1):
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
ans=""
x=S
y=T
l=dp[-1][-1]
while len(ans)<dp[-1][-1]:
    if dp[x][y-1]==l:
        y-=1
    elif dp[x-1][y]==l:
        x-=1
    else:
        ans+=t[y-1]
        x-=1
        y-=1
        l-=1
print(ans[::-1])

Submission status: Accepted

Solution code:
s1 = input()
s2 = input()
n = len(s2);    m = len(s1)
dp = [[0 for i in range(m+1)] for i in range(n+1)]
for i in range(n):
    for j in range(m):
        if s2[i] == s1[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])
# for i in range(n+1):
#     if i == 0:
#         print("   ", *s1)
#         print(" ", *dp[i])
#     else:
#         print(s2[i-1], *dp[i])
# print(dp[n][m])
i = n;  j = m
ind = ''
while i > 0 and j > 0:
    if dp[i][j] != dp[i-1][j] and dp[i][j] != dp[i][j-1]:
        ind = s1[j-1]+ind;  i -= 1; j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1
print(ind)

Submission status: Accepted

Solution code:
# have to run on PyPy3
ABOVE,LEFT,UPPERLEFT=1,2,3
s = str(input())
t = str(input())
ls = len(s)
lt = len(t)
dp = [[0 for j in range(lt+2)] for i in range(ls+2)]
memo = [[0 for j in range(lt+2)] for i in range(ls+2)] #from ... ABOVE=1; LEFT=2; UPPERLEFT=3;
for i in range(ls+1):
    for j in range(lt+1):
        if i<ls and j<lt and s[i] == t[j]: #short-circuit
            dp[i+1][j+1] = dp[i][j] + 1
            memo[i+1][j+1] = UPPERLEFT
        if dp[i+1][j] < dp[i][j]:
            dp[i+1][j] = dp[i][j]
            memo[i+1][j] = ABOVE
        if dp[i][j+1] < dp[i][j]:
            dp[i][j+1] = dp[i][j]
            memo[i][j+1] = LEFT

result=""
row,column=ls,lt
while(memo[row][column]!=0):
    if memo[row][column] == ABOVE:
        row -= 1
    elif memo[row][column] == LEFT:
        column -= 1
    elif memo[row][column] == UPPERLEFT:
        result = s[row-1]+result
        row -= 1
        column -= 1
print(result)

Submission status: Accepted

Solution code:
def p_f():
    S = input()
    T = input()
    s_n = len(S)
    t_n = len(T)
    dp = [[0] * (s_n + 1) for _ in range(t_n + 1)]

    for i in range(1, t_n + 1):
        f = False
        for j in range(1, s_n + 1):
            if S[j - 1] == T[i - 1]:
                f = True
                dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i - 1][j])
                continue

            if f:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]

    ans = ""
    while s_n > 0 and t_n > 0:
        if dp[t_n - 1][s_n] == dp[t_n][s_n]:
            t_n -= 1

        if dp[t_n][s_n - 1] == dp[t_n][s_n]:
            s_n -= 1

        if dp[t_n - 1][s_n] != dp[t_n][s_n] and dp[t_n][s_n - 1] != dp[t_n][s_n]:
            ans = S[s_n - 1] + ans
            s_n -= 1
            t_n -= 1

    print(ans)


if __name__ == '__main__':
    p_f()

Submission status: Accepted

Solution code:
s, t = 'd'+input(), 'd'+input()
n, m = len(s)-1, len(t)-1

# 1-indexed

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

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

ans = ""
i, j = n, m
while i != 0 and j != 0:
    if s[i] == t[j] and memo[i][j]-1 == memo[i-1][j-1]:
        ans += s[i]
        i -= 1
        j -= 1
    elif memo[i][j] == memo[i-1][j]:
        i -= 1
    elif memo[i][j] == memo[i][j-1]:
        j -= 1

print(ans[::-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
from copy import *

s, t = input(), input()
ls, lt = len(s), len(t)
dp = [[0] * (lt+1) for i in range(ls+1)]
for i, x in enumerate(s, 1):
    for j, y in enumerate(t, 1):
        if x == y:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
ans = ''
while 0 < dp[i][j]:
    if dp[i-1][j] == dp[i][j]:
        i -= 1
    elif dp[i][j-1] == dp[i][j]:
        j -= 1
    else:
        i -= 1
        j -= 1
        ans += s[i]
print(ans[::-1])

Submission status: Accepted

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

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

    lenS = len(S)
    lenT = len(T)

    dp = [[0] * (lenT + 1) for _ in range(lenS + 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 = []
    now = dp[lenS][lenT]
    i = lenS
    j = lenT
    while now > 0:
        if dp[i - 1][j] == now:
            i -= 1
        elif dp[i][j - 1] == now:
            j -= 1
        else:
            ans.append(S[i - 1])
            i -= 1
            j -= 1
            now -= 1

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

sol()

Submission status: Accepted

Solution code:
s = input()
t = input()
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(1, len(s) + 1):
  for j in range(1, len(t) + 1):
    if s[i - 1] == t[j - 1]:
      dp[i][j] = max(dp[i][j], dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + 1)
    else:
      dp[i][j] = max(dp[i][j], dp[i - 1][j], dp[i][j - 1])
u = []
while True:
  if dp[i][j] == 0:
    break
  elif dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    u.append(s[i - 1])
    i -= 1
    j -= 1
print(''.join(u[::-1]))

Submission status: Accepted

Solution code:
s1=input()
s2=input()
dp=[0]*(len(s1)+1)
dp[0]=[0]*(len(s2)+1)
for i in range(1,len(s1)+1):
	dp[i]=[0]*(len(s2)+1)
	for j in range(1,len(s2)+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])
# for i in range(len(s1)+1):
# 	print(dp[i])
s=""
i,j=len(s1),len(s2)
while(i>0 and j>0):
	if s1[i-1]==s2[j-1]:
		s+=s1[i-1]
		i-=1
		j-=1
	elif dp[i][j-1]>dp[i-1][j]:
		j-=1
	else:
		i-=1
print(s[::-1])

Submission status: Accepted

Solution code:
# AtCoder DP Task F - LCS
def backtrack(C, A, B, i, j):
    out = ""
    while i != 0 and j != 0:
        if A[i - 1] == B[j - 1]:
            out = A[i - 1] + out
            i -= 1
            j -= 1
        elif C[i][j - 1] > C[i - 1][j]:
            j -= 1
        else:
            i -= 1
    return out

def lcs(A, B):
    a, b = len(A), len(B)
    C = [ [0] * (b + 1) for _ in range(a + 1) ]
    for i in range(1, a + 1):
        for j in range(1, b + 1):
            if A[i - 1] == B[j - 1]:
                C[i][j] = C[i-1][j-1] + 1
            else:
                C[i][j] = max(C[i][j - 1], C[i - 1][j])
#    return C[a][b]
    ret = backtrack(C, A, B, a, b)
    return ret

assert lcs("XMJYAUZ", "MZJAWXU") == "MJAU"
assert lcs("MZJAWXU", "XMJYAUZ") == "MJAU"
assert lcs("AGCAT", "GAC") == "AC"
assert lcs("AAAA", "AAAA") == "AAAA"
assert lcs("a", "z") == ""

if False:
    import random
    for _ in range(1000):
        q = [chr(random.randint(ord('a'), ord('z'))) for _ in range(random.randint(1, 1000))]
        p = [chr(random.randint(ord('a'), ord('z'))) for _ in range(random.randint(1, 1000))]
        lcs("".join(q), "".join(p))

x = input().strip()
y = input().strip()
ans = lcs(x, y)
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i 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])
result = ''
i = slen
j = tlen
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:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)

Submission status: Accepted

Solution code:
import decimal,math
from collections import Counter,defaultdict
from fractions import gcd
from bisect import bisect_right,bisect_left
decimal.getcontext().prec = 100
 
s = (raw_input())
t = (raw_input())
n=len(s)
m=len(t)
dp=[]
for i in range(n+1):
	lp=[]
	for j in range(m+1):
		lp.append(0)
	dp.append(lp)
# ans=""	
for i in range(0,n+1):
	for j in range(0,m+1):
		if(i==0 or j==0):
			continue
		if(s[i-1]==t[j-1]):
			dp[i][j]=1+dp[i-1][j-1]
			# ans=ans+s[i-1]
		else:
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])
			# if(dp[i][j]==dp[i-1][j]):
			# 	ans=ans+s[i-1]
			# else:
			# 	ans=ans+t[j-1]
ii = dp[n][m]
ans=""
i=n
j=m
while(i>0 and j>0):
	if(s[i-1]==t[j-1]):
		ans=ans+s[i-1]
		i=i-1
		j=j-1
	elif(dp[i-1][j]>dp[i][j-1]):
		i=i-1
	else:	
		j=j-1	
print ans[::-1]

Submission status: Accepted

Solution code:
def S(): return input()


def main():
    s = [ord(c) - 97 for c in S()]
    t = [ord(c) - 97 for c in S()]
    sl = len(s)
    tl = len(t)
    rr = [[0] * (tl) for _ in range(sl)]
    t0 = t[0]
    for i in range(sl):
        if s[i] == t0:
            for k in range(i,sl):
                rr[k][0] = 1
            break

    rr0 = rr[0]
    s0 = s[0]
    for j in range(tl):
        if s0 == t[j]:
            for k in range(j,tl):
                rr0[k] = 1
            break

    ta = [(i,t[i]) for i in range(1, tl)]
    for i in range(1, sl):
        rri = rr[i]
        rri1 = rr[i-1]
        si = s[i]
        for j, tj in ta:
            if si == tj:
                rri[j] = rri1[j-1] + 1
            else:
                rri[j] = rri1[j]
                if rri[j] < rri[j-1]:
                    rri[j] = rri[j-1]

    i = sl-1
    j = tl-1
    r = []
    while i >= 0 and j >= 0:
        if s[i] == t[j]:
            r.append(s[i] + 97)
            i -= 1
            j -= 1
            continue
        if rr[i][j] == 0:
            break
        if i > 0 and rr[i-1][j] == rr[i][j]:
            i -= 1
        else:
            j -= 1

    return ''.join(map(chr,r[::-1]))


print(main())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
S = np.array(list(input().rstrip()), dtype='U1')
T = np.array(list(input().rstrip()), dtype='U1')

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

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

dp = [np.zeros(LT+1, dtype=np.int16)]

for i in range(LS):
    prev = dp[-1]
    x = prev.copy()
    np.maximum(x[1:], prev[:-1] + equal[i] * 1, out = x[1:])
    np.maximum.accumulate(x, out = x)
    dp.append(x)

x = LS
y = LT
rev_ans = []

while x >= 1 and y >= 1:
    if equal[x-1][y-1]:
        rev_ans.append(str(S[x-1]))
        x -= 1
        y -= 1
        continue
    n1 = dp[x-1][y]
    n2 = dp[x][y-1]
    if n1 < n2:
        y -= 1
        continue
    x -= 1
    continue

answer = ''.join(rev_ans[::-1])

print(answer)

Submission status: Accepted

Solution code:
s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i 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 + 1][j + 1], dp[i][j] + 1, dp[i + 1][j], dp[i][j + 1])
    else:
      dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1])
result = ''
i = slen
j = tlen
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:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)