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:
def main():
    s = input()
    t = input()
    v = [0] * (len(t) + 1)
    dp = [v]
    for i, si in enumerate(s, 1):
        u, v = v, v.copy()
        dp.append(v)
        ll, ul = 0, 0
        for j, ti in enumerate(t, 1):
            uu = u[j]
            if si == ti:
                v[j] = ll = ul + 1
            else:
                if ll > uu:
                    v[j] = ll
                else:
                    ll = uu
            ul = uu
    k = dp[i][j]
    r = ''
    while k:
        if dp[i - 1][j] == k:
            i -= 1
        elif dp[i][j - 1] == k:
            j -= 1
        else:
            k -= 1
            i -= 1
            j -= 1
            r += s[i]
    print(r[::-1])

main()

Submission status: Accepted

Solution code:
import numpy as np

s = np.array(list(input()), np.unicode)
sl = len(s)
t = np.array(list(input()), np.unicode)
tl = len(t)
equal = (s[:, None] == t[None, :])

dp = [np.zeros(tl + 1, np.int32)]
for i in range(sl):
    tmp = dp[-1].copy()
    np.maximum(tmp[1:], tmp[:-1] + equal[i], out=tmp[1:])
    np.maximum.accumulate(tmp, out=tmp)
    dp.append(tmp)

answer = ''
while sl > 0 and tl > 0:
    if s[sl - 1] == t[tl - 1]:
        sl -= 1
        tl -= 1
        answer += s[sl]
        continue

    if dp[sl - 1][tl] > dp[sl][tl - 1]:
        sl -= 1
    else:
        tl -= 1

print(answer[::-1])

Submission status: Accepted

Solution code:
s=input()
t=input()
ma=0
a=[0,0]
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):
        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],1+dp[i-1][j-1])
i=len(s)
j=len(t)

ss=""
while i and j:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ss+=s[i-1]
        i-=1
        j-=1
ss=ss[-1::-1]
print(ss)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def main():
    s = input()[:-1]
    t = input()[:-1]

    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:i+1] == t[j: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])
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])
    
    ans = ""
    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:
            ans = s[i-1:i] + ans
            i -= 1
            j -= 1
    
    # for i in range(S+1):
    #     print(dp[i])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# EDP F-LCS
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)]
#dp[i][j] = s[:i]とt[:j]に置けるLCS
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])

#print(dp)
#print(dp[s_length][t_length])

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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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 loop
        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 = ""

        ## Recover the LCS from DP table
        ## checking the update point
        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()

Submission status: Accepted

Solution code:


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

            #Sのi文字目と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()

Submission status: Accepted

Solution code:
文字列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(答え))

Submission status: Accepted

Solution code:
文字列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(答え))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

ans = ''
# dp[i][j]:sをi文字目、tをj文字目まで見たときの最長部分列長
# dpに最長部分列そのものを持たせたら、TLEしてしまった。
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]
    #print(dp)
#print(dp)
#print(dp[len(s)][len(t)])

# dpを逆にたどって最長部分文字列を復元する
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))))

Submission status: Accepted

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

ans = ''
#dp[i][j]:sをi文字目、tをj文字目まで見たときの最長部分列長
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]
    #print(dp)
#print(dp)
#print(dp[len(s)][len(t)])

# dpを逆にたどって最長部分文字列を復元する
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))))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

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

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

    # restore
    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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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.e. dp[i][j + 1] == dp[i][j]
        i, j = i, j - 1

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

print(ret)

Submission status: Accepted

Solution code:
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.e. dp[i][j + 1] == dp[i][j]
        i, j = i, j - 1

ret = ret_rev[::-1]

print(ret)

Submission status: Accepted

Solution code:
"""
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)
# for i in range(ns+1):
#     print(*dp[i][:ts+1])

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: 
            # print(i,j,cnt, S[i],T[j])
            ans_r += S[i]
            flg = False
            cnt -= 1
print(ans_r[::-1])

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
"""
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)]

    #prev = {}
    # 部分列の最大長さを求める
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if s == t:
                #i番目とｊ番目が同じなら、dp[i+1][j+1]はそれまでの最大長さ＋１
                dp[i+1][j+1] = dp[i][j] + 1
                #prev[(i+1, j+1)] = (i,j)
            else:
                #異なる場合はdp[i][j]かd[i+1][j]かdp[i][j+1]のどれかだけども、後者ふたつがi,jより小さいことはないから後ろ二つの大きいほうを採用
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
                #prev[(i+1, j+1)] = (i+1,j) if dp[i+1][j] >= dp[i][j+1] else (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)


    #TLEなのでやめた
    """
    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()

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
#DPS F LSC 
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])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#EDPC F

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

Submission status: Accepted

Solution code:
# 最長共通部分　LCS ***未完成***
strA = input()
strB = input()
### 一致したら左上+1、そうでない場合は上か左のMAX
# / | 0 | A | B | C | B | A |
# 0 | 0 | 0 | 0 | 0 | 0 | 0 |
# B | 0 | 0 | 1 | 1 | 1 | 1 |
# B | 0 | 0 | 1 | 1 | 2 | 2 |
# A | 0 | 0 | 1 | 1 | 2 | 3 |
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)