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: Time Limit Exceeded

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

dp = [[0]*len(t) for i in range(len(s))]


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


ret = ['']*dp[-1][-1]
id = dp[-1][-1]
i = len(s) - 1
j = len(t) - 1
while(i >= 0 and j >= 0):
    #print(s[i], t[j], i, j)
    if s[i] == t[j]:
        id -= 1
        ret[id] = s[i]
        i -= 1
        j -= 1
        # print(ret)
    else:
        if i > 0 and dp[i-1][j] >= dp[i][j-1]:
            i -= 1
        else:
            j -= 1

print(''.join(ret))
#print(*dp, sep='\n')

Submission status: Time Limit Exceeded

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

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

for i in range(1,n+1):
    for j in range(1,m+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])

res = ''
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
        res = s[n] + res
print(res)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
m = len(s)
n = len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
res = ""
while n != 0 and m != 0:
    if dp[m][n] == dp[m-1][n]:
        m -= 1
    elif dp[m][n] == dp[m][n-1]:
        n -= 1
    else:
        n -= 1
        m -= 1
        res = s[m] + res
print(res)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
m = len(s)
n = len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        x = s[i-1]
        y = t[j-1]
        if x == y:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
res = ""
while n != 0 and m != 0:
    if dp[m][n] == dp[m-1][n]:
        m -= 1
    elif dp[m][n] == dp[m][n-1]:
        n -= 1
    else:
        n -= 1
        m -= 1
        res = s[m] + res
print(res)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
m = len(s)
n = len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        x = s[i-1]
        y = t[j-1]
        if x == y:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = dp[i-1][j]
            if dp[i][j] < dp[i][j-1]:
                dp[i][j] = dp[i][j-1]
res = ""
while n != 0 and m != 0:
    if dp[m][n] == dp[m-1][n]:
        m -= 1
    elif dp[m][n] == dp[m][n-1]:
        n -= 1
    else:
        n -= 1
        m -= 1
        res = s[m] + res
print(res)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
def lcs(s,t):
    m = len(s)
    n = len(t)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            x = s[i-1]
            y = t[j-1]
            if x == y:
                dp[i][j] = dp[i-1][j-1]+1
            else:
                dp[i][j] = dp[i-1][j]
                if dp[i][j] < dp[i][j-1]:
                    dp[i][j] = dp[i][j-1]
    res = ""
    while n > 0 and m > 0:
        if dp[m][n] == dp[m-1][n]:
            m -= 1
        elif dp[m][n] == dp[m][n-1]:
            n -= 1
        else:
            n -= 1
            m -= 1
            res = s[m] + res
    print(res)
    return 0
a = lcs(s,t)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
def lcs(s,t):
    m = len(s)
    n = len(t)
    dp = [[""]*(n+1) for _ in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            x = s[i-1]
            y = t[j-1]
            if x == y:
                dp[i][j] = dp[i-1][j-1]+x
            else:
                dp[i][j] = dp[i-1][j]
                if len(dp[i][j]) < len(dp[i][j-1]):
                    dp[i][j] = dp[i][j-1]
    return dp[i][j]
print(lcs(s,t))

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left as bl, bisect_right as br, insort
    import sys
    import heapq
    # from math import *
    from collections import defaultdict as dd, deque
    def data():
        return sys.stdin.readline().strip()

    def mdata():
        return map(int, data().split())

    out = sys.stdout.write
    # sys.setrecursionlimit(100000)
    INF = int(10e9)

    s = data()
    t = data()
    dp = [[0] * (len(s) + 1) for i in range(len(t) + 1)]
    for i in range(1, len(t) + 1):
        for j in range(1, len(s) + 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])
    m = max(max(dp))
    ans = ''
    for i in range(len(t) - 1, -1, -1):
        for j in range(len(s) - 1, -1, -1):
            if dp[i + 1][j + 1] == m and s[j] == t[i]:
                ans = s[j] + ans
                m -= 1
                break
    out(ans+'\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def LCS_iter(s1, s2):
	dp = [[-10000 for i in range(len(s2) + 1)] for i in range(len(s1) + 1)]
	ans = [['' for i in range(len(s2) + 1)] for i in range(len(s1) + 1)]
	for i in range(len(s2) + 1):
		dp[0][i] = 0
	for i in range(len(s1) + 1):
		dp[i][0] = 0
	i = 1
	j = 1
	while i <= len(s1):
		while j <= len(s2):
			if s1[i - 1] == s2[j - 1]:
				dp[i][j] = 1 + dp[i - 1][j - 1]
				ans[i][j] = 'cross'
			else:
				if dp[i - 1][j] > dp[i][j - 1]:
					dp[i][j] = dp[i - 1][j]
					ans[i][j] = 'up'
				else:
					dp[i][j] = dp[i][j - 1]
					ans[i][j] = 'left'
			j += 1
		i += 1
		j = 1
	i = len(s1)
	j = len(s2)
	s = ''
	while i >= 0 and j >= 0:
		if ans[i][j] == 'cross':
			s += s1[i - 1]
			i -= 1
			j -= 1
		elif ans[i][j] == 'up':
			i -= 1
		else:
			j -= 1
	return s[::-1]


s1 = input()
s2 = input()

print(LCS_iter(s1, s2))

Submission status: Time Limit Exceeded

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

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

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

for ns in range(ls):
    for nt in range(lt):
        if s[ns] == t[nt]:
            dp[ns + 1][nt + 1] = max(dp[ns][nt] + 1, dp[ns + 1][nt + 1])
        dp[ns + 1][nt + 1] = max(dp[ns + 1][nt + 1], dp[ns + 1][nt], dp[ns][nt + 1])

ans = ''
i, j = ls, 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] + ans
        i -= 1
        j -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy
s=list(input())
t=list(input())
dp=[["" 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]:
            list=[dp[i][j]+s[i],dp[i+1][j],dp[i][j+1]]
            index=numpy.argmax([len(item) for item in list])
            dp[i+1][j+1]=list[index]
        else:
            list=[dp[i][j],dp[i+1][j],dp[i][j+1]]
            index=numpy.argmax([len(item) for item in list])
            dp[i+1][j+1]=list[index]
print(dp[len(s)][len(t)])

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

s = readline().rstrip().decode()
t = readline().rstrip().decode()
s_size = len(s)
t_size = len(t)
dp = [[0] * (t_size + 1) for _ in range(s_size + 1)]
ans = ''
for i in range(s_size):
    for j in range(t_size):
        if s[i] == t[j]:
            if dp[i + 1][j + 1] < dp[i][j] + 1:
                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])
while s_size > 0 and t_size > 0:
    if dp[s_size][t_size] == dp[s_size - 1][t_size]:
        s_size -= 1
    elif dp[s_size][t_size] == dp[s_size][t_size - 1]:
        t_size -= 1
    else:
        ans = s[s_size - 1] + ans
        s_size -= 1
        t_size -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


s=data()
t=data()
dp1=[0]*len(s)
for i in range(len(t)):
    m=0
    for j in range(len(s)):
        if s[j]==t[i]:
            k=dp1[j]
            dp1[j]=m+1
            m=max(k,m)
        else:
            m=max(m,dp1[j])

dp2=[0]*len(s)
for i in range(len(t)-1,-1,-1):
    m=0
    for j in range(len(s)-1,-1,-1):
        if s[j]==t[i]:
            k=dp2[j]
            dp2[j]=m+1
            m=max(k,m)
        else:
            m=max(m,dp2[j])

m=max(dp1)
cnt=m
ans=''
for j in range(len(s)-1,-1,-1):
    if dp1[j]>=cnt and dp2[j]>=m-cnt+1:
        ans=s[j]+ans
        cnt-=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


s=data()
t=data()
dp1=[0]*len(s)
for i in range(len(t)):
    m=0
    dp2=dp1.copy()
    for j in range(len(s)):
        if s[j]==t[i]:
            dp2[j]=max(m+1,dp1[j])
        m=max(m,dp1[j])
    dp1=dp2.copy()

dp3=[0]*len(s)
for i in range(len(t)-1,-1,-1):
    m=0
    dp2=dp3.copy()
    for j in range(len(s)-1,-1,-1):
        if s[j]==t[i]:
            dp2[j]=max(m+1,dp3[j])
        m=max(m,dp3[j])
    dp3=dp2.copy()

m=max(dp1)
cnt=m
ans=''
for j in range(len(s)-1,-1,-1):
    if dp1[j]>=cnt and dp3[j]>=m-cnt+1:
        ans=s[j]+ans
        cnt-=1
    if cnt==0:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:

def buildString(s, t, dp):

	result = []
	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:
			result.append(s[i-1])
			i -= 1
			j -= 1

	return ''.join(reversed(result))


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

	return buildString(s, t, dp)

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

Submission status: Time Limit Exceeded

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

def solve(S,T):
    # print(W)
    s = len(S)
    t = len(T)
    dp = [[['',0] for _ in range(t+1)] for _ in range(s+1)]
    for i in range(s):
        for j in range(t):
            if S[i]==T[j]:
                dp[i+1][j+1][0] = dp[i][j][0]+S[i]
                dp[i+1][j+1][1] = dp[i][j][1]+1
            elif dp[i][j+1][1]>dp[i+1][j][1]:
                dp[i+1][j+1] = dp[i][j+1]
            else:
                dp[i+1][j+1] = dp[i+1][j]
    ans = dp[-1][-1][0]
    return ans
print(solve(S,T))

Submission status: Time Limit Exceeded

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

def solve(S,T):
    # print(W)
    s = len(S)
    t = len(T)
    dp = [['']*(t+1) for _ in range(s+1)]
    for i in range(s):
        for j in range(t):
            if S[i]==T[j]:
                dp[i+1][j+1] = dp[i][j]+S[i]
            elif len(dp[i][j+1])>len(dp[i+1][j]):
                dp[i+1][j+1] = dp[i][j+1]
            else:
                dp[i+1][j+1] = dp[i+1][j]
    ans = dp[-1][-1]
    return ans
print(solve(S,T))

Submission status: Time Limit Exceeded

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

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

dp = list([0]*(len(t)+1) for _ in range(len(s)+1))
route = list([[0,0]]*(len(t)+1) for _ in range(len(s)+1))
for i in range(len(s)+1):
    for j in range(len(t)+1):
        route[i][j] = [0,0]


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
            route[i+1][j+1] = [i,j]
        if dp[i+1][j+1] < dp[i+1][j]:
            dp[i+1][j+1] = dp[i+1][j]
            route[i+1][j+1] = [i+1,j]
        if dp[i+1][j+1] < dp[i][j+1]:
            dp[i+1][j+1] = dp[i][j+1]
            route[i+1][j+1] = [i,j+1]

i = len(s)
j = len(t) 
ans = ""

while i > 0 and j > 0:
    i, j = route[i][j][0], route[i][j][1]
    if i >= len_s or j >= len_t:
        continue
    if s[i] == t[j]:
        ans += s[i]

ans = ans[::-1]
print(ans)

Submission status: Time Limit Exceeded

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

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

dp = list([0]*(len(t)+1) for _ in range(len(s)+1))
route = list([0]*(len(t)+1) for _ in range(len(s)+1))
for i in range(len(s)+1):
    for j in range(len(t)+1):
        route[i][j] = [0,0]


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
            route[i+1][j+1] = [i,j]
        if dp[i+1][j+1] < dp[i+1][j]:
            dp[i+1][j+1] = dp[i+1][j]
            route[i+1][j+1] = [i+1,j]
        if dp[i+1][j+1] < dp[i][j+1]:
            dp[i+1][j+1] = dp[i][j+1]
            route[i+1][j+1] = [i,j+1]

i = len(s)
j = len(t) 
ans = ""

while i > 0 and j > 0:
    i, j = route[i][j][0], route[i][j][1]
    if i >= len_s or j >= len_t:
        continue
    if s[i] == t[j]:
        ans += s[i]

ans = ans[::-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
x = len(s)
y = len(t)
dp = [[""]*(y+1) for _ in range(x+1)]
for i in range(x):
    for j in range(y):
        if s[i] == t[j]:
            lcs = dp[i][j] + s[i]
        elif len(dp[i+1][j]) >= len(dp[i][j+1]):
            lcs = dp[i+1][j]
        else:
            lcs = dp[i][j+1]
        dp[i+1][j+1] = lcs
# for i in range(x+1): print(dp[i])
print(dp[x][y])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
sl = len(s)
tl = len(t)
dp = [[""]*(tl) for _ in range(sl)]
#sのi番目までの文字とtのj番目までの文字の最長共通

for i in range(sl):
  for j in range(tl):
    a = len(dp[i-1][j-1])
    b = len(dp[i][j-1])
    c = len(dp[i-1][j])
    if s[i] == t[j]:
      if i>=1 and j>=1:
        dp[i][j] = dp[i-1][j-1] + s[i]
      else:
        dp[i][j] = s[i]
    else:
      if b > c:
        dp[i][j] = dp[i][j-1]
      else:
        dp[i][j] = dp[i-1][j]
      
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
# educational DP contest F

X = input()
Y = input()
x = len(X)
y = len(Y)

dp = [[0 for _ in range(y + 1)] for _ in range(x + 1)]
for i in range(x):
    for j in range(y):
        if X[i] == Y[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])

# print(dp[x][y])

ans = ''
while x > 0 and y > 0:
    if dp[x][y] == dp[x][y - 1]:
        y -= 1
    elif dp[x][y] == dp[x - 1][y]:
        x -= 1
    else:
        ans += X[x - 1]
        x -= 1
        y -= 1

print(ans[::-1])

Submission status: Time Limit Exceeded

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

    """
    dp[i][j] := s[1] ... s[i] と t[1] ... t[j] に対するLCSの長さ
    
    s[i+1] == t[i+1]のとき、dp[i+1][j+1]は dp[i][j]+1, dp[i+1][j], dp[i][j+1]のいずれか  
    dp[i+1][j+1] = max(dp[i][j] + 1, dp[i+1][j], dp[i][j+1])

    それ以外の時
    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    """

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

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

ls=len(S)
lt=len(T)


DP=[[0]*(lt+1) for _ 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]=max(DP[i-1][j-1]+1,DP[i][j-1],DP[i-1][j])
        else:
            DP[i][j]=max(DP[i][j-1],DP[i-1][j])

lf=DP[ls][lt]

res=''
u=ls
v=lt
while u>0 and v>0:
    if DP[u][v]==DP[u-1][v]:
        u-=1
    elif DP[u][v]==DP[u][v-1]:
        v-=1
    else:
        res=S[u-1]+res
        u-=1
        v-=1

print(res)

Submission status: Time Limit Exceeded

Solution code:
s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
def al(str):
    return alphabetlist.index(str)+1

dp=[[0 for i in range(0,M)] for i in range(0,N)]

firsts=N
for i in range(0,N):
    if s[i]==t[0]:
        firsts=i
        break

firstt=M
for i in range(0,M):
    if t[i]==s[0]:
        firstt=i
        break

for i in range(0,N):
    if i>=firsts:
        dp[i][0]=al(t[0])

for i in range(0,M):
    if i>=firstt:
        dp[0][i]=al(s[0])

for i in range(1,N):
    for j in range(1,M):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]*27+al(s[i])
        else:
            if dp[i][j-1]>dp[i-1][j]:
                dp[i][j]=dp[i][j-1]
            else:
                dp[i][j]=dp[i-1][j]

a=dp[N-1][M-1]
ans=[]
while a!=0:
    i=a%27
    ans.append(alphabetlist[i-1])
    a//=27

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
def al(str):
    return alphabetlist.index(str)+1

dp=[[0 for i in range(0,M)] for i in range(0,N)]

firsts=N
for i in range(0,N):
    if s[i]==t[0]:
        firsts=i
        break

firstt=M
for i in range(0,M):
    if t[i]==s[0]:
        firstt=i
        break

for i in range(0,N):
    if i>=firsts:
        dp[i][0]=al(t[0])

for i in range(0,M):
    if i>=firstt:
        dp[0][i]=al(s[0])

for i in range(1,N):
    for j in range(1,M):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]*100+al(s[i])
        else:
            if dp[i][j-1]>dp[i-1][j]:
                dp[i][j]=dp[i][j-1]
            else:
                dp[i][j]=dp[i-1][j]

a=dp[N-1][M-1]
ans=[]
while a!=0:
    i=a%100
    ans.append(alphabetlist[i-1])
    a//=100

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
N=len(s)
t=input()
M=len(t)

dp=[['' for i in range(0,M)] for i in range(0,N)]

firsts=N
for i in range(0,N):
    if s[i]==t[0]:
        firsts=i
        break

firstt=M
for i in range(0,M):
    if t[i]==s[0]:
        firstt=i
        break

for i in range(0,N):
    if i>=firsts:
        dp[i][0]=t[0]

for i in range(0,M):
    if i>=firstt:
        dp[0][i]=s[0]

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

print(dp[N-1][M-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s=input()
t=input()

ns=len(s)
nt=len(t)
dp=np.zeros((ns+1,nt+1),np.int64)
pp=np.full((ns+1,nt+1),'-1')
for i in range(ns):
  for j in range(nt):
    a=np.array([dp[i][j]+1 if s[i]==t[j] else -1,dp[i+1][j],dp[i][j+1]])
    dp[i+1][j+1]=np.max(a)
    pp[i+1][j+1]=np.argmax(a)

i=ns
j=nt
ans=[]
while i>0 and j>0:
  sw=pp[i][j]
  if sw==0:
        i-=1
        j-=1
        ans.append(s[i])
  elif sw==1:
        j-=1
  elif sw==2:
        i-=1
ans1=''
for _ in range(len(ans)):
      ans1+=ans.pop()
print(ans1)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    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])
    
    res = ""
    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:
            res = s[i-1] + res
            i -= 1
            j -= 1
    
    print(res)
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import copy,bisect

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

index={moji:[] for moji in alphabetlist}
for i in range(N):
    index[s[i]].append(i)

dp=['' for i in range(0,N)]

for i in range(0,N):
    if index[t[0]]:
        if i>=index[t[0]][0]:
            dp[i]=t[0]

for i in range(1,M):
    x=t[i]
    if index[x]:
        for j in range(N-1,index[x][0]-1,-1):
            next=index[x][bisect.bisect_right(index[x],j)-1]-1
            if next>=0:
                if len(dp[j])<1+len(dp[next]):
                    dp[j]=dp[next]+t[i]
            else:
                if dp[j]=='':
                    dp[j]=t[i]

print(dp[N-1])

Submission status: Time Limit Exceeded

Solution code:
import copy,bisect

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

Index={moji:[] for moji in alphabetlist}
for i in range(N):
    Index[s[i]].append(i)

dp=[0 for i in range(0,N)]

for i in range(0,N):
    if Index[t[0]]:
        if i>=Index[t[0]][0]:
            num=alphabetlist.index(t[0])+1
            dp[i]=num

for i in range(1,M):
    x=t[i]
    num=alphabetlist.index(x)+1
    if Index[x]:
        for j in range(N-1,Index[x][0]-1,-1):
            next=Index[x][bisect.bisect_right(Index[x],j)-1]-1
            if next>=0:
                if dp[j]<num+100*dp[next]:
                    dp[j]=dp[next]*100+num
            else:
                if dp[j]==0:
                    dp[j]=num

ans=[]
a=dp[-1]
while a!=0:
    i=a%100
    ans.append(alphabetlist[i-1])
    a-=i
    a//=100

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

Submission status: Time Limit Exceeded

Solution code:
import copy,bisect

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

index={moji:[] for moji in alphabetlist}
for i in range(N):
    index[s[i]].append(i)

dp=['' for i in range(0,N)]

for i in range(0,N):
    if index[t[0]]:
        if i>=index[t[0]][0]:
            dp[i]=t[0]

for i in range(1,M):
    x=t[i]
    if index[x]:
        for j in range(N-1,index[x][0]-1,-1):
            next=index[x][bisect.bisect_right(index[x],j)-1]-1
            if next>=0:
                if len(dp[j])<1+len(dp[next]):
                    dp[j]=dp[next]+t[i]
            else:
                if dp[j]=='':
                    dp[j]=t[i]

print(dp[N-1])

Submission status: Time Limit Exceeded

Solution code:
import copy,bisect

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

index={moji:[] for moji in alphabetlist}
for i in range(N):
    index[s[i]].append(i)

dp=[[] for i in range(0,N)]

for i in range(0,N):
    if index[t[0]]:
        if i>=index[t[0]][0]:
            dp[i]=[t[0]]

for i in range(1,M):
    x=t[i]
    if index[x]:
        for j in range(N-1,index[x][0]-1,-1):
            next=index[x][bisect.bisect_right(index[x],j)-1]-1
            if next>=0:
                if len(dp[j])<1+len(dp[next]):
                    xxx=copy.copy(dp[next])
                    xxx.append(t[i])
                    dp[j]=xxx
            else:
                if dp[j]==[]:
                    dp[j]=[t[i]]

print(''.join(dp[N-1]))

Submission status: Time Limit Exceeded

Solution code:
import copy

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

index={moji:[] for moji in alphabetlist}
for i in range(N):
    index[s[i]].append(i)

dp=[[[] for i in range(0,N)] for j in range(0,M)]

for i in range(0,N):
    if index[t[0]]:
        if i>=index[t[0]][0]:
            dp[0][i]=[t[0]]

for i in range(0,M):
    for j in range(0,N):
        x=t[i]
        if index[x] and j>=index[x][0]:
            start=0
            end=len(index[x])-1
            while end-start>1:
                test=(end+start)//2
                if j>=index[x][test]:
                    start=test
                else:
                    end=test
            if j>=index[x][end]:
                next=index[x][end]-1
            else:
                next=index[x][start]-1
            if next>=0:
                if len(dp[i-1][j])>1+len(dp[i-1][next]):
                    dp[i][j]=dp[i-1][j]
                else:
                    x=copy.copy(dp[i-1][next])
                    x.append(t[i])
                    dp[i][j]=x
            else:
                if dp[i-1][j]==[]:
                    dp[i][j]=[t[i]]
                else:
                    dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=dp[i-1][j]

print(''.join(dp[M-1][N-1]))

Submission status: Time Limit Exceeded

Solution code:
s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

index={moji:[] for moji in alphabetlist}
for i in range(N):
    index[s[i]].append(i)

dp=[[[] for i in range(0,N)] for j in range(0,M)]

for i in range(0,N):
    if index[t[0]]:
        if i>=index[t[0]][0]:
            dp[0][i]=[t[0]]

for i in range(0,M):
    for j in range(0,N):
        x=t[i]
        if index[x] and j>=index[x][0]:
            start=0
            end=len(index[x])-1
            while end-start>1:
                test=(end+start)//2
                if j>=index[x][test]:
                    start=test
                else:
                    end=test
            if j>=index[x][end]:
                next=index[x][end]-1
            else:
                next=index[x][start]-1
            if next>=0:
                if len(dp[i-1][j])>1+len(dp[i-1][next]):
                    dp[i][j]=dp[i-1][j]
                else:
                    dp[i][j]=dp[i-1][next]+[t[i]]
            else:
                if dp[i-1][j]==[]:
                    dp[i][j]=[t[i]]
                else:
                    dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=dp[i-1][j]

print(''.join(dp[M-1][N-1]))

Submission status: Time Limit Exceeded

Solution code:
s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

index={moji:[] for moji in alphabetlist}
for i in range(N):
    index[s[i]].append(i)

dp=[["" for i in range(0,N)] for j in range(0,M)]

for i in range(0,N):
    if index[t[0]]:
        if i>=index[t[0]][0]:
            dp[0][i]=t[0]

for i in range(0,M):
    for j in range(0,N):
        x=t[i]
        if index[x] and j>=index[x][0]:
            start=0
            end=len(index[x])-1
            while end-start>1:
                test=(end+start)//2
                if j>=index[x][test]:
                    start=test
                else:
                    end=test
            if j>=index[x][end]:
                next=index[x][end]-1
            else:
                next=index[x][start]-1
            if next>=0:
                if len(dp[i-1][j])>1+len(dp[i-1][next]):
                    dp[i][j]=dp[i-1][j]
                else:
                    dp[i][j]=dp[i-1][next]+t[i]
            else:
                if dp[i-1][j]=="":
                    dp[i][j]=t[i]
                else:
                    dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=dp[i-1][j]

print(dp[M-1][N-1])

Submission status: Time Limit Exceeded

Solution code:
X = input()
Y = input()
x = len(X)
y = len(Y)

dp = [['' for _ in range(y + 1)] for _ in range(x + 1)]
for i in range(x):
    for j in range(y):
        if X[i] == Y[j]:
            dp[i + 1][j + 1] = dp[i][j] + X[i]
        else:
            if len(dp[i][j + 1]) > len(dp[i + 1][j]):
                dp[i + 1][j + 1] = dp[i][j + 1]
            else:
                dp[i + 1][j + 1] = dp[i + 1][j]

print(dp[x][y])
# print(dp)

Submission status: Time Limit Exceeded

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

inf = pow(10, 4)
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
key = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)+1):
  for j in range(len(t)+1):
    if i == 0 and j == 0:
      continue
    if i == 0:
      dp[i][j] = dp[i][j-1]
      continue
    if j == 0:
      dp[i][j] = dp[i-1][j]
      continue
    if s[i-1] == t[j-1]:
      dp[i][j] = dp[i-1][j-1] + 1
      key[i][j] = (i-1)*inf+(j-1)
    else:
      if dp[i-1][j] > dp[i][j-1]:
        dp[i][j] = dp[i-1][j]
        key[i][j] = key[i-1][j]
      else:
        dp[i][j] = dp[i][j-1]
        key[i][j] = key[i][j-1]

ans = []
i, j = key[len(s)][len(t)]//inf, key[len(s)][len(t)]%inf
while True:
  if s[i] == t[j]:
    ans.append(s[i])
  if i == 0 or j == 0:
    break
  i, j = key[i][j]//inf, key[i][j]%inf

ans.reverse()
print("".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import copy

s = input()
t = input()

dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
key = [[[0, 0] for _ in range(len(t)+1)] for _ in range(len(s)+1)]
for i in range(len(s)+1):
  for j in range(len(t)+1):
    if i == 0 and j == 0:
      continue
    if i == 0:
      dp[i][j] = dp[i][j-1]
      continue
    if j == 0:
      dp[i][j] = dp[i-1][j]
      continue
    if s[i-1] == t[j-1]:
      dp[i][j] = dp[i-1][j-1] + 1
      key[i][j] = [i-1, j-1]
    else:
      if dp[i-1][j] > dp[i][j-1]:
        dp[i][j] = dp[i-1][j]
        key[i][j] = copy.deepcopy(key[i-1][j])
      else:
        dp[i][j] = dp[i][j-1]
        key[i][j] = copy.deepcopy(key[i][j-1])

ans = []
i, j = len(s), len(t)
while True:
  i, j = map(int, key[i][j])
  if s[i] == t[j]:
    ans.append(s[i])
  if i == 0 or j == 0:
    break

ans.reverse()
print("".join(ans))