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: Wrong Answer

Solution code:
def main():
    import sys
    input=sys.stdin.buffer.readline
    s=input()[:-1]
    t=input()[:-1]
    n,m=len(s),len(t)
    dp=[[0]*-~m for _ in range(n+1)]
    b=dp[0]
    for i,x in enumerate(s,1):
        dpi=dp[i]
        dpib=dpi[0]
        for j,y in enumerate(t,1):
            dpib=dpi[j]=b[j-1]+1if x==y else b[j]if b[j]>dpib else dpib
        b=dpi
    ans=[]
    i,j=n-1,m-1
    while dp[i][j]:
        if dp[i][j]==dp[i-1][j]:
            i-=1
        elif dp[i][j]==dp[i][j-1]:
            j-=1
        else:
            ans.append(s[i-1])
            i-=1
            j-=1
    print(''.join(map(chr,ans))[::-1])
main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    e=enumerate
    s,t=sys.stdin.buffer
    n,m=len(s),len(t)
    dp=[[0]*-~m for _ in range(n+1)]
    b=dp[0]
    for i,x in e(s,1):
        dpi=dp[i]
        c=0
        for j,y in e(t,1):
            dpi[j]=c=b[j-1]+1if x==y else c if c>b[j]else b[j]
        b=dpi
    ans=[]
    i,j=n-1,m-1
    dpi=dp[i]
    while dpi[j]:
        if dpi[j]==dp[i-1][j]:
            i-=1
            dpi=dp[i]
        elif dpi[j]==dpi[j-1]:
            j-=1
        else:
            ans+=s[i-1],
            i-=1
            j-=1
    print(''.join(map(chr,ans))[::-1])
main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys


def solve(s, t):
    dp = [[0 for _ in range(len(s) + 1)] for _ in range(len(t) + 1)]
    for i in range(1, len(t) + 1):
        for j in range(1, min(len(s) + 1, i + 2)):
            if s[j - 1] == t[i - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    print("\n".join(map(str, dp)))
    i = len(t)
    j = len(s)
    selected = []
    while i > 0 and j > 0:
        if t[i - 1] == s[j - 1]:
            selected.append(t[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    print(i, j)
    return "".join(reversed(selected))


def do_job():
    "Do the work"
    s = input()
    t = input()
    result = solve(s, t)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys


def solve(s, t):
    dp = [[0 for _ in range(len(s) + 1)] for _ in range(len(t) + 1)]
    for i in range(1, len(t) + 1):
        for j in range(i - 1, len(s) + 1):
            if s[j - 1] == t[i - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    i = len(t)
    j = len(s)
    selected = []
    while i > 0 and j > 0:
        if t[i - 1] == s[j - 1]:
            selected.append(t[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(selected))


def do_job():
    "Do the work"
    s = input()
    t = input()
    result = solve(s, t)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    s = input().rstrip()
    t = input().rstrip()

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

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

    for i in range(1, n + 1):
        s_ = s[i - 1]
        for j in range(1, m + 1):
            t_ = t[j - 1]
            if s_ != t_:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            else:
                dp[i][j] = dp[i - 1][j - 1] + 1
    ans = []
    while n > 0 and m > 0:
        if dp[n][m] != dp[n - 1][m - 1]:
            ans.append(s[n - 1])
            n -= 1
            m -= 1
        else:
            if dp[n - 1][m] >= dp[n][m - 1]:
                n -= 1
            else:
                m -= 1
    print("".join(ans[::-1]))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)
    
    dp = [[0] * (M+1) for _ in range(N+1)]
    ans = [[''] * (M+1) for _ in range(N+1)]
    
    for i in range(1, N+1):
        p = S[i-1]
        for j in range(1, M+1):
            if T[j-1] == p:
                dp[i][j] = dp[i-1][j] + 1
                ans[i][j] = ans[i-1][j] + p
            else:
                if dp[i][j-1] < dp[i-1][j]:
                    dp[i][j] = dp[i-1][j]
                    ans[i][j] = ans[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1]
                    ans[i][j] = ans[i][j-1]
                
    print(ans[N][M])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def solve(s, t):
    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])
    sol = []
    pr, pc = n, m
    while pr > 0 and pc > 0:
        if dp[pr-1][pc-1] == dp[pr][pc]-1:
            sol.append(s[pr-1])
            pr -= 1
            pc -= 1
        elif dp[pr][pc-1] > dp[pr-1][pc]:
            pc -= 1
        else:
            pr -= 1
    return ''.join(reversed(sol))
  
s = input()
t = input()
print(solve(s, t))

Submission status: Wrong Answer

Solution code:
import os, sys

if sys.platform == 'ios':
  sys.stdin = open(os.path.splitext(__file__)[0] + '.txt')
#sys.setrecursionlimit(10**6)

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

#print(dp[-1][-1])
ans=[]
for i in range(len(s)):
  if dp[i][-1] != dp[i+1][-1]:
    ans.append(s[-1])
print(''.join(ans))

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0]*3300 for i in range(3300)]

for i in range(n+1):
  for j in range(m+1):
    if (i==0 or j==0):
      dp[i][j]=0
      continue
    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-1][j-1]+1,dp[i][j])
rewsna=[]

while (n>=0 and m>=0):
  if (dp[n][m]==dp[n-1][m]):
    n-=1
  if (dp[n][m]==dp[n][m-1]):
    m-=1
  else:
    rewsna.append(t[m-1])
    n-=1
    m-=1

l=len(rewsna)
if l==0:
  print('')
  exit()
print(''.join(rewsna[::-1]))

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
n=len(s)
m=len(t)
#print(n,m)
dp=[[0]*3300 for i in range(3300)]

for i in range(n+1):
  for j in range(m+1):
    if (i==0 or j==0):
      dp[i][j]=0
      continue
    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-1][j-1]+1,dp[i][j])
#print(dp[n][m])  
rewsna=[]
#print(rewsna)
while (n>=0 and m>=0):
  if (dp[n][m]==dp[n-1][m]):
    n-=1
  if (dp[n][m]==dp[n][m-1]):
    m-=1
  else:
    rewsna.append(t[m-1])
    n-=1
    m-=1
    #print(rewsna)
ans=''
l=len(rewsna)
if l==0:
  print('')
  exit()
print(''.join(rewsna[::-1])) 
'''
for i in range(l+1):
  ans+=rewsna[l-i-1]
print(''.join(ans[:-1]))
'''

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
n=len(s)
m=len(t)
#print(n,m)
dp=[[0]*3300 for i in range(3300)]

for i in range(n+1):
  for j in range(m+1):
    if (i==0 or j==0):
      dp[i][j]=0
      continue
    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-1][j-1]+1,dp[i][j])
#print(dp[n][m])  
rewsna=[]
#print(rewsna)
while (n>=0 and m>=0):
  if (dp[n][m]==dp[n-1][m]):
    n-=1
  if (dp[n][m]==dp[n][m-1]):
    m-=1
  else:
    rewsna.append(t[m-1])
    n-=1
    m-=1
    print(rewsna)
ans=''
l=len(rewsna)
if l==0:
  print('')
  exit()
print(''.join(rewsna[::-1])) 
'''
for i in range(l+1):
  ans+=rewsna[l-i-1]
print(''.join(ans[:-1]))
'''

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
n=len(s)
m=len(t)
#print(n,m)
dp=[[0]*3300 for i in range(3300)]

for i in range(n+1):
  for j in range(m+1):
    if (i==0 or j==0):
      dp[i][j]=0
      continue
    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-1][j-1]+1,dp[i][j])
#print(dp[n][m])  
rewsna=[]
#print(rewsna)
while (n>=0 and m>=0):
  if (dp[n][m]==dp[n-1][m]):
    n-=1
  if (dp[n][m]==dp[n][m-1]):
    m-=1
  else:
    rewsna.append(t[m-1])
    n-=1
    m-=1
    #print(rewsna)
ans=[] 
l=len(rewsna)
if l==0:
  print('')
  exit()
for i in range(l+1):
  ans.append(rewsna[l-i-1])
print(''.join(ans[:-1]))

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
n=len(s)
m=len(t)
#print(n,m)
dp=[[0]*3300 for i in range(3300)]

for i in range(n+1):
  for j in range(m+1):
    if (i==0 | j==0):
      dp[i][j]=0
      continue
    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-1][j-1]+1,dp[i][j])
#print(dp[n][m])  
rewsna=''
#print(rewsna)
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:
    rewsna+=s[n-1]
    n-=1
    m-=1
    #print(rewsna)
ans=[] 
l=len(rewsna)
for i in range(l):
  ans.append(rewsna[l-i-1])

Submission status: Wrong Answer

Solution code:
import copy
S = list(input())
T = list(input())
m, n = len(S), len(T)
C = [[[] for j in range(n+1)] for i in range(m+1)]
for i in range(m):
    Ci = copy.deepcopy(C[i])
    for j in range(n):
        if S[i] == T[j]:
            Ci[j].append(S[i])
            C[i+1][j+1] = Ci[j]
        elif len(C[i+1][j]) >= len(C[i][j+1]):
            C[i+1][j+1] = C[i+1][j]
        else:
            C[i+1][j+1] = C[i][j+1]
print(''.join(C[m][n]))

Submission status: Wrong Answer

Solution code:
import copy
S = list(input())
T = list(input())
m, n = len(S), len(T)
C = [[[] for j in range(n+1)] for i in range(m+1)]
for i in range(m):
    Ci = copy.copy(C[i])
    for j in range(n):
        if S[i] == T[j]:
            Ci[j].append(S[i])
            C[i+1][j+1] = Ci[j]
        elif len(C[i+1][j]) >= len(C[i][j+1]):
            C[i+1][j+1] = C[i+1][j]
        else:
            C[i+1][j+1] = C[i][j+1]
print(''.join(C[m][n]))

Submission status: Wrong Answer

Solution code:
import copy
S = list(input())
T = list(input())
m, n = len(S), len(T)
C = [[[] for j in range(n+1)] for i in range(m+1)]
for i in range(m):
    for j in range(n):
        if S[i] == T[j]:
            Cij = C[i][j]
            Cij.append(S[i])
            C[i+1][j+1] = Cij
        elif len(C[i+1][j]) >= len(C[i][j+1]):
            C[i+1][j+1] = C[i+1][j]
        else:
            C[i+1][j+1] = C[i][j+1]
print(''.join(C[m][n]))

Submission status: Wrong Answer

Solution code:
s,t=input(),input()
T,S=len(t),len(s)
dpi=["" for j in range(T+1)]
dpi1=dpi
for i in range(S):
    for j in range(T):
        if s[i]==t[j]:dpi1[j+1]=dpi[j]+s[i]
        else:dpi1[j+1]=max(dpi[j],dpi1[j],dpi[j+1],key=lambda x:len(x))
        dpi=dpi1
print(dpi[T])

Submission status: Wrong Answer

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

ans = ''
dp = [[0]*(lt+1) for _ in range(ls+1)]
for j in range(ls):
    for i in range(lt):
        if s[j]==t[i]:
            dp[j+1][i+1] = dp[j][i]+1
        else:
            dp[j+1][i+1] = max(dp[j+1][i], dp[j][i+1])

if dp[ls][lt] == 0:
    print('')
    exit()

i = lt
j = ls

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

Submission status: Wrong Answer

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

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

dps = [['']*(lt+1) for _ in range(ls+1)]
dpl = [[0]*(lt+1) for _ in range(ls+1)]

for i in range(ls):
    for j in range(lt):
        if s[i]==t[j]:
            dps[i+1][j+1] = dps[i][j]+s[i]
            dpl[i+1][j+1] += 1
            
            if dpl[i+1][j] > dpl[i+1][j+1]:
                dps[i+1][j+1] = dps[i+1][j]
                dpl[i+1][j+1] = dpl[i+1][j]
            
            if dpl[i][j+1] > dpl[i+1][j+1]:
                dps[i+1][j+1] = dps[i][j+1]
                dpl[i+1][j+1] = dpl[i][j+1]
        
        else:
            if dpl[i+1][j] >= dpl[i][j+1]:
                dps[i+1][j+1] = dps[i+1][j]
                dpl[i+1][j+1] = dpl[i+1][j]
            else:
                dps[i+1][j+1] = dps[i][j+1]
                dpl[i+1][j+1] = dpl[i][j+1]

print(dps[ls][lt])

Submission status: Wrong Answer

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

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

for i_s in range(len(s)):
    for i_t in range(len(t)):
        if s[i_s] == t[i_t]:
            dp[i_s+1][i_t+1] = dp[i_s][i_t] + 1
        dp[i_s+1][i_t] = max(dp[i_s+1][i_t], dp[i_s][i_t])
        dp[i_s][i_t+1] = max(dp[i_s][i_t+1], dp[i_s][i_t])

ans = []

i_s = len(s)
i_t = len(t)

while i_s > 0 and i_t > 0:
    if dp[i_s][i_t] == dp[i_s][i_t-1]:
        i_t -= 1
    elif dp[i_s][i_t] == dp[i_s-1][i_t]:
        i_s -= 1
    else:
        ans.append(s[i_s-1])
        i_s -= 1
        i_t -= 1

print("".join(reversed(ans)))

Submission status: Wrong Answer

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

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

for i_s in range(len(s)):
    for i_t in range(len(t)):
        if s[i_s] == t[i_t]:
            dp[i_s+1][i_t+1] = dp[i_s][i_t] + 1
        dp[i_s+1][i_t] = max(dp[i_s+1][i_t], dp[i_s][i_t])
        dp[i_s][i_t+1] = max(dp[i_s][i_t+1], dp[i_s][i_t])

ans = ""

i_s = len(s)
i_t = len(t)

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

print(ans)

Submission status: Wrong Answer

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

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

for i_s in range(len(s)):
    for i_t in range(len(t)):
        if s[i_s] == t[i_t]:
            dp[i_s+1][i_t+1] = dp[i_s][i_t] + 1
        dp[i_s+1][i_t] = max(dp[i_s+1][i_t], dp[i_s][i_t])
        dp[i_s][i_t+1] = max(dp[i_s][i_t+1], dp[i_s][i_t])

ans = ""

i_s = len(s)
i_t = len(t)

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

S = input()
T = input()
ls = len(S)+1
lt = len(T)+1

dp = dp2(0, ls, lt)

#moji = [['']*ls for i in range(lt)]
#print(moji)
for i in range(1, lt):
    for j in range(1, ls):
        if S[j-1]==T[i-1]:
            dp[i][j] = dp[i-1][j-1]+1
            #moji[i][j] = moji[i-1][j-1] + S[j-1]
        else:
            if dp[i-1][j] >= dp[i][j-1]:
                dp[i][j] = dp[i-1][j]
                #moji[i][j] = moji[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
                #moji[i][j] = moji[i][j-1]
#print(moji)
#print(moji[lt-1][ls-1])
ans = ''
i = lt-1
j = ls-1
while i > 0 and j > 0:
    if dp[i][j] > dp[i-1][j-1]:
        ans += S[j-1]
    i -= 1
    j -= 1

print(ans[::-1])

Submission status: Wrong Answer

Solution code:
from collections import Counter

a = str(input())
b = str(input())
c = Counter(a)&Counter(b)

print("".join(c.keys()))

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
lenS = len(S)
lenT = len(T)

dp=[[0]*(lenT+1) for _ in range(lenS+1)]

for i in range(1,lenS+1):
    s = S[i-1]
    for j in range(1,lenT+1):
        t = T[j-1]
        if s==t:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+1)
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])

"""
復元
"""
ans = []
j = lenT
for i in range(lenS,0,-1):
    if dp[i][j] == dp[i-1][j-1]+1:
        ans.append(S[i-1])
    j -= 1
ans = ans[::-1]
print("".join(ans))

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
s = list(input())
t = list(input())
ls = len(s)
lt = len(t)
dp = [[[] for i in range(lt+1)] for i in range(ls+1)]
for i in range(ls):
    flag = True
    for j in range(lt):
        if flag and s[i] == t[j]:
            if len(dp[i][j+1]) > len(dp[i+1][j]):
                dp[i+1][j+1] = deepcopy(dp[i][j+1])
            else:
                dp[i+1][j+1] = deepcopy(dp[i+1][j])
            dp[i+1][j+1].append(s[i])
            flag= False
        elif s[i] == t[j]:
            if len(dp[i][j+1])+1 > len(dp[i+1][j]):
                dp[i+1][j+1] = deepcopy(dp[i][j+1])
                dp[i+1][j+1].append(s[i])
            else:
                dp[i+1][j+1] = dp[i+1][j]
        else:
            dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j],key=lambda x: len(x))
    print(dp)
print(''.join(dp[ls][lt]))

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
a=len(s)
b=len(t)
c=[]
for i in range(a+1):
    d=[]
    for j in range(b+1):
        d.append(0)
    c.append(d)
for i in range(1,a+1):
    for j in range(1,b+1):
        if s[i-1]==t[j-1]:
            c[i][j]=max(c[i-1][j-1]+1,c[i-1][j],c[i][j-1])
        else:
            c[i][j]=max(c[i-1][j-1],c[i-1][j],c[i][j-1])
k=""
i=a
j=b
while not(i==0 or j==0):
    if c[i][j]==c[i-1][j-1]+1:
        k=k+s[i-1]
        i=i-1
        j=j-1
    elif c[i][j]==c[i-1][j]:
        i=i-1
    elif c[i][j]==c[i][j-1]:
        j=j-1
    elif c[i][j]==c[i-1][j-1]:
        i=i-1
        j=j-1
print(k[::-1])

Submission status: Wrong Answer

Solution code:
#EDPC_F
s=input()
t=input()
lens=len(s)
lent=len(t)
dp=[[0]*(lent+1) for _ in range(lens+1)]
for i in range(lens):
    for j in range(lent):
        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=lens
j=lent
ans=''
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j-1]+1:
        ans=s[i-1]+ans
        i-=1
        j-=1
    elif dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
print(ans)

Submission status: Wrong Answer

Solution code:
S = list(input())
T = list(input())
s_len = len(S)
t_len = len(T)
# Create array for DP which has over one element.
dp = [[0]*(t_len+1) for i in range(s_len+1)] 

# Get the length of　answer with DP
for i in range(s_len):
    for j in range(t_len):
        if S[i] == T[j]:
            dp[i+1][j+1] = max(dp[i][j+1]+1,dp[i+1][j])
        else:
            dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])

# Output
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[i-1][j] > dp[i][j-1]:
        i -= 1
    else:
        j -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
def LCS_bottom_up_print(X,Y):
    
    n = len(X)
    m = len(Y)
    
    L = [[None for y in range(m+1)] for x in range(n+1)]
    
    for i in range(n+1):
        for j in range(m+1):
            if i == 0 or j == 0:
                L[i][j] = 0
            elif X[i-1] == Y[j-1]:
                L[i][j] = 1 + L[i-1][j-1]
            else:
                tmp1 = L[i-1][j]
                tmp2 = L[i][j-1]
                L[i][j] = max(tmp1,tmp2)
      
    # Following code is used to print LCS 
    # 文字列の長さ
    index = L[n][m]
    
    # Create a character array to store the lcs string 
    lcs = [""] * (index+1) 
    
    # Start from the right-most-bottom-most corner and 
    # one by one store characters in lcs[] 
    # Start from the right-most-bottom-most corner and 
    # one by one store characters in lcs[] 
    i = n 
    j = m 
    while i > 0 and j > 0: 
  
        # If current character in X[] and Y are same, then 
        # current character is part of LCS 
        if X[i-1] == Y[j-1]: 
            lcs[index-1] = X[i-1] 
            i-=1
            j-=1
            index-=1
  
        # If not same, then find the larger of two and 
        # go in the direction of larger value 
        elif L[i-1][j] > L[i][j-1]: 
            i-=1
        else: 
            j-=1
  
    return "".join(lcs)
  
X=input()
Y=input()
LCS_bottom_up_print(X,Y)

Submission status: Wrong Answer

Solution code:
S = list(input())
T = list(input())
# Create array for DP which has over one element.
dp = [[str()]*(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] = dp[i][j] + S[i]
        else:
            dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
# print(dp)
print(dp[len(S)][len(T)])

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(200000)

X = input()
Y = input()
lenX = len(X)
lenY = len(Y)
dp = np.full((lenX+1,lenY+1),"-1",dtype=object)
dp[0,:]=""
dp[:,0]=""
def f(i,j):
  if dp[i][j]=="-1":
    x = X[i-1]
    y = Y[j-1]
    lo = f(i-1,j-1)
    l = f(i,j-1)
    o = f(i-1,j)
    if x==y:
      dp[i][j]="".join([lo,x])
    else:
      if len(l)>=len(o):
        dp[i][j]=l
      else:
        dp[i][j]=o
  return dp[i][j]

print(f(lenX,lenY))
print(dp)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

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

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

Submission status: Wrong Answer

Solution code:
from difflib import SequenceMatcher


def main():
    S, T = open(0).read().split()
    s = SequenceMatcher(None, S, T)
    lcs = "".join(
        [S[block.a : (block.a + block.size)] for block in s.get_matching_blocks()]
    )
    print(lcs)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
s=input()
t=input()

dp=[["" for i in range(len(t)+1)] for j in range(len(s)+1)]

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

ans=""
for item in dp[-1]:
    if len(item)>len(ans):
        ans=item
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
  s = input()
  t = input()
  sn, tn = len(s), len(t)
  dp = [[0]*(tn+1) for _ in range(sn+1)]
  for i, si in enumerate(s):
    di, di2 = dp[i], dp[i+1]
    for j, ti in enumerate(t):
      if si == ti:
        di2[j+1] = di[j] + 1
      else:
          if di[j+1] > di[j]:
              di2[j+1] = di[j+1]
          else:
              di2[j+1] = di2[j]
    dp[i+1] = di2
  ans = ""
  while sn*tn:
    di = dp[sn][tn]
    if di == dp[sn-1][tn-1]:
      tn -= 1
      sn -= 1
      ans += s[sn-1]
    elif di == dp[sn][tn-1]:
      tn -= 1
    else:
      sn -= 1
      
  print(ans[::-1])

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
def main():
  s = input()
  t = input()
  sn, tn = len(s), len(t)
  dp = [[""]*(tn+1) for _ in range(sn+1)]
  for i, si in enumerate(s):
    di, di2 = dp[i], dp[i+1]
    for j, ti in enumerate(t):
      if si == ti:
        di2[j+1] = di[j] + si
      else:
        di2[j+1] = max(di[j+1], di2[j])
    dp[i+1] = di2
  print(dp[sn][tn])

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
#最長共通部分文字列問題（連続文字数での共通部分）
#----------------------------------------------------------------
def lcs(S,T):
    m = len(S)
    n = len(T)
    counter = [[0]*(n+1) for x in range(m+1)]
    longest = 0
    lcs_set = set()
    
    #計算量はO(MN)
    for i in range(m):
        for j in range(n):
            if S[i] == T[j]:#同じやったとき
                c = counter[i][j] + 1
                counter[i+1][j+1] = c
                if c > longest:
                    lcs_set = set()#最長が更新された場合は、集合を空にする
                    longest = c
                    lcs_set.add(S[i-c+1:i+1])
                elif c == longest:#同じ場合は追加だけ（複数の最長文字列があれば、複数の要素が返ってくる）
                    lcs_set.add(S[i-c+1:i+1])
    return lcs_set
#集合で返す
# if I want to know the length of the Lcs, return longest.
#----------------------------------------------------------------
S = input()
T = input()
for s in lcs(S,T):
    print(s)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
a=len(s)
b=len(t)
dp=[[0]*b for i in range(a)]
dp[0][0]=0
ans=''
for i in range(a):
  for j in range(b):
    if s[i]==t[j]:
      dp[i][j]=dp[i-1][j-1]+1
      ans+=s[i]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
print(dp)      
print(ans)

Submission status: Wrong Answer

Solution code:
def lcs():
    n=len(s)
    m=len(t)
    ans=""
    mi=0
    dp=[[0 for i in range(n+1)] for j in range(m+1)]
    for i in range(m+1):
        for j in range(n+1):
            if i==0 or j==0:
                dp[i][j]=0
            elif t[i-1]==s[j-1]:
                dp[i][j]=dp[i-1][j-1]+1
                if dp[i][j]>mi:
                    mi=dp[i][j]
                    ans+=t[i-1]
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    return ans
  
s=input()
t=input()
print(lcs())

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	s = IS()
	t = IS()
	n = len(s)
	m = len(t)
	dp = [[0 for _ in range(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] = max(dp[i+1][j],dp[i][j+1],dp[i][j]+1)
			else:
				dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])

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

if __name__ == '__main__':
	main()