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: Runtime Error

Solution code:
X = input()
Y = input()

def optLCSPath(s1, s2):
    memo = {}
    parents = {}
    def helper(i, j):
        if (i, j) in memo:
            return memo[(i, j)]
        if i < 0 or j < 0:
            return 0
        if s1[i] == s2[j]:
            f = 1 + helper(i-1, j-1)
            parents[(i, j)] = (i-1, j-1)
        else:
            c1 = helper(i-1, j)
            c2 = helper(i, j-1)
            f = max(c1, c2)
            if c1 < c2:
                parents[(i, j)] = (i, j-1) # decremented j
            else:
                parents[(i, j)] = (i-1, j) # decremented i
        memo[(i, j)] = f
        return f
    l = helper(len(s1) - 1, len(s2) - 1)
    lcs = []
    start = (len(s1) - 1, len(s2) - 1)

    while start in memo:
        if s1[start[0]] == s2[start[1]]:
            lcs.append(s1[start[0]])
        start = parents[start]
    return ''.join(reversed(lcs))
print(optLCSPath(X,Y))

Submission status: Runtime Error

Solution code:
X = input()
Y = input()
def lcs(s1, s2):
    memo = {}
    parents = {}
    def helper(i, j):
        if (i, j) in memo:
            return memo[(i, j)]
        if i < 0 or j < 0:
            return 0
        if s1[i] == s2[j]:
            f = 1 + helper(i-1, j-1)
        else:
            c1 = helper(i-1, j)
            c2 = helper(i, j-1)
            f = max(c1, c2)
        memo[(i, j)] = f
        return f
    l = helper(len(s1) - 1, len(s2) - 1)
    lcs = []
    s = max(memo.keys(), key=lambda x: memo[x])
    while s in memo:
        i, j = s
        if s1[i] == s2[j]:
            lcs.append(s1[i])
            s = (i-1, j-1)
        else:
            left = (i-1, j) in memo
            up = (i, j-1) in memo
            if left and up:
                if memo[i-1, j] > memo[i, j-1]:
                    s = (i-1, j)
                else:
                    s = (i, j-1)
            elif left:
                s = (i-1, j)
            elif up:
                s = (i, j-1)
            else:
                break
    return ''.join(lcs[::-1])
print(lcs(X, Y))

Submission status: Runtime Error

Solution code:
X = input()
Y = input()
def lcs(s1, s2):
    memo = {}
    parents = {}
    def helper(i, j):
        if (i, j) in memo:
            return memo[(i, j)]
        if i < 0 or j < 0:
            return 0
        if s1[i] == s2[j]:
            f = 1 + helper(i-1, j-1)
        else:
            c1 = helper(i-1, j)
            c2 = helper(i, j-1)
            f = max(c1, c2)
        memo[(i, j)] = f
        return f
    l = helper(len(s1) - 1, len(s2) - 1)
    lcs = []
    s = (len(s1) - 1, len(s2) - 1)
    while s in memo:
        i, j = s
        if s1[i] == s2[j]:
            lcs.append(s1[i])
            s = (i-1, j-1)
        elif (i-1, j) and (i, j-1) in memo:
            if memo[i-1, j] > memo[i, j-1]:
                s = (i-1, j)
            else:
                s = (i, j-1)
        else:
            break
    return ''.join(lcs[::-1])
print(lcs(X, Y))

Submission status: Runtime Error

Solution code:
# coding:utf-8

import sys

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


s = [ord(n) for n in S()]
t = [ord(n) for n in S()]

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

# 最長共通部分列の長さ
# print(dp[-1][-1])

ans = ''
i = len(s)
for j in range(len(t) + 1)[::-1]:
    if dp[i][j] != dp[i][j - 1]:
        while dp[i][j] == dp[i - 1][j]:
            i -= 1
        ans += chr(t[j - 1])
        i -= 1

print(ans[::-1])

Submission status: Runtime Error

Solution code:
a = list(input())
b = list(input())

k = max(len(a),len(b))

dp = [[0]*(len(b)+1) for i in range(len(a)+1)]

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

ans = ''
def rec(m,n):
	if m == 0 or n == 0:
		return ans
	if a[m-1] == b[n-1]:
		global ans
		ans += a[m-1]
		rec(m-1,n-1)
	elif dp[m-1][n] > dp[m][n-1]:
		rec(m-1,n)
	else:
		rec(m,n-1) 

rec(len(a),len(b))
print(ans[::-1])

Submission status: Runtime Error

Solution code:
a = list(input())
b = list(input())

k = max(len(a),len(b))

dp = [[0]*(len(b)+1) for i in range(len(a)+1)]

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

ans = ""

def rec(m,n):
	if m == 0 and n == 0:
		return ans
	if a[m-1] == b[n-1]:
		global ans
		ans += a[m-1]
		rec(m-1,n-1)
	elif dp[m-1][n] > dp[m][n-1]:
		rec(m-1,n)
	else:
		rec(m,n-1) 

rec(len(a),len(b))
print(ans[::-1])

Submission status: Runtime Error

Solution code:
a = list(map(input()))
b = list(map(input()))

k = max(len(a),len(b))

dp = [['']*(len(b)+1) for i in range(len(a))]

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

global ans = ""

def rec(m,n):
	if m == 0 and n == 0:
		return ans
	if a[m-1] == b[n-1]:
		ans += a[m]
		rec(m-1.n-1)
	elif dp[m-1][n] > dp[m][n-1]:
		rec(m-1,n)
	else:
		rec(m,n-1) 

rec(len(a),len(b))
print(ans)

Submission status: Runtime Error

Solution code:
def solve(a, b):
	if a < 0 or b < 0:
		return ''
	if dp[a][b] != '-1':
		return dp[a][b]
	if s[a] == t[b]:
		dp[a][b] = solve(a-1, b-1) + s[a]
	else:
		string1 = solve(a-1, b)
		string2 = solve(a, b-1)
		if len(string1) > len(string2):
			dp[a][b] = string1
		else:
			dp[a][b] = string2
	return dp[a][b]

s = raw_input()
t = raw_input()
dp = [['-1' for i in xrange(len(t))] for j in xrange(len(s))]
print solve(len(s)-1, len(t)-1)

Submission status: Runtime Error

Solution code:
s=input()
t=input()
ls,lt=len(s),len(t)
dp=[['']*(ls+1) for i in range(lt+1)]
for i in range(lt):
    for j in range(ls):
        if t[i]==s[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[-1][-1])

Submission status: Runtime Error

Solution code:

def 解():
    sS = input().rstrip()
    sT = input().rstrip()
    iS = len(sS)
    iT = len(sT)

    dp = [[0]*(iT+1) for _ in range(iS+1)]
    for i in range(iS):
        for j in range(iT):
            if sS[i] == sT[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])
    iC = dp[iS][iT]
    aR = [""]*iC
    i = iS
    j = iT
    Q = []

    def findS(i,j):
        iC = dp[i][j]
        if iC == 0 or aR[iC-1] != "":
            return False
        if dp[i][j] == dp[i-1][j] + 1 == dp[i][j-1] +1 :
            t = dp[i][j]
            aR[t-1] = sS[i-1]
            findS(i-1,j-1)
        else:
            findS(i-1,j)
            findS(i,j-1)
    findS(i,j)
    print("".join(aR))
解()

Submission status: Runtime Error

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(ls):
  for j in range(lt):
    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=""
def rec(i,j):
  if i==0 or j==0:
    return 
  global ans
  if s[i-1]==t[j-1]:
    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)

Submission status: Runtime Error

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(ls):
  for j in range(lt):
    dp[i+1][j+1]=max(dp[i][j]+(s[i]==t[j]),dp[i+1][j],dp[i][j+1])

ans=""
def rec(i,j):
  if i==0 or j==0:
    return 
  global ans
  if s[i-1]==t[j-1]:
    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)

Submission status: Runtime Error

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(ls):
  for j in range(lt):
    dp[i+1][j+1]=max(dp[i][j]+(s[i]==t[j]),dp[i+1][j],dp[i][j+1])

ans=""
def rec(i,j):
  if i==0 and j==0:
    return 
  global ans
  if s[i-1]==t[j-1]:
    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)

Submission status: Runtime Error

Solution code:
def longest(l):
    am = 0
    for i in range(len(l)):
        if len(l[i]) > len(l[am]):
            am = i
    return am

def get_ss(s, t, i, j, mem):
    if (i, j) in mem:
        return mem[(i, j)]

    mem[(i, j)] = ''.join(longest_ss(s, t, i, j, mem))
    return mem[(i, j)]

def longest_ss(s, t, i, j, mem):
    if i == -1 or j == -1:
        mem[(i, j)] = []
        return []
    
    jm1 = get_ss(s, t, i, j - 1, mem)
    im1 = get_ss(s, t, i - 1, j, mem)
    m1 = get_ss(s, t, i - 1, j - 1, mem)

    if s[i] == t[j]:
        #m1.append(s[i])
        m1 = m1 + s[i]

    opt = [jm1, im1, m1]
    am = longest(opt)
    mem[(i, j)] = opt[am]

    return opt[am]

mem = {}
s = raw_input()
t = raw_input()
print("".join(longest_ss(s, t, len(s) - 1, len(t) - 1, mem)))

Submission status: Runtime Error

Solution code:
s = input()
t = input()
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
		elif 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, j = len(s), len(t)

while i > 0 or j > 0:
	#if dp[i][j] == dp[i-1][j-1] + 1:
	if s[i-1] == t[j-1]:
		ans += s[i-1]
		i, j = i-1, j-1
	elif dp[i][j-1] >= dp[i-1][j]:
		j -= 1
	else:
		i -= 1

print(ans[::-1])

Submission status: Runtime Error

Solution code:
S = input()
T = input()
N = len(S)
M = len(T)

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

for i in range(N):
    for j in range(M):
        if S[i] == T[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

ans = ''
def rec(i,j):
    print(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: Runtime Error

Solution code:
#出典
#http://d.hatena.ne.jp/mzp/20100623/lcs
#ここから完全にコピペしました
def maxBy(f, x, y):
    if f(x) > f(y):
        return x
    else:
        return y

table = { ("","") : "" }

def lcs(xs,ys):
    if (xs,ys) in table:
        return table[(xs,ys)]

    ret = ""
    if xs == "" or ys == "":
        ret = ""
    elif xs[-1] == ys[-1]:
        ret = lcs(xs[:-1],ys[:-1]) + xs[-1]
    else:
        ret = maxBy(len,
                    lcs(xs[:-1],ys),
                    lcs(xs,ys[:-1]))
    table[(xs,ys)] = ret
    return ret
S=input()
T=input()
print(lcs(S,T))

Submission status: Runtime Error

Solution code:
def maxBy(f, x, y):
    if f(x) > f(y):
        return x
    else:
        return y


table = {("", ""): ""}


def lcs(xs, ys):
    if (xs, ys) in table:
        return table[(xs, ys)]

    ret = ""
    if xs == "" or ys == "":
        ret = ""
    elif xs[-1] == ys[-1]:
        ret = lcs(xs[:-1], ys[:-1]) + xs[-1]
    else:
        ret = maxBy(len,
                    lcs(xs[:-1], ys),
                    lcs(xs, ys[:-1]))
    table[(xs, ys)] = ret
    return ret


s = input()
t = input()

c = lcs(s, t)
print(c)

Submission status: Runtime Error

Solution code:
s = input()
t = input()
dp = [0]
lcs = ['']
for b in t:
    search_idx = 0
    ncs = lcs.copy()
    for i, curr_idx in enumerate(dp):
        char_idx = s.find(b, search_idx)
        if char_idx == -1:
            break
        next_idx = char_idx + 1
        if next_idx < curr_idx:
            dp[i] = next_idx
            ncs[i] = lcs[i - 1] + b
        search_idx = curr_idx
    else:
        char_idx = s.find(b, search_idx)
        if char_idx > -1:
            dp.append(char_idx + 1)
            ncs.append(lcs[-1] + b)
    lcs = ncs
print(lcs[-1])

Submission status: Runtime Error

Solution code:
#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-

def maxBy(f, x, y):
    if f(x) > f(y):
        return x
    else:
        return y

table = { ("","") : "" }

def lcs(xs,ys):
    if (xs,ys) in table:
        return table[(xs,ys)]

    ret = ""
    if xs == "" or ys == "":
        ret = ""
    elif xs[-1] == ys[-1]:
        ret = lcs(xs[:-1],ys[:-1]) + xs[-1]
    else:
        ret = maxBy(len,
                    lcs(xs[:-1],ys),
                    lcs(xs,ys[:-1]))
    table[(xs,ys)] = ret
    return ret


s = input()
t = input()
print (lcs(s, t))

Submission status: Runtime Error

Solution code:
S = input()
T = input()
LS = len(S); LT = len(T)

memo = [[-1]*LT for i in range(LS)]
nxt = [[(0, None, None)]*(LT+1) for i in range(LS+1)]
def dfs(i, j):
    if i == LS or j == LT:
        return 0
    if memo[i][j] != -1:
        return memo[i][j]
    r0 = dfs(i+1, j); r1 = dfs(i, j+1)
    r = max(r0, r1)
    x = (0, i, j+1) if r0 < r1 else (0, i+1, j)
    if S[i] == T[j]:
        r2 = dfs(i+1, j+1) + 1
        if r < r2:
            r = r2
            x = (1, i+1, j+1)
    memo[i][j] = r
    nxt[i][j] = x
    return r

dfs(0, 0)
i = j = 0
ans = []
while i is not None:
    m, i0, j = nxt[i][j]
    if m:
        ans.append(S[i])
    i = i0
print(*ans, sep='')