Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Longest Common Subsequence

For given two sequences $X$ and $Y$, a sequence $Z$ is a common subsequence of $X$ and $Y$ if $Z$ is a subsequence of both $X$ and $Y$. For example, if $X = \{a,b,c,b,d,a,b\}$ and $Y = \{b,d,c,a,b,a\}$, the sequence $\{b,c,a\}$ is a common subsequence of both $X$ and $Y$. On the other hand, the sequence $\{b,c,a\}$ is not a longest common subsequence (LCS) of $X$ and $Y$, since it has length 3 and the sequence $\{b,c,b,a\}$, which is also common to both $X$ and $Y$, has length 4. The sequence $\{b,c,b,a\}$ is an LCS of $X$ and $Y$, since there is no common subsequence of length 5 or greater.

  Write a program which finds the length of LCS of given two sequences $X$ and $Y$. The sequence consists of alphabetical characters.

Input

  The input consists of multiple datasets. In the first line, an integer $q$ which is the number of datasets is given. In the following $2 \times q$ lines, each dataset which consists of the two sequences $X$ and $Y$ are given.

Output

  For each dataset, print the length of LCS of $X$ and $Y$ in a line.

Constraints

$1 \leq q \leq 150$

$1 \leq$ length of $X$ and $Y$ $\leq 1,000$

$q \leq 20$ if the dataset includes a sequence whose length is more than 100

Sample Input 1

3
abcbdab
bdcaba
abc
abc
abc
bc

Sample Output 1

4
3
2

Reference

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.



Sample input:
3
abcbdab
bdcaba
abc
abc
abc
bc


Sample output:
4
3
2

Submission status: Time Limit Exceeded

Solution code:

n=int(input())
cnt=[]
for k in range(n):
    a=input()
    b=input()
    lc=[[0 for j in range(len(b)+1)]for i in range(len(a)+1)]
    for i in range(len(a)):
        for j in range(len(b)):
            if a[i]==b[j]:
                lc[i+1][j+1]=lc[i][j]+1
            else:
                if lc[i][j+1]>lc[i+1][j]:
                    lc[i+1][j+1]=lc[i][j+1]
                else:
                    lc[i+1][j+1]=lc[i+1][j]
    cnt.append(lc[-1][-1])
for i in range(len(cnt)):
    print(cnt[i])

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
ans = []

for i in range(q):
    s1 = input()
    n1 = len(s1)
    s2 = input()
    n2 = len(s2)

    f = [[0 for j in range(n2)] for i in range(n1)]
    if s1[0] == s2[0]:
        f[0][0] = 1
    else:
        f[0][0] = 0

    for j in range(1, n2):
        if f[0][j-1] == 0:
            if s1[0] == s2[j]: delta = 1
            else: delta = 0
            f[0][j] = f[0][j-1]+delta
        else:
            f[0][j] = f[0][j-1]

    for i in range(1, n1):
        if f[i-1][0] == 0:
            if s1[i] == s2[0]: delta = 1
            else: delta = 0
            f[i][0] = f[i-1][0]+delta
        else:
            f[i][0] = f[i-1][0]

    for i in range(1, n1):
        for j in range(1, n2):
            if s1[i] == s2[j]:
                f[i][j] = f[i-1][j-1]+1
            else:
                f[i][j] = max(f[i-1][j], f[i][j-1])

    ans.append(f[n1-1][n2-1])
    #print(f)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
def lcs(l1,l2):
    dp=[[0 for x in range(len(l2)+1)] for y in range(len(l1)+1)]

    for i in range(1,len(l1)+1):
        for j in range(1,len(l2)+1):
            if l1[i-1]==l2[j-1]:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
                
    return dp[len(l1)][len(l2)]


a=[]
n=int(input())
for i in range(n):
    l1=list(input())
    l2=list(input())
    a+=[lcs(l1,l2)]

for i in range(n):
    print(a[i])

Submission status: Time Limit Exceeded

Solution code:
a = (int)(input())
for i in range(a):
    str1 = input()
    str2 = input()
    size1 = len(str1)
    size2 = len(str2)
    dp = [[0 for j in range(size2+1)] for k in range(size1+1)]

    for j in range(1,size1+1):
        for k in range(1,size2+1):
            if str1[j-1]==str2[k-1]:
                dp[j][k] = max([dp[j-1][k],dp[j][k-1],dp[j-1][k-1]+1])
            else:
                dp[j][k] = max([dp[j-1][k],dp[j][k-1],dp[j-1][k-1]])

    print(dp[size1][size2])

Submission status: Time Limit Exceeded

Solution code:
m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    A = [[0 for j in range(len(str1)+1)]for k in range(len(str2)+1)]
    for j in range(len(str2)):
        for k in range(len(str1)):
            if(str1[k]==str2[j]):
                A[j+1][k+1] = A[j][k]+1
            else:
                if(A[j+1][k] < A[j][k+1]):
                    A[j+1][k+1] = A[j][k+1]
                else:
                    A[j+1][k+1] = A[j+1][k]
    print(A[len(str2)][len(str1)])

Submission status: Time Limit Exceeded

Solution code:
m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    A = [0 for j in range(len(str2)+1)]
    for j in range(len(str1)):
        A_copy = A[:]
        for k in range(len(str2)):
            if(str1[j]==str2[k]):
                A[k+1] = A_copy[k]+1
            else:
                if(A[k] > A[k+1]):
                    A[k+1] = A[k]
    print(A[-1])

Submission status: Time Limit Exceeded

Solution code:
m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    A = [0 for j in range(len(str2)+1)]
    for char1 in str1:
        A_copy = A[:]
        for j,char2 in enumerate(str2):
            if(char1==char2):
                A[j+1] = A_copy[j]+1
            elif(A[j] > A[j+1]):
                A[j+1] = A[j]
    print(A[-1])

Submission status: Time Limit Exceeded

Solution code:
m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    A = [0]*(len(str2)+1)
    for char1 in str1:
        A_copy = A[:]
        for j,char2 in enumerate(str2):
            if(char1==char2):
                A[j+1] = A_copy[j]+1
            elif(A[j] > A[j+1]):
                A[j+1] = A[j]
    print(A[-1])

Submission status: Time Limit Exceeded

Solution code:
def LCS(str1,str2):
    A = [[0 for _ in range(len(str2)+1)]for __ in range(len(str1)+1)]
    for i in range(len(str1)):
        for j in range(len(str2)):
            if(str1[i]==str2[j]):
                A[i+1][j+1] = A[i][j]+1
            elif(A[i+1][j] > A[i][j+1]):
                A[i+1][j+1] = A[i+1][j]
            else:
                A[i+1][j+1] = A[i][j+1]
    return A[-1][-1]
 
 
m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    print(LCS(str1,str2))

Submission status: Time Limit Exceeded

Solution code:
def lcs(str1,str2):
    f=[[0 for i in range(len(str2)+1)]for j in range(len(str1)+1)]
    for i in range(1,len(str1)+1):
        for j in range(1,len(str2)+1):
           if str1[i-1]==str2[j-1]:
              f[i][j]=f[i-1][j-1]+1
           else:
              f[i][j]=max(f[i-1][j],f[i][j-1])
    return f[-1][-1]
               

N=int(input())
for i in range(N):
    x=input()
    y=input()
    print(lcs(x,y))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

cnt=[0 for i in range(n)]

for i in range(n):
	A = []
	A = input()
	B = []
	B = input()

	DP = [[0 for k in range(len(B)+1)] for j in range(len(A)+1)]

	for j in range(len(A)):
		for k in range(len(B)):
			if A[j]==B[k]:
				DP[j+1][k+1]=DP[j][k]+1
			else:
				DP[j+1][k+1]=max(DP[j+1][k], DP[j][k+1])
	cnt[i]=DP[len(A)][len(B)]


for i in range(n):
	print(cnt[i])

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    for i in range(n):
        a = input()
        b = input()
        na=len(a)
        nb=len(b)
        array = [[0]*nb for i in range(na)]
        #array = [[0 for i in range(nb)] for j in range(na)]
        for i in range(na):
            for j in range(nb):
                c = 0
                if i==0:
                    if a[i]==b[j]:
                        array[i][j]=1
                elif j==0:
                    if a[i]==b[j]:
                        array[i][j]=1
                else:
                    if a[i] == b[j]:
                        c = 1
                    array[i][j] = max(
                        array[i-1][j],
                        array[i][j-1],
                        array[i-1][j-1]+c)
        print(array[na-1][nb-1])
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
for _ in range(n):
    a = input()
    b = input()
    na=len(a)
    nb=len(b)
    array = [[0]*nb for i in range(na)]
    #array = [[0 for i in range(nb)] for j in range(na)]
    for i in range(na):
        for j in range(nb):
            c = 0
            if i==0:
                if a[i]==b[j]:
                    array[i][j]=1
            elif j==0:
                if a[i]==b[j]:
                    array[i][j]=1
            else:
                if a[i] == b[j]:
                    c = 1
                array[i][j] = max(
                    array[i-1][j],
                    array[i][j-1],
                    array[i-1][j-1]+c)
    print(array[na-1][nb-1])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
for _ in range(n):
    a = input()
    b = input()
    na=len(a)
    nb=len(b)
    #array = [[0]*nb for i in range(na)]
    array = [[0 for i in range(nb)] for j in range(na)]
    for i in range(na):
        for j in range(nb):
            c = 0
            if i==0:
                if a[i]==b[j]:
                    array[i][j]=1
            elif j==0:
                if a[i]==b[j]:
                    array[i][j]=1
            else:
                if a[i] == b[j]:
                    c = 1
                array[i][j] = max(
                    array[i-1][j],
                    array[i][j-1],
                    array[i-1][j-1]+c)
    print(array[na-1][nb-1])

Submission status: Time Limit Exceeded

Solution code:
#dj 16D8101012J ito jun
n = int(input())
for _ in range(n):
    a = input()
    b = input()
    na=len(a)
    nb=len(b)
    array = [[0 for i in range(nb+1)] for j in range(na+1)]
    for i in range(1,na+1):
        for j in range(1,nb+1):
            c = 0
            if a[i-1] == b[j-1]:
                c = 1
            array[i][j] = max(
                array[i-1][j],
                array[i][j-1],
                array[i-1][j-1]+c)
    print(array[na][nb])

Submission status: Time Limit Exceeded

Solution code:
#dj 16D8101012J ito jun
n = int(input())
for _ in range(n):
    a = input()
    b = input()
    na=len(a)
    nb=len(b)
    array = [[0 for i in range(nb+1)] for j in range(na+1)]
    for i in range(1,na+1):
        for j in range(1,nb+1):
            c = 0
            if a[i-1] == b[j-1]:
                array[i][j]=array[i-1][j-1]+1
            else:
                array[i][j] = max(array[i-1][j],array[i][j-1])
    print(array[na][nb])

Submission status: Time Limit Exceeded

Solution code:
#dj 16D8101012J ito jun
n = int(input())
for _ in range(n):
    a = input()
    b = input()
    na=len(a)
    nb=len(b)
    array = [[0 for i in range(nb+1)] for j in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            else:
                row[j] = max(prerow[j],row[j-1])
    print(array[na][nb])

Submission status: Time Limit Exceeded

Solution code:
#dj 16D8101012J ito jun
n = int(input())
for _ in range(n):
    a = input()
    b = input()
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            else:
                row[j] = max(prerow[j],row[j-1])
    print(array[na][nb])

Submission status: Time Limit Exceeded

Solution code:
#dj 16D8101012J ito jun
n = int(input())
for _ in range(n):
    a = input()
    b = input()
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]+1:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    print(array[na][nb])

Submission status: Time Limit Exceeded

Solution code:
#dj 16D8101012J ito jun
n = int(input())
for _ in range(n):
    a = input()
    b = input()
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]+1:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    print(array[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]+1:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in sys.stdin.read().splitlines()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

def calc(x,y):
    i = len(x)
    j = len(y)
    if d[i][j]:
        return d[i][j]
    else:
        if i == 1:
            if x in y:
                d[i][j] = 1
                return 1
            else:
                d[i][j] = 0
                return 0
        elif j == 1:
            if y in x:
                d[i][j] = 1
                return 1
            else:
                d[i][j] = 0
                return 0
        else:
            if x[-1] == y[-1]:
                tmp = max(calc(x[:-1],y[:-1])+1,calc(x[:-1],y),calc(x,y[:-1]))
                d[i][j] = tmp
                return tmp
            else:
                tmp = max(calc(x[:-1],y),calc(x,y[:-1]))
                d[i][j] = tmp
                return tmp
        
q = int(input())
for i in range(q):
    x = input()
    y = input()
    d = [[None for _ in range(len(y)+1)] for _ in range(len(x)+1)]
    print(calc(x,y))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

def calc(x,y):
    i = len(x)
    j = len(y)
    if not d[i][j] == None:
        return d[i][j]
    else:
        if x[-1] == y[-1]:
            tmp = max(calc(x[:-1],y[:-1])+1,calc(x[:-1],y),calc(x,y[:-1]))
            d[i][j] = tmp
            return tmp
        else:
            tmp = max(calc(x[:-1],y),calc(x,y[:-1]))
            d[i][j] = tmp
            return tmp
        
q = int(input())
for i in range(q):
    x = input()
    y = input()
    d = [[0 if i == 0 or j == 0 else None for i in range(len(y)+1)] for j in range(len(x)+1)]
    print(calc(x,y))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

def calc(x,y):
    i = len(x)
    j = len(y)
    if not d[i][j] == None:
        return d[i][j]
    else:
        if x[-1] == y[-1]:
            tmp = calc(x[:-1],y[:-1])+1
            d[i][j] = tmp
            return tmp
        else:
            tmp = max(calc(x[:-1],y),calc(x,y[:-1]))
            d[i][j] = tmp
            return tmp
        
q = int(input())
for i in range(q):
    x = input()
    y = input()
    d = [[0 if i == 0 or j == 0 else None for i in range(len(y)+1)] for j in range(len(x)+1)]
    print(calc(x,y))

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
for i in range(q):
    x = input()
    y = input()
    n = len(x)
    m = len(y)
    d = [[0 for _ in range(m+1)] for _ in range(n+1)]
    for i in range(n):
        for j in range(m):
            if x[i] == y[j]:
                d[i+1][j+1] = d[i][j]+1
            else:
                d[i+1][j+1] = max(d[i+1][j],d[i][j+1])
    print(d[n][m])

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
d = [[0 for _ in range(1001)] for _ in range(1001)]
for i in range(q):
    x = input()
    y = input()
    n = len(x)
    m = len(y)
    for i in range(1001):
        d[i][0]=0
        d[0][i]=0
    for i in range(n):
        for j in range(m):
            if x[i] == y[j]:
                d[i+1][j+1] = d[i][j]+1
            else:
                d[i+1][j+1] = max(d[i+1][j],d[i][j+1])
    print(d[n][m])

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
for i in range(q):
    x = input()
    y = input()
    n = len(x)
    m = len(y)
    d = [0]*((n+1)*(m+1))
    for i in range(n):
        for j in range(m):
            if x[i] == y[j]:
                d[(n+1)*(j+1)+i+1] = d[(n+1)*j+i]+1
            else:
                d[(n+1)*(j+1)+i+1] = max(d[(n+1)*j+i+1],d[(n+1)*(j+1)+i])
    print(d[-1])

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
for i in range(q):
    x = input()
    y = input()
    n = len(x)
    m = len(y)
    dp = [0]*((n+1)*(m+1))
    for i in range(n):
        for j in range(m):
            a = (n+1)*(j+1)+i+1
            if x[i] == y[j]:
                b = (n+1)*j+i
                dp[a] = dp[b]+1
            else:
                c = (n+1)*j+i+1
                d = (n+1)*(j+1)+i
                dp[a] = max(dp[c],dp[d])
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
for i in range(q):
    x = input()
    y = input()
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        dp2 = dp1[:]
        for j in range(m):
            if x[i] == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    print(dp1[-1])

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
for i in range(q):
    x = input().rstrip()
    y = input().rstrip()
    n = len(x)
    m = len(y)
    d = [[0 for _ in range(m+1)] for _ in range(n+1)]
    for i in range(n):
        for j in range(m):
            if x[i] == y[j]:
                d[i+1][j+1] = d[i][j]+1
            else:
                d[i+1][j+1] = max(d[i+1][j],d[i][j+1])
    print(d[n][m])

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
for i in range(q):
    x = input()
    y = input()
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    print(dp1[-1])

Submission status: Time Limit Exceeded

Solution code:
q = int(input().rstrip())
for i in range(q):
    x = input().rstrip()
    y = input().rstrip()
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    print(dp1[-1])

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
ans = []
for i in range(q):
    x = input()
    y = input()
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    ans+=[dp1[-1]]
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
ans = []
for i in range(q):
    x = input()
    y = input()
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    ans.append(dp1[-1])
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
q = int(input().rstrip())
ans = []
for i in range(q):
    x = input().rstrip()
    y = input().rstrip()
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    ans.append(dp1[-1])
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
def calc(x,y):
    n = len(x)
    m = len(y)
    d = [[0 for _ in range(m+1)] for _ in range(n+1)]
    for i in range(n):
        s = x[i]
        for j in range(m):
            if s == y[j]:
                d[i+1][j+1] = d[i][j]+1
            else:
                d[i+1][j+1] = max(d[i+1][j],d[i][j+1])
    return d[n][m]

q = int(input())
for i in range(q):
    x = input()
    y = input()
    print(calc(x,y))

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
for _ in [0]*q:
    s1, s2 = input(), input()
    l1, l2 = len(s1), len(s2)

    dp = [[0]*(l2+1) for _ in [0]*(l1+1)]
    for i, c1 in enumerate(s1, start=1):
        for j, c2 in enumerate(s2, start=1):
            dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+(c1==c2))

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

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
for _ in [0]*q:
    s1, s2 = input(), input()
    l1, l2 = len(s1), len(s2)

    dp = [[0]*(l2+1) for _ in [0]*(l1+1)]
    for i, (c1, prev, cur) in enumerate(zip(s1, dp, dp[1:]), start=1):
        for j, (c2, ul, u, l, c) in enumerate(zip(s2, prev, prev[1:], cur, cur[1:]), start=1):
            dp[i][j] = max(ul+(c1==c2), u, l, c)

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

Submission status: Time Limit Exceeded

Solution code:
global memo
global ans

def judge_dup(list1,list2):#list1とlist2に共通した要素がある場合は１、ない場合は０
    tmp_list1=list(set(list1))
    tmp_list2=list(set(list2))
    judge=tmp_list1 + tmp_list2
    if(len(tmp_list1) + len(tmp_list2) == len(set(judge))):
        return 0
    else:
        return 1


def longest_common(data1,ind1,data2,ind2):
    #data1[ind1],data2[ind2]を先頭とする２つの部分文字列の最長common文字列の長さを返す
    if(len(data1) <=ind1 or len(data2) <=ind2):
        return 0
    if(memo[ind1][ind2]!=-1):
        return memo[ind1][ind2]

    tmp_data1=data1[ind1:]
    tmp_data2=data2[ind2:]
    tmp_max=0
    for i in range(len(tmp_data1)):
        x=tmp_data1[i]
        for j in range(len(tmp_data2)):
            if(x==tmp_data2[j]):
                if(judge_dup(tmp_data1[:i],tmp_data2[:j])==0):
                    #注目する文字以前に共通する文字があったら調査する意味なし
                    tmp = longest_common(data1,ind1+i+1,data2,ind2+j+1)
                    if(tmp_max < tmp +1):
                        tmp_max=tmp+1
                break
    
    memo[ind1][ind2]=tmp_max
    global ans
    if(ans < tmp_max):
        ans =tmp_max
    return tmp_max
            
    






                





n=int(input())


for loop in range(n):
    ans=0
    data1=input()
    data2=input()
    data1=list(data1)
    data2=list(data2)

    memo=[[-1]*len(data2) for i in range(len(data1))]
#memo[n][m]は、data1[n]、data2[m]それぞれを先頭とする
#部分文字列の最長common文字列の長さを格納する
    longest_common(data1,0,data2,0)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:




def mk_row(data1,data2,table,row_num):
    for column in range(1,len(data2)+1):
        if(data1[row_num-1] ==data2[column-1]):
            table[row_num][column]=table[row_num-1][column-1]+1
        else:
            table[row_num][column]=max([table[row_num-1][column],table[row_num][column-1]])




n=int(input())

for loop in range(n):
    data1=input()
    data2=input()
    data1=list(data1)
    data2=list(data2)
    table=[[0]*(len(data2)+1) for i in range(len(data1)+1)]#0行、0列は空集合に対応

    for i in range(1,len(data1)+1):
        mk_row(data1,data2,table,i)
    print(table[len(data1)][len(data2)])

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections
import heapq
import itertools
import operator
import sys

def lcs(x, y):
    dp = [[0] * 1010 for _ in range(1010)]
    for i, c in enumerate(y):
        if c == x[0]:
            dp[0][i] = 1
    for i, c in enumerate(x):
        if c == y[0]:
            dp[i][0] = 1
    for i in range(len(x)):
        for j in range(len(y)):
            if x[i] == y[j]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
    return dp[len(x)-1][len(y)-1]

def main():
    n = int(sys.stdin.readline())
    for _ in range(n):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print(lcs(x, y))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections
import heapq
import itertools
import operator
import sys

dp = [[0] * 1010 for _ in range(1010)]

def lcs(x, y):
    for i, c in enumerate(y):
        if c == x[0]:
            dp[0][i] = 1
    for i, c in enumerate(x):
        if c == y[0]:
            dp[i][0] = 1
    for i in range(len(x)):
        for j in range(len(y)):
            if x[i] == y[j]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
    return dp[len(x)-1][len(y)-1]

def main():
    n = int(sys.stdin.readline())
    for _ in range(n):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print(lcs(x, y))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

for _ in range(int(sys.stdin.readline())):
    x = sys.stdin.readline()
    y = sys.stdin.readline()
    c = [[0 for _ in range(len(y))] for _ in range(len(x))]
    

    for i in range(1,len(x)):
        for j in range(1,len(y)):
            if i>0 and j>0 and x[i-1]==y[j-1]:
                c[i][j] = c[i-1][j-1]+1
            else:
                c[i][j] = max(c[i][j-1], c[i-1][j])
            
    print(c[len(x)-1][len(y)-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

c = [[0 for _ in range(1001)] for _ in range(1001)]
for _ in range(int(sys.stdin.readline())):
    x = sys.stdin.readline().rstrip()
    y = sys.stdin.readline().rstrip()
    c[0][0]=0
    for i,xi in enumerate(x):
        for j,yj in enumerate(y):
            if xi==yj:
                c[i+1][j+1] = c[i][j]+1
            elif c[i][j+1] > c[i+1][j]:
                c[i+1][j+1] = c[i][j+1]
            else:
                c[i+1][j+1] = c[i+1][j]
            
    print(c[len(x)][len(y)])

Submission status: Time Limit Exceeded

Solution code:
Q = int(input().strip())
for q in range(Q):
    X = str(input().strip())
    Y = str(input().strip())
    lx = len(X)
    ly = len(Y)
    L = [[0 for j in range(0,ly+1)] for i in range(0,lx+1)]
    for i in range(1,lx+1):
        for j in range(1,ly+1):
            if X[i-1] == Y[j-1]:
                L[i][j] = 1 + L[i-1][j-1]
            else:
                L[i][j] = max(L[i-1][j],L[i][j-1])
    print(L[lx][ly])

Submission status: Time Limit Exceeded

Solution code:
Q = int(input().strip())
for q in range(Q):
    X = str(input().strip())
    Y = str(input().strip())
    lx = len(X)
    ly = len(Y)
    L = [[0 for j in range(0,ly+1)] for i in range(0,lx+1)]
    for i in range(1,lx+1):
        for j in range(1,ly+1):
            if X[i-1] == Y[j-1]:
                L[i][j] = 1 + L[i-1][j-1]
            else:
                L[i][j] = max(L[i-1][j],L[i][j-1])
    print(L[lx][ly])

Submission status: Time Limit Exceeded

Solution code:
def lcs(a_str, b_str):
    dp = [[0 for n in range(len(a))] for m in range(len(b_str))]
    for i in range(len(b_str)):
        for j in range(len(a_str)):
            if i == 0 or j == 0:
                dp[i][j] = int(a_str[j] == b_str[i])
            else:
                dp[i][j] = max(dp[i - 1][j - 1] + int(a_str[j] == b_str[i]), dp[i - 1][j], dp[i][j - 1])
    return dp[len(b_str) - 1][len(a_str) - 1]

trial = int(input())

for _ in range(trial):
    a = input()
    b = input()
    print(lcs(a, b))

Submission status: Time Limit Exceeded

Solution code:
def lcs(a_str, b_str):
    dp = [[0 for n in range(len(a))] for m in range(len(b_str))]
    for i in range(len(b_str)):
        for j in range(len(a_str)):
            if i == 0 or j == 0:
                dp[i][j] = int(a_str[j] == b_str[i])
            else:
                dp[i][j] = max(dp[i - 1][j - 1] + int(a_str[j] == b_str[i]), dp[i - 1][j], dp[i][j - 1])
    return dp[len(b_str) - 1][len(a_str) - 1]

trial = int(input())

for _ in range(trial):
    a = input()
    b = input()
    a = {k:v for k, v in enumerate(a)}
    b = {k:v for k, v in enumerate(b)}
    print(lcs(a, b))

Submission status: Time Limit Exceeded

Solution code:
#JOI
def main():
    X=input()
    Y=input()
    dp=[[0 for y in range(1+len(Y))] for x in range(1+len(X))]
    for x in range(len(X)):
        for y in range(len(Y)):
            now=0
            dp[x][y]=max(dp[x-1][y],dp[x][y-1])
            for x1 in range(Y[:y+1].count(X[x])):
                idx=now+Y[now:y+1].index(X[x])
                now=idx+1
                dp[x][y]=max(dp[x-1][idx-1]+1,dp[x][y])
            now=0
            for y1 in range(X[:x+1].count(Y[y])):
                idx=now+X[now:x+1].index(Y[y])
                now=idx+1
                dp[x][y]=max(dp[idx-1][y-1]+1,dp[x][y])
    print(dp[len(X)-1][len(Y)-1])
for i in range(int(input())):
    main()

Submission status: Time Limit Exceeded

Solution code:
#JOI
def main():
    X=input()
    Y=input()
    dp=[[0 for y in range(1+len(Y))] for x in range(1+len(X))]
    for x in range(len(X)):
        for y in range(len(Y)):
            now=0
            dp[x][y]=max(dp[x-1][y],dp[x][y-1])
            idx=Y[:y+1].rfind(X[x])
            if idx!=-1:
                dp[x][y]=max(dp[x-1][idx-1]+1,dp[x][y])
            idx=X[:x+1].rfind(Y[y])
            if idx!=-1:
                dp[x][y]=max(dp[idx-1][y-1]+1,dp[x][y])
    print(dp[len(X)-1][len(Y)-1])
for i in range(int(input())):
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


n = int(input())

# result = []

@lru_cache()
def search(s1, s2, rs=''):

    if not s1:
        # print(rs)
        result.append(rs)
        return

    if s1:
        s1_head, s1_body = s1[0], s1[1:]
        for idx2, s2_tgt in enumerate(s2):
            if s1_head == s2_tgt:
                search(s1_body, s2[idx2+1:], rs+s1_head)

    if s2:
        s2_head, s2_body = s2[0], s2[1:]
        for idx1, s1_tgt in enumerate(s1):
            if s2_head == s1_tgt:
                search(s1[idx1+1:], s2_body, rs+s2_head)

    if s1 and s2:
        search(s1[1:], s2[1:], rs)

    result.append(rs)
    # print(rs)


for _ in range(n):
    result = []
    s1 = input()
    s2 = input()
    search(s1, s2)
    print(max(map(len, result)))