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:
def f_lcs(S, T):
    """
    文字列s, tが与えられる。sの部分列かつtの部分列であるような文字列のうち、
    最長のものを1つ求めよ。文字列xの部分列とは、xから0個以上の文字を除いたあと、
    残りの文字を元の順序で連結して得られる文字列のことである。
    """
    # 参考: https://qiita.com/drken/items/03c7db44ccd27820ea0d
    from itertools import product

    # dp[i+1][j+1]: sのi文字目までとtのj文字目まで見たときにできる
    # Longest Common Subsequence (LCS) の長さ
    dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]
    for i, j in product(range(len(S)), range(len(T))):
        # もし s_i = t_j なら、dp[i][j] から作れるLCSに対し、 s_i(t_jも同じ) を
        # 加えることで、それまでより長いLCSを作りうる
        if S[i] == T[j]:
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
        # dp[i+1][j] に対して、tのj文字目を見てもLCSの長さは不変。
        # なぜなら、もし、sのi文字目とtのj-1文字目が等しいなら、それらを
        # LCSに加えてしまっているのでsのi文字目とtのj文字目とではLCSの候補にできない。
        # つまり、 dp[i+1][j+1]=dp[i+1][j] である。
        # 逆に、等しくないなら、 sのi文字目とtのj文字目から新たなLCSを作りうるが、
        # これは単に dp[i+1][j+1] の値である。結局、配列の2つの要素のうち小さくない方を選べばいい。
        # 同じく、 dp[i][j+1] に対して、sのi文字目を見てもLCSの長さは不変。
        # これらの事実を反映したのが下の式。
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1])

    ans = ''
    # DPテーブルから、現時点で見ているノードがどのノードから遷移してきたかを
    # 特定することでLCSの文字列を復元する
    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1  # (i-1, j) -> (i, j) と遷移していた
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1  # (i, j-1) -> (i, j) と遷移していた
        else:
            # (i-1, j-1) -> (i, j) と遷移していた
            ans += S[i - 1]  # T[j-1]でも(同じ文字なので)構わない
            i -= 1
            j -= 1
    ans = ans[::-1]  # DPテーブルの末尾から走査する都合上、解が逆さになる
    return ans

S = input()
T = input()
print(f_lcs(S, T))

Submission status: Time Limit Exceeded

Solution code:
S=input()
T=input()
dp=[['']*(len(S)+1) for _ in range(len(T)+1)]
for i in range(1,len(S)+1):
    for j in range(1,len(T)+1):
        for k in range(1,i+1):
            if S[k-1]==T[j-1]:
                if len(dp[j-1][k-1])+1 >= len(dp[j-1][i]):
                    dp[j][i]=dp[j-1][k-1]+T[j-1]
        if dp[j][i]=='':dp[j][i]=dp[j-1][i]
print(dp[-1][-1])

Submission status: Time Limit Exceeded

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):
    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 = ""
while n > 0 and m > 0:
    if s[n - 1] == t[m - 1]:
        ans += t[m - 1]
        n -= 1
        m -= 1
    elif dp[n - 1][m] >= dp[n][m - 1]:
        n -= 1
    else:
        m -= 1
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
s="0"+input()
t="0"+input()
m=len(s)
n=len(t)

dp=[["" for i in range(n)] for j in range(m)]


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

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    s = [c for c in S()]
    t = [c for c in S()]
    sl = len(s)
    tl = len(t)
    rr = [[0] * (tl) for _ in range(sl)]
    for i in range(sl):
        if s[i] == t[0]:
            for k in range(i,sl):
                rr[k][0] = 1

    for j in range(tl):
        if s[0] == t[j]:
            for k in range(j,tl):
                rr[0][k] = 1
            break

    ta = list(range(1, tl))
    for i in range(1, sl):
        rri = rr[i]
        for j in ta:
            if s[i] == t[j]:
                rri[j] = rr[i-1][j-1] + 1
                continue

            m = rr[i-1][j]
            if m < rri[j-1]:
                m = rri[j-1]
            rri[j] = m

    i = sl-1
    j = tl-1
    r = []
    while i >= 0 and j >= 0:
        if s[i] == t[j]:
            r.append(s[i])
            i -= 1
            j -= 1
            continue
        if rr[i][j] == 0:
            break
        if i > 0 and rr[i-1][j] == rr[i][j]:
            i -= 1
        else:
            j -= 1

    return ''.join(r[::-1])


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    s = [c for c in S()]
    t = [c for c in S()]
    sl = len(s)
    tl = len(t)
    rr = [[0] * (tl) for _ in range(sl)]
    for i in range(sl):
        for j in range(tl):
            if s[i] == t[j]:
                if i > 0 and j > 0:
                    rr[i][j] = rr[i-1][j-1] + 1
                else:
                    rr[i][j] = 1
                continue

            m = 0
            if i > 0:
                m = rr[i-1][j]
            if j > 0 and m < rr[i][j-1]:
                m = rr[i][j-1]
            rr[i][j] = m

    i = sl-1
    j = tl-1
    r = []
    while i >= 0 and j >= 0:
        if s[i] == t[j]:
            r.append(s[i])
            i -= 1
            j -= 1
            continue
        if rr[i][j] == 0:
            break
        if i > 0 and rr[i-1][j] == rr[i][j]:
            i -= 1
        else:
            j -= 1

    return ''.join(r[::-1])


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    s = S()
    t = S()
    sl = len(s)
    tl = len(t)
    rr = [[0] * (tl) for _ in range(sl)]
    for i in range(sl):
        for j in range(tl):
            if s[i] == t[j]:
                if i > 0 and j > 0:
                    rr[i][j] = rr[i-1][j-1] + 1
                else:
                    rr[i][j] = 1
                continue

            m = 0
            if i > 0:
                m = rr[i-1][j]
            if j > 0 and m < rr[i][j-1]:
                m = rr[i][j-1]
            rr[i][j] = m

    i = sl-1
    j = tl-1
    r = []
    while i >= 0 and j >= 0:
        if s[i] == t[j]:
            r.append(s[i])
            i -= 1
            j -= 1
            continue
        if rr[i][j] == 0:
            break
        if i > 0 and rr[i-1][j] == rr[i][j]:
            i -= 1
        else:
            j -= 1

    return ''.join(r[::-1])


print(main())

Submission status: Time Limit Exceeded

Solution code:
s=' '+input()
t=' '+input()
dp=[['']*len(t)for _ in range(len(s))]
for i in range(1,len(s)):
    for j in range(1,len(t)):
        if s[i]==t[j]:
            dp[i][j]=''.join([dp[i-1][j-1],s[i]])
        elif len(dp[i-1][j])>len(dp[i][j-1]):
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=dp[i][j-1]
print(dp[-1][-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
raw_input = sys.stdin.readline
s = list(raw_input().strip('\n'))
t = list(raw_input().strip('\n'))
N,M = len(s),len(t)
dp = [[0 for x in range(M+1)] for x in range(N+1)]
lst = [[[] for x in range(M+1)] for x in range(N+1)]
fin = 0
for i in range(1,N+1):
    for j in range(1,M+1):
        if s[i-1]==t[j-1]:
            if dp[i][j]<dp[i-1][j-1]+1:
                lst[i][j] = [i-1,j-1]
                dp[i][j] = dp[i-1][j-1]+1
        else:
            if dp[i][j]<dp[i-1][j-1]:
                lst[i][j] = [i-1,j-1]
                dp[i][j] = dp[i-1][j-1]
        if dp[i][j]<dp[i-1][j]:
            lst[i][j] = lst[i-1][j]
            dp[i][j] = dp[i-1][j]
        if dp[i][j]<dp[i][j-1]:
            lst[i][j] = lst[i][j-1]
            dp[i][j] = dp[i][j-1]
a,b = N,M
ans = ['']
while lst[a][b]:
    a,b = lst[a][b]
    if s[a]==t[b]:
        ans.append(s[a])
print "".join(ans[::-1])

'''
abcdefghijklmnop
jlmopabcdef
'''

Submission status: Time Limit Exceeded

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

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

DP=[[0 for j in range(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]=DP[i-1][j-1]+1
        else:
            DP[i][j]=max(DP[i-1][j],DP[i][j-1])
            
        
x,y=len_s,len_t
ANS=""

while x>0 and y>0:
    if x>0 and DP[x-1][y]==DP[x][y]:
        x-=1
    elif y>0 and DP[x][y-1]==DP[x][y]:
        y-=1
    else:
        ANS+=s[x-1]
        x-=1
        y-=1

print(ANS[::-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
raw_input = sys.stdin.readline
s = list(raw_input().strip('\n'))
t = list(raw_input().strip('\n'))
N,M = len(s),len(t)
dp = [[0 for x in range(M+1)] for x in range(N+1)]
lst = [[[] for x in range(M+1)] for x in range(N+1)]
fin = 0
for i in range(1,N+1):
    for j in range(1,M+1):
        if s[i-1]==t[j-1]:
            if dp[i][j]<dp[i-1][j-1]+1:
                lst[i][j] = [i-1,j-1]
                dp[i][j] = dp[i-1][j-1]+1
        else:
            if dp[i][j]<dp[i-1][j-1]:
                lst[i][j] = [i,j]
                dp[i][j] = dp[i-1][j-1]
        if dp[i][j]<dp[i-1][j]:
            lst[i][j] = lst[i-1][j]
            dp[i][j] = dp[i-1][j]
        if dp[i][j]<dp[i][j-1]:
            lst[i][j] = lst[i][j-1]
            dp[i][j] = dp[i][j-1]
a,b = N,M
ans = ['']
while lst[a][b]:
    a,b = lst[a][b]
    if s[a]==t[b]:
        ans.append(s[a])
print "".join(ans[::-1])

'''
abcdefghijklmnop
jlmopabcdef
'''

Submission status: Time Limit Exceeded

Solution code:
import sys
raw_input = sys.stdin.readline
s = list(raw_input().strip('\n'))
t = list(raw_input().strip('\n'))
N,M = len(s),len(t)
dp = [[0 for x in range(M+1)] for x in range(N+1)]
lst = [[[] for x in range(M+1)] for x in range(N+1)]
fin = 0
for i in range(N):
    for j in range(M):
        if s[i]==t[j]:
            if (dp[i][j]+1)>dp[i+1][j+1]:
                lst[i+1][j+1] = [i,j]
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1)
        if dp[i][j]>dp[i+1][j]:
            lst[i+1][j] = [i,j]
        dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if dp[i][j]>dp[i][j+1]:
            lst[i][j+1] = [i,j]
        dp[i][j+1] = max(dp[i][j+1],dp[i][j])
        if dp[i][j]>dp[i+1][j+1]:
            lst[i+1][j+1] = [i,j]
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j])
        fin = max(fin,dp[i+1][j+1])
a,b = N,M
for i in range(N+1):
    if dp[i][M]==fin:
        a,b = [i,M]
for i in range(M+1):
    if dp[N][i]==fin:
        a,b = [N,i]
ans = ['']
while lst[a][b]:
    a,b = lst[a][b]
    if s[a]==t[b]:
        ans.append(s[a])
print "".join(ans[::-1])

'''
abcdefghijklmnop
jlmopabcdef
'''

Submission status: Time Limit Exceeded

Solution code:
*S, = map(ord, input())
*T, = map(ord, input())
LS = len(S); LT = len(T)

dp = [[-1]*(LT+2) for i in range(LS+2)]
for i in range(LS-1, -1, -1):
    X = dp[i]; Y = dp[i+1]; si = S[i]
    r = X[LT]
    for j in range(LT-1, -1, -1):
        X[j] = r = max(Y[j+1] + 1, Y[j], r) if si == T[j] else max(Y[j], r)
i = j = 0
ans = []
X = dp[0]; Y = dp[1]
while i < LS and j < LT:
    if S[i] == T[j] and X[j] == Y[j+1] + 1:
        ans.append(S[i])
        i += 1; j += 1
        X = Y; Y = dp[i+1]
    elif X[j] == Y[j]:
        i += 1
        X = Y; Y = dp[i+1]
    else:
        j += 1
print(*map(chr, ans), sep='')

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input().strip()
    t = input().strip()
    dp = [[""] * (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] + s[i-1]
            if len(dp[i][j]) < len(dp[i-1][j]):
                dp[i][j] = dp[i-1][j]
            if len(dp[i][j]) < len(dp[i][j-1]):
                dp[i][j] = dp[i][j-1]
    print(dp[len(s)][len(t)])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
S,T = input(),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):
    dp[i][j] = max(dp[i][j-1], dp[i-1][j], dp[i-1][j-1] + (S[i-1]==T[j-1]))

res = []
x,y = len(S),len(T)
v = dp[x][y]
while v > 0:
  if dp[x-1][y] == v:
    x -= 1
  elif dp[x][y-1] == v:
    y -= 1
  else:
    res.append(S[x-1])
    x -= 1
    y -= 1

  v = dp[x][y]

print(''.join(reversed(res)))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
s = input()
ns = len(s)
t = input()
nt = len(t)

dp = [[0 for _ in range(ns+1)] for _ in range(nt+1)]

for ti in range(nt):
    for si in range(ns):
        if t[ti]==s[si]:
            add = 1
        else:
            add = 0

        dp[ti+1][si+1] = max(
            dp[ti][si]+add,
            dp[ti+1][si],
            dp[ti][si+1]
        )

# print(dp[nt][ns])

res = []
ti = nt
si = ns
while ti>0 and si>0:
    if t[ti-1]==s[si-1]:
        res.append(s[si-1])
        si -= 1
        ti -= 1
    elif dp[ti][si-1]>dp[ti-1][si]:
        si -= 1
    else:
        ti -= 1

res.reverse()
print("".join(res))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(int(1e7))

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

Solution code:
import sys
sys.setrecursionlimit(int(1e6) + 10)

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

Solution code:
s = input()
t = input()
lens, lent = len(s), len(t)
DP = [["" for j in range(lent + 1)] for i in range(lens + 1)]

for i in [num for num in range(lens)]:
    for j in [num for num in range(lent)]:
        if s[i] == t[j]:
            if len(DP[i+1][j+1]) < len(DP[i][j]) + 1:
                DP[i+1][j+1] = DP[i][j] + s[i]
        if len(DP[i+1][j+1]) < len(DP[i+1][j]):
            DP[i+1][j+1] = DP[i+1][j]
        if len(DP[i+1][j+1]) < len(DP[i][j+1]):
            DP[i+1][j+1] = DP[i][j+1]

print(DP[lens][lent])

Submission status: Time Limit Exceeded

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

DP = [[(0, "") for j in range(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]:
            if DP[i+1][j+1][0] < DP[i][j][0] + 1:
                DP[i+1][j+1] = (DP[i][j][0]+1, DP[i][j][1] + s[i])
        if DP[i+1][j+1][0] < DP[i+1][j][0]:
            DP[i+1][j+1] = DP[i+1][j]
        if DP[i+1][j+1][0] < DP[i][j+1][0]:
            DP[i+1][j+1] = DP[i][j+1]

print(DP[len(s)][len(t)][1])

Submission status: Time Limit Exceeded

Solution code:
def lcs(x, y):
    m = len(x)
    n = len(y)

    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])

    lcs_str = ''
    i, j = m, n
    while i > 0 and j > 0:
        if x[i-1] == y[j-1]:
            lcs_str += x[i-1]
            i -= 1
            j -= 1
        else:
            if c[i][j] == c[i-1][j]:
                i -= 1
            else:
                j -= 1

    return lcs_str[::-1]


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

Submission status: Time Limit Exceeded

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

    dp = [[""]*(iT+1) for _ in range(2)]
    for i in range(iS):
        OE0 = i&1
        OE1 = (i+1)&1
        for j in range(iT):
            if sS[i] == sT[j]:
                dp[OE1][j+1] = dp[OE0][j] + sS[i]
            else:
                s1 = dp[OE1][j]
                s2 = dp[OE0][j+1]
                if len(s1) > len(s2):
                    dp[OE1][j+1] = s1
                else:
                    dp[OE1][j+1] = s2
    print(dp[iS&1][iT])
解()

Submission status: Time Limit Exceeded

Solution code:
sS = input().rstrip()
sT = input().rstrip()
iS = len(sS)
iT = len(sT)

dp = [[""]*(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] + sS[i]
        else:
            s1 = dp[i+1][j]
            s2 = dp[i][j+1]
            if len(s1) > len(s2):
                dp[i+1][j+1] = s1
            else:
                dp[i+1][j+1] = s2
print(dp[iS][iT])

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
ls=len(s)
lt=len(t)
dp=[[""]*(lt+1) for i in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    if len(dp[i+1][j])==max(len(dp[i][j+1]),len(dp[i+1][j]),len(dp[i][j])+(s[i]==t[j])):
      dp[i+1][j+1]=dp[i+1][j]
    elif len(dp[i][j+1])==max(len(dp[i][j+1]),len(dp[i+1][j]),len(dp[i][j])+(s[i]==t[j])):
      dp[i+1][j+1]=dp[i][j+1]
    else:
      dp[i+1][j+1]=dp[i][j]+s[i]
print(dp[ls][lt])

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
ls=len(s)
lt=len(t)
dp=[[""]*(lt+1) for i in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    if len(dp[i+1][j])==max(len(dp[i][j+1]),len(dp[i+1][j]),len(dp[i][j])+(s[i]==t[j])):
      dp[i+1][j+1]=dp[i+1][j]
    elif len(dp[i][j+1])==max(len(dp[i][j+1]),len(dp[i+1][j]),len(dp[i][j])+(s[i]==t[j])):
      dp[i+1][j+1]=dp[i][j+1]
    elif len(dp[i][j])+(s[i]==t[j])==max(len(dp[i][j+1]),len(dp[i+1][j]),len(dp[i][j])+(s[i]==t[j])):
      a=list(dp[i][j])
      a.append(s[i])
      dp[i+1][j+1]="".join(a)
print(dp[ls][lt])

Submission status: Time Limit Exceeded

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

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

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

print(dp[LS][LT][1])

Submission status: Time Limit Exceeded

Solution code:
in_a = input();
in_b = input();
# parameters
# d -> ギャップペナルティ
# w -> 文字列が一致した時に加算するスコア
# miss -> ミスマッチ時のスコア
d = 0
w = 1
miss = 0

# initialize array
arr_score = [[0 for i in range(len(in_a) + 1)] for j in range(len(in_b) + 1)]
w_score = [[0 for i in range(len(in_a))] for j in range(len(in_b))]
trace_back_tmp = [[0 for i in range(len(in_a) + 1)]
                  for j in range(len(in_b) + 1)]
delta = [(-1, -1), (0, -1), (-1, 0)]
trace_back = []
max_int_length = 0
str_a = ""
str_b = ""

# score between chars
for m in range(len(in_b)):
    for n in range(len(in_a)):
        if (in_b[m] == in_a[n]):
            w_score[m][n] = w
        else:
            w_score[m][n] = miss

# calculating score
for m in range(len(in_b) + 1):
    for n in range(len(in_a) + 1):
        if n == 0:
            arr_score[m][n] = m * d
            trace_back_tmp[m][n] = delta[1]
        elif m == 0:
            arr_score[m][n] = n * d
            trace_back_tmp[m][n] = delta[0]
        else:
            a = arr_score[m - 1][n - 1] + w_score[m - 1][n - 1]
            b = arr_score[m - 1][n] + d
            c = arr_score[m][n - 1] + d
            arr_score[m][n] = max(a, b, c)
            if (a >= b and a >= c):
                trace_back_tmp[m][n] = delta[0]
            elif (b >= a and b >= c):
                trace_back_tmp[m][n] = delta[1]
            elif (c >= a and c >= b):
                trace_back_tmp[m][n] = delta[2]
        # for output score matrix
        if len(str(arr_score[m][n])) >= max_int_length:
            max_int_length = len(str(arr_score[m][n]))

# for trace_back
m = len(in_b)
n = len(in_a)

# trace_back
while (m > 0 or n > 0):
    d = trace_back_tmp[m][n]
    if d[0] == -1 and n > 0:
        n += d[0]
        str_a = in_a[n] + str_a
    elif m > 0:
        n += d[0]
        str_a = "-" + str_a
    if d[1] == -1 and m > 0:
        m += d[1]
        str_b = in_b[m] + str_b
    elif n > 0:
        m += d[1]
        str_b = "-" + str_b

ans = ""
for i in range(len(str_a)):
    if str_a[i] == str_b[i]:
        ans = ans + str_a[i]
print(ans)

Submission status: Time Limit Exceeded

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


s = tuple(fin())
t = tuple(fin())

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

dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
parent_ptrs = [[None] * (len_t + 1) for _ in range(len_s + 1)]

len_LCS = 0
len_LCS_idx = None
for i in reversed(range(len_s)):
    for j in reversed(range(len_t)):
        ins, dl = dp[i + 1][j], dp[i][j + 1]
        swap = dp[i + 1][j + 1] + 1 if s[i] == t[j] else dp[i + 1][j + 1]
        cand_tuple = (ins, dl, swap)
        max_val = max(cand_tuple)
        max_idx = cand_tuple.index(max_val)
        dp[i][j] = max_val
        parent_ptrs[i][j] = max_idx
        if len_LCS < max_val:
            len_LCS = max_val
            len_LCS_idx = (i, j)

LCS = []
i, j = len_LCS_idx
while parent_ptrs[i][j] != None:
    ptr_val = parent_ptrs[i][j]
    if ptr_val == 2:
        LCS.append(s[i])
        i, j = i + 1, j + 1
    elif ptr_val == 1:
        i, j = i, j + 1
    else:
        i, j = i + 1, j

print("".join(LCS))

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

s = " " + ns()
t = " " + ns()

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

lcs = [[""]*lent for _ in range(lens)]

for i in range(1,lens):
    for j in range(1,lent):
        if s[i] == t[j]:
            lcs[i][j] = lcs[i-1][j-1] + s[i]
            
        else:
            if len(lcs[i-1][j]) > len(lcs[i][j-1]):
                lcs[i][j] = lcs[i-1][j]
            else:
                lcs[i][j] = lcs[i][j-1]
                
print(lcs[-1][-1])

Submission status: Time Limit Exceeded

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

LS = len(s)
LT = len(t)

dp = [['' for _ in range(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] = dp[i - 1][j - 1] + s[i - 1]
        else:
            if len(dp[i - 1][j]) < len(dp[i][j - 1]):
                dp[i][j] = dp[i][j - 1]
            else:
                dp[i][j] = dp[i - 1][j]

print(dp[LS][LT])

Submission status: Time Limit Exceeded

Solution code:
#出典
#http://d.hatena.ne.jp/mzp/20100623/lcs
#ここから完全にコピペしました
import sys
sys.setrecursionlimit(10**7)
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: Time Limit Exceeded

Solution code:

s = input()
t = input()
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]
        else:
            dpj = dp[i][j+1] 
            dpi = dp[i+1][j]
            if len(dpi) > len(dpj):
                dp[i+1][j+1] = dpi
            else:
                dp[i+1][j+1] = dpj
    # print(dp)
print(dp[S][T])

Submission status: Time Limit Exceeded

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

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

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

ans = ""

s_ind = len(s) 
t_ind = len(t) 

while True:
        if s_ind <= 0 or t_ind <= 0:
                break
        
        prev_max = max(dp[s_ind][t_ind - 1], dp[s_ind - 1][t_ind])
        if s[s_ind - 1] == t[t_ind - 1]:
                prev_max = max(prev_max, dp[s_ind - 1][t_ind - 1] + 1)
        
        if prev_max == dp[s_ind][t_ind - 1]:
                t_ind -= 1
                continue
        if prev_max == dp[s_ind - 1][t_ind]:
                s_ind -= 1
                continue
        else:
                ans += s[s_ind - 1]
                s_ind -= 1
                t_ind -= 1
                continue

print(''.join(list(reversed(ans))))

Submission status: Time Limit Exceeded

Solution code:
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):
        indicator = 1 if S[i - 1] == T[j - 1] else 0
        dp[i][j] = max(dp[i - 1][j - 1] + indicator, dp[i - 1][j], dp[i][j - 1])

ans = ''


def print_lcs(s, t, dp_table, i, j):
    global ans
    if i == 0 or j == 0:
        return
    if S[i - 1] == T[j - 1]:
        print_lcs(s, t, dp, i - 1, j - 1)
        ans += S[i - 1]
    else:
        if dp[i - 1][j] >= dp[i][j - 1]:
            print_lcs(S, T, dp, i - 1, j)
        else:
            print_lcs(S, T, dp, i, j - 1)


print_lcs(S, T, dp, len(S), len(T))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
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: Time Limit Exceeded

Solution code:
s = input()
t = input()
dp = [''] * (len(t)+1)

enumt = list(enumerate(t))[::-1]
for i, si in list(enumerate(s))[::-1]:
  a = dp[:]
  for j, tj in enumt:
    if si == tj:
      a[j] = si + dp[j+1]
    else:
      x = a[j]
      y = a[j+1]
      a[j] = x if len(x) > len(y) else y
  dp = a

print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [''] * (lt+1)

ranget = list(range(lt))[::-1]
for i in range(ls)[::-1]:
  a = dp[:]
  for j in ranget:
    if s[i] == t[j]:
      a[j] = s[i] + dp[j+1]
    else:
      x = a[j]
      y = a[j+1]
      a[j] = x if len(x) > len(y) else y
  dp = a

print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[''] * (lt+1) for _ in range(ls+1)]

for x in range(ls):
  i = ls - 1 - x
  for y in range(lt):
    j = lt - 1 - y
    a = dp[i+1][j]
    b = dp[i][j+1]
    c = a if len(a) > len(b) else b
    if s[i] == t[j]:
      d = s[i] + dp[i+1][j+1]
      c = c if len(c) > len(d) else d
    dp[i][j] = c

print(dp[0][0])

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = raw_input()
    T = raw_input()
    
    # dp[i][j] := Sのi文字目, Tのj文字目まで見た場合のLCS
    dp = [[''] * (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] = dp[i - 1][j - 1] + S[i - 1]
            else:
                if len(dp[i - 1][j]) > len(dp[i][j - 1]):
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = dp[i][j - 1]
    
    print(dp[-1][-1])
    
main()