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

ans = ''
n, m = len(s), len(t)
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] + ans

print(ans)

Submission status: Accepted

Solution code:
def LCS(S, T):
    ls = len(S)
    lt = len(T)
    S = [-1] + [ord(s) for s in S]
    T = [-2] + [ord(t) for t in T]
    dp = [0]*((ls+1)*(lt+1))
    geta = ls + 1
    for j in range(1, lt+1):
        for i in range(1, ls+1):
            if S[i] == T[j]:
                dp[geta*j + i] = dp[geta*(j-1) + i-1] + 1
            else:
                dp[geta*j + i] = max(dp[geta*(j-1) + i], dp[geta*j + i-1])
    if not dp[-1]:
        return ''
    ans = [0]*dp[-1]
    i, j = ls, lt
    ctr = -1
    for _ in range(ls + lt):
        if i == 0 or j == 0:
            break
        if S[i] == T[j]:
            ans[ctr] = S[i]
            i -= 1
            j -= 1
            ctr -= 1
        elif dp[(j-1)*geta + i] >= dp[j*geta + i-1]:
            j -= 1
        else:
            i -= 1
    return ''.join([chr(a) for a in ans])
s = input().strip()
t = input().strip()
print(LCS(s, t))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

s = input()
t = input()

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

dp = [[0]*(lt+1) for _ in [0]*(ls+1)]

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

L=dp[ls][lt]
ans = [0]*L
idx=L-1
while idx >= 0:
#    print(i,j,idx)
    if i>0 and dp[i-1][j] == dp[i][j]:
        i -= 1
    elif j>0 and dp[i][j-1] == dp[i][j]:
        j-=1
    else:
        i-=1
        j-=1
        ans[idx] = s[i]
        idx -= 1

#print(dp)
print(''.join(ans))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

s = input()
t = input()

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

dp = [[0]*(lt+1) for _ in [0]*(ls+1)]

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

L=dp[ls][lt]
ans = [0]*L
idx=L-1
i=ls
j=lt
while idx >= 0:
#    print(i,j,idx)
    if i>0 and dp[i-1][j] == dp[i][j]:
        i -= 1
    elif j>0 and dp[i][j-1] == dp[i][j]:
        j-=1
    else:
        i-=1
        j-=1
        ans[idx] = s[i]
        idx -= 1

#print(dp)
print(''.join(ans))

Submission status: Accepted

Solution code:
def f():
    s = input()
    t = input()
    ls, lt = len(s), len(t)
    dp = [[0] * (ls + 1) for _ in range(lt + 1)]
    for i in range(lt):
        for j in range(ls):
            if s[j] == t[i]:
                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])
    r = ''
    i += 1
    j += 1
    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:
            r = s[j - 1] + r
            j -= 1
            i -= 1
    return r
 
 
if __name__ == '__main__':
    ans = f()
    print(ans)

Submission status: Accepted

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

# dp = [[[] for _ in range(len(S)+1)] for _ in range(len(T)+1)]
cdp = [[None for _ in range(len(S)+1)] for _ in range(len(T)+1)]
ddp = [[None for _ in range(len(S)+1)] for _ in range(len(T)+1)]
# dp[0] = [[''] for _ in range(len(S)+1)]
cdp[0] = [0 for _ in range(len(S)+1)]
ddp[0] = [0 for _ in range(len(S)+1)]

for i in range(1,len(T)+1):
    for j in range(len(S)+1):
        if j == 0:
            # dp[i][j] = ['']
            cdp[i][j] = 0
            ddp[i][j] = 0
            continue
        if S[j-1] == T[i-1]:
            # dp[i][j] = [p + S[j-1] for p in dp[i-1][j-1]]
            cdp[i][j] = cdp[i-1][j-1] + 1
            ddp[i][j] = 2
        else:
            if cdp[i][j-1] > cdp[i-1][j]:
                # dp[i][j] = dp[i][j-1]
                cdp[i][j] = cdp[i][j-1]
                ddp[i][j] = 1
            else:
                # dp[i][j] = dp[i-1][j]
                cdp[i][j] = cdp[i-1][j]
                ddp[i][j] = 0

# print(dp[-1][-1][0])

i, j = len(T), len(S)
L = ''
while i > 0 and j > 0:
    if ddp[i][j] == 2:
        i -= 1
        j -= 1
        L += T[i]
    elif ddp[i][j] == 1:
        j -= 1
    elif ddp[i][j] == 0:
        i -= 1

print(L[::-1])

Submission status: Accepted

Solution code:
def lcs(a, b):
    n = len(a)
    m = len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
 
    for i in range(n):
        for j in range(m):
            if a[i] == b[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])
 
    lcs_str = ''
    i, j = n, m
    while i >= 1 and j >= 1:
        if a[i - 1] == b[j - 1]:
            lcs_str += a[i - 1] #or b[j - 1]
            i -= 1
            j -= 1
        else:
            if dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1
 
    return lcs_str[::-1]
 
 
s = input()
t = input()
print(lcs(s, t))

Submission status: Accepted

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

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

    # print(max(dp_table[-1]))
    mem_s = len(s)
    mem_t = len(t)
    ans = ""
    while True:
        if dp_table[mem_s][mem_t] == dp_table[mem_s][mem_t-1]:
            mem_t = mem_t - 1
        elif dp_table[mem_s][mem_t] == dp_table[mem_s-1][mem_t]:
            mem_s = mem_s - 1
        else:
        # if dp_table[mem_s][mem_t] == dp_table[mem_s-1][mem_t-1]:
            ans = s[mem_s-1] + ans
            mem_s = mem_s - 1
            mem_t = mem_t - 1
        if mem_s == 0 or mem_t == 0:
            break
    print(ans)

sub()

Submission status: Accepted

Solution code:
S = input()
T = input()
M = len(S)
N = len(T)
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])

M = i
N = j
ans = ''
while i + 1 > 0 and j + 1 > 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:
        ans = S[i] + ans
        i -= 1
        j -= 1
    
print(ans)

Submission status: Accepted

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

S, T = len(s), len(t)

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def mi(): return map(int, input().split())


def li(): return list(mi())


def li_(): return [int(x) - 1 for x in input().split()]


def lin(n: int): return [input() for _ in range(n)]


def llin(n: int): return [li() for _ in range(n)]


def llin_(n: int): return [li_() for _ in range(n)]


def lli(): return [list(map(int, l.split())) for l in input()]


def i(): return int(input())


def f(): return float(input())


def s(): return input().replace('\n', '')


def main():
    S = s()
    T = s()
    dp = [[0] * len(T) for _ in range(len(S))]
    dp[0][0] = int(S[0] == T[0])
    check = [[None] * len(T) for _ in range(len(S))]
    ok = (10, 10)
    check[0][0] = ok if dp[0][0] else (0, 0)
    for i in range(1, len(S)):
        if S[i] == T[0]:
            dp[i][0] = 1
            check[i][0] = ok
        else:
            dp[i][0] = dp[i - 1][0]
            check[i][0] = (-1, 0)
    for j in range(1, len(T)):
        if T[j] == S[0]:
            dp[0][j] = 1
            check[0][j] = ok
        else:
            dp[0][j] = dp[0][j-1]
            check[0][j] = (0, -1)
    for i in range(1, len(S)):
        for j in range(1, len(T)):
            if S[i] == T[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                check[i][j] = (-1, -1)
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                if dp[i - 1][j] > dp[i][j - 1]:
                    check[i][j] = (-1, 0)
                else:
                    check[i][j] = (0, -1)

    ans = ""
    i = len(S)-1
    j = len(T)-1
    for _ in range(len(S) + len(T)):
        if check[i][j] == ok:
            ans = S[i] + ans
            break
        else:
            if check[i][j] == (-1, -1):
                ans = S[i] + ans
                tmp = i
                i += check[i][j][0]
                j += check[tmp][j][1]
            else:
                tmp = i
                i += check[i][j][0]
                j += check[tmp][j][1]
    #print(*check, sep="\n")
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import numpy as np
a = input()
b = input()
dp = [[0] * (len(b) + 1)  for i in range(len(a) + 1)]

for x in range(len(a)):
	for y in range(len(b)):
		if a[x] == b[y]:
			dp[x + 1][y + 1] = dp[x][y] + 1
		else:
			dp[x + 1][y + 1] = max(dp[x + 1][y], dp[x][y + 1])
		
x, y = len(a) - 1, len(b) - 1
s = ''
while (x >= 0 and y >= 0):
	if a[x] == b[y]:
		s = a[x] + s
		x -= 1
		y -= 1
	elif dp[x][y + 1] > dp[x + 1][y]:
		x -= 1
	else:
		y -= 1
		
print(s)

Submission status: Accepted

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

len_s = len(s)
len_t = len(t)

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

i = len_s
j = len_t
str = ''

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

s = input()
t = input()

lens = len(s)
lent = len(t)

dp = [[0 for _ in range(lent+1)] for _ in range(lens+1)]

ans_index = []

for i in range(1, lens+1):
    for j in range(1, lent+1):
        if s[i-1] == t[j-1]:
            candidate = max(dp[i-1][j-1]+1, dp[i-1][j], dp[i][j-1])
            if candidate == dp[i-1][j-1]+1:
                dp[i][j] = dp[i-1][j-1]+1
                continue
            elif candidate == dp[i-1][j]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
        else:
            candidate = max(dp[i-1][j], dp[i][j-1])
            if candidate == dp[i-1][j]:
                dp[i][j] = dp[i-1][j]
                continue
            else:
                dp[i][j] = dp[i][j-1]

i, j = lens, lent
ans = ''
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)

Submission status: Accepted

Solution code:
"Template made by : https://codeforces.com/profile/c1729 , github repo : https://github.com/cheran-senthil/PyRival"
from __future__ import division, print_function
import bisect
import math
import itertools
import sys
from atexit import register

if sys.version_info[0] < 3:
    from io import BytesIO as stream
else:
    from io import StringIO as stream


if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip


def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new synchronization setting.

    """
    global input, flush

    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')

        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

def main():
    s=input()
    t=input()
    L=[ [0]*(len(t)+1) for _ in range(len(s)+1) ]
    
    def lcs(s,t):
        n=len(s)
        m=len(t)
        for i in range(0,n+1):
            for j in range(0,m+1):
                if i==0 or j==0:
                    L[i][j]=0
                elif s[i-1]==t[j-1]:
                    L[i][j]=L[i-1][j-1]+1
                else :
                    L[i][j]=max(L[i-1][j],L[i][j-1])
    lcs(s,t)
    ans=[]
    i=len(s)
    j=len(t)
    while L[i][j]!=0:
        if L[i][j]!=L[i-1][j] and L[i][j]!=L[i][j-1]:
            ans.append(s[i-1])
            i-=1
            j-=1
        else :
            if L[i][j]==L[i-1][j]:
                i-=1
                continue
            else :
                j-=1
                continue
    print(''.join(ans[::-1]))
if __name__ == '__main__':
    sync_with_stdio(False)
    main()

Submission status: Accepted

Solution code:
x = input()
y = input()
lx, ly = len(x), len(y)

length = [[0] * (ly + 1) for _ in range(lx + 1)]

for i_x in range(lx):
    for i_y in range(ly):
        if x[i_x] == y[i_y]:
            length[i_x+1][i_y+1] = length[i_x][i_y] + 1
        else:
            length[i_x+1][i_y+1] = max(length[i_x+1][i_y], length[i_x][i_y+1])

lcs = ''
i_x, i_y = lx, ly
while i_x and i_y:
    if x[i_x-1] == y[i_y-1]:
        lcs += x[i_x-1]
        i_x -= 1
        i_y -= 1
    elif length[i_x][i_y-1] > length[i_x-1][i_y]:
        i_y -= 1
    else:
        i_x -= 1

print(lcs[::-1])

Submission status: Accepted

Solution code:
x = input()
y = input()
lx = len(x)
ly = len(y)

chars = [[''] * (ly + 1) for _ in range(lx + 1)]
length = [[0] * (ly + 1) for _ in range(lx + 1)]
prev = [[0b00] * (ly + 1) for _ in range(lx + 1)]

for i_x in range(lx):
    for i_y in range(ly):
        if x[i_x] == y[i_y]:
            length[i_x+1][i_y+1] = length[i_x][i_y] + 1
            chars[i_x+1][i_y+1] = x[i_x]
            prev[i_x+1][i_y+1] = 0b11
        elif length[i_x+1][i_y] > length[i_x][i_y+1]:
            length[i_x+1][i_y+1] = length[i_x+1][i_y]
            prev[i_x+1][i_y+1] = 0b01
        else:
            length[i_x+1][i_y+1] = length[i_x][i_y+1]
            prev[i_x+1][i_y+1] = 0b10

lcs = [''] * length[-1][-1]
i_x, i_y = lx, ly
i = 1
while i_x and i_y:
    if prev[i_x][i_y] == 0b11:
        lcs[-i] = chars[i_x][i_y]
        i += 1
    i_x, i_y = i_x - ((prev[i_x][i_y] & 0b10) >> 1), i_y - (prev[i_x][i_y] & 0b01)

print(''.join(lcs))

Submission status: Accepted

Solution code:
s = input()
t = input()
n,m = len(s),len(t)
dp = [[0]*3010 for i in range(3010)]
for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i+1][j+1]=max(dp[i+1][j+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 = 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:
        res = s[i-1]+res
        i -=1
        j -=1
print(res)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
sList, tList = list(input()), list(input())

dp = [[0] * (len(tList) + 1) for _ in range(len(sList) + 1)]
for i, s in enumerate(sList, start=1):
    sameNum = 0
    for j, t in enumerate(tList, start=1):
        num = dp[i-1][j]
        if s == t:
            sameNum = max(num, dp[i-1][j-1] + 1)
        dp[i][j] = max(num, sameNum)

ans = ""

while(i > 0, j > 0):
    num = dp[i][j]
    if num == 0:
        break
    if sList[i-1] == tList[j-1]:
        ans = sList[i-1] + ans
        i -= 1
        j -= 1
    else:
        if dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1

print(ans)

Submission status: Accepted

Solution code:

sList, tList = input(), input()

dp = [[0] * (len(tList) + 1) for _ in range(len(sList)+1)]


# 横方向で回す
for i, s in enumerate(sList, start=1):
    for j, t in enumerate(tList, start=1):
        dp[i][j] = max([dp[i][j - 1], dp[i-1][j],
                        dp[i-1][j-1] + 1 if s == t else 0])
m = dp[i][j]
ans = ""
# traceback
cnt = 0
while i + j != 0:
    if dp[i - 1][j - 1] == m - 1 and tList[j-1] == sList[i-1]:
        ans = tList[j-1] + ans
        i -= 1
        j -= 1
        m -= 1
    else:
        if dp[i - 1][j] == m:
            i -= 1
        elif dp[i][j-1] == m:
            j -= 1
    cnt += 1
print(ans)

Submission status: Accepted

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

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

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

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
    elif dp[i][j] == dp[i-1][j-1] + 1:
        ans = s[i-1] + ans
        i -=1
        j -=1

print(ans)

Submission status: Accepted

Solution code:
s, t = [input() for _ in range(2)]

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

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

print(ans[::-1])

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

s = stdin.readline().rstrip()
t = stdin.readline().rstrip()

s_len = len(s)
t_len = len(t)

# dp[i][j] : sのi文字目、tのj文字目の時のLCSの長さ
# LCS...Longest-common subsequence（最長共通部分列）
dp = [[0] * (t_len+1) for _ in range(s_len+1)] 

for i in range(s_len):
    for j in range(t_len):
        if s[i] == t[j]:
            # dpテーブルの左上の値から+1したものが最長の長さ
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

# for Debug
"""
print('      ', end='')
print(*t, sep=''  '')
ss = ' ' + s
for i in range(len(dp)):
    print(ss[i], end=' ')
    print(dp[i])
"""


# 結果の文字列の算出
# dp配列を逆からたどってLCSを作成する
# LCSの長さが更新されたときの文字を追加していく
res = ""
while s_len and t_len:
    if dp[s_len][t_len] == dp[s_len-1][t_len]:
        s_len -= 1
    elif dp[s_len][t_len] == dp[s_len][t_len-1]:
        t_len -= 1
    else:
        # 先頭からくっつけていく
        res = s[s_len-1] + res
        s_len -= 1
        t_len -= 1

print(res)

Submission status: Accepted

Solution code:
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 and m:
    if dp[n][m] == dp[n-1][m]:
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    else:
        res = s[n-1]+res
        n -= 1
        m -= 1
print(res)

Submission status: Accepted

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

point = [ [0 for t in range(len(T) + 1)] for _ in range(len(S) + 1)]
path = [ [0 for t in range(len(T) + 1)] for _ in range(len(S) + 1)] #vert 3, right2, slash 1

# dp[point] S seq
for s_index in range(len(S)):
    for t_index in range(len(T)):
        if S[s_index] == T[t_index]:
            point[s_index + 1][t_index + 1] = point[s_index][t_index] + 1
            path[s_index + 1][t_index + 1] = 1
        elif point[s_index + 1][t_index] > point[s_index][t_index + 1] :
            point[s_index + 1][t_index + 1] = point[s_index + 1][t_index]
            path[s_index + 1][t_index + 1] = 3
        else:
            point[s_index + 1][t_index + 1] = point[s_index][t_index + 1]
            path[s_index + 1][t_index + 1] = 2



last_s = len(S) 
last_t = len(T)

ret = ''
while(last_s != 0 and last_t != 0):
    if path[last_s][last_t] == 1:
        ret += S[last_s-1]
        last_s -= 1
        last_t -= 1
    elif path[last_s][last_t] == 2:
        last_s -= 1
    else:
        last_t -= 1

print(ret[::-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

s = input()
t = input()

dp = [[0]*(len(t)+1) for i 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])

ansl = []
cnt = dp[-1][-1]
def tami(i,j):
  global cnt
  if cnt == 0:
    return
  if s[i-1] == t[j-1]:
    cnt -= 1
    ansl.append(i-1)
  if dp[i-1][j-1]==cnt:
    tami(i-1,j-1)
  elif dp[i][j-1]==cnt:
    tami(i,j-1)
  elif dp[i-1][j]==cnt:
    tami(i-1,j)

tami(len(s),len(t))

ans = ""
for i in ansl:
  ans += s[i]
print(ans[::-1])

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
S=input()
T=input()
a=[ord(i) for i in S]
b=[ord(i) for i in T]
N=len(a);M=len(b)
X=[[0 for j in range(M+1)] for i in range(N+1)]
Y=[[0 for j in range(M+1)] for i in range(N+1)]
for i in range(N):
    for j in range(M):
        if a[i]==b[j]:
            X[i+1][j+1]=X[i][j]+1
            Y[i+1][j+1]=0
        elif X[i+1][j]<X[i][j+1]:
            X[i+1][j+1]=X[i][j+1]
            Y[i+1][j+1]=+1
        else:
            X[i+1][j+1]=X[i+1][j]
            Y[i+1][j+1]=-1
c=[]
i=N;j=M
while(i>0 and j>0):
    if Y[i][j]>0:
        i-=1
    elif Y[i][j]<0:
        j-=1
    else:
        c.append(a[i-1])
        i-=1
        j-=1
print("".join([chr(i) for i in c[::-1]]))

Submission status: Accepted

Solution code:
s = input()
t = input()
n, m = len(s), len(t)

T = [[0] * (m + 1) for i in range(n + 1)]
k = 0
for j in range(m):
    if s[0] == t[j]:
        k = 1
    T[0][j] = k

k = 0
for i in range(n):
    if s[i] == t[0]:
        k = 1
    T[i][0] = k

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


i, j = n - 1, m - 1
ans = ''
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        ans += s[i]
        i, j = i - 1, j - 1
    else:
        if T[i - 1][j] > T[i][j - 1]:
            i -= 1
        else:
            j -= 1

print(ans[::-1])

Submission status: Accepted

Solution code:
#!/snap/bin/pypy3

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

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

    print(ans[::-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

dp = [[0]*(lt+1) for i in range(ls+1)]

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

max_len = dp[-1][-1]
#print(max_len)

prev = max_len

ans = ""

i = ls
j = lt

for l in range(max_len):
    while dp[i-1][j] == max_len - l:
        i -= 1
    while dp[i][j-1] == max_len - l:
        j -= 1
    ans += s[i-1]
    i -= 1
    j -= 1
print(ans[::-1])

Submission status: Accepted

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

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

dp = [[0]*(lt+1) for i in range(ls+1)]

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

max_len = dp[-1][-1]
ans = ""

i = ls
j = lt

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

print(ans[::-1])

Submission status: Accepted

Solution code:
import sys

s = sys.stdin.readline().strip()
t = sys.stdin.readline().strip()

s_len = len(s)
t_len = len(t)
dp = [[0 for x in range(t_len + 1)] for y in range(s_len + 1)]


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

ans = ''
i = s_len
j = t_len

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

Submission status: Accepted

Solution code:
s=list(input())
t=list(input())
n = len(s)
m = len(t)
dp=[[0 for i in range(m+1)] for j in range(n+1)]
for i in range(n+1):
    for j in range(m+1):
        if i<n and j<m and s[i]==t[j]:
            dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j+1])
        if j<m:
            dp[i][j+1]=max(dp[i][j],dp[i][j+1])
        if i<n:
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
ans=[]
while(n>0 and m>0):
    if dp[n][m]==dp[n-1][m]:
        n-=1
        continue
    if dp[n][m]==dp[n][m-1]:
        m-=1
        continue
    ans.append(s[n-1])
    n-=1
    m-=1
print("".join(ans[::-1]))

Submission status: Accepted

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

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

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

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

i = n
j = m
ans = ''
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
        continue
    if dp[i][j] == dp[i][j-1]:
        j -= 1
        continue
    i -= 1
    j -= 1
    ans += s[i]

print(ans[::-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)

S = input()
T = input()

N,M = len(S),len(T)

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

ans = ''
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(N,M)
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] = 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 = 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)