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

Solution code:
n=int(input())
x=[0 for i in range(n)]
y=[0 for i in range(n)]
for i in range(n):
    x[i]=input()
    y[i]=input()

for i in range(n):
    X=list(x[i])
    Y=list(y[i])
    a=[int(0) for i in range(len(X))]
    for j in range(len(X)):
        b=-1
        for l in range(j,len(X)):
            for k in range(len(Y)):
                if X[l]==Y[k] and b<k:
                    b=k
                    a[j]+=1
                    break
                
    print(max(a))

Submission status: Wrong Answer

Solution code:

def ask(X,Y):

 a=len(X)
 b=len(Y)
 Z=[]
 c=0
 for n in range(a):
  z=0
  for i in range(n,a):
   for j in range(c,b):
    if(X[i]==Y[j]):
     z+=1
     c=j
     break
  Z.append(z)

 Z.sort();
 return Z[a-1]


q=int(input())
Z=[]
for p in range(q):
 x=input()
 X=list(x)
 y=input()
 Y=list(y)
 z=ask(X,Y)
 Z.append(z)

for p in range(q):
 print(Z[p])

Submission status: Wrong Answer

Solution code:
n=int(input())

for i in range(n):
    a=list(input())
    b=list(input())

    r=[[0 for j in range(len(b)+1)]for i in range(len(a)+1)]

    for j in range(1,len(a)+1):
        for k in range(1,len(b)+1):
            c=max(r[j-1][k-1],r[j-1][k],r[j][k-1])
            
            if a[j-1]==b[k-1]:
                c=c+1
            
            r[j][k]=c
    print(r[len(a)][len(b)])

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    result = []
    for i in range(n):
        a = input()
        b = input()
        array = [[1 for i in range(len(b))] for j in range(len(a))]
        for i in range(1, len(a)):
            for j in range(1, len(b)):
                c = 0
                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)
        result.append(array[len(a)-1][len(b)-1])
    for i in result:
        print(i)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def ask(X,Y):

 a=len(X)
 b=len(Y)
 Z=[]
 c=0
 for n in range(a):
  z=0
  for i in range(n,a):
   for j in range(c,b):
    if(X[i]==Y[j]):
     z+=1
     c=j
     break
  Z.append(z)

 Z.sort();
 return Z[a-1]


q=int(input())
Z=[]
for p in range(q):
 x=input()
 X=list(x)
 y=input()
 Y=list(y)
 z=ask(X,Y)
 Z.append(z)

for p in range(q):
 print(Z[p])

Submission status: Wrong Answer

Solution code:
n=int(input())

for i in range(n):
    a=list(input())
    b=list(input())

    r=[[0 for j in range(len(b)+1)]for i in range(len(a)+1)]

    for j in range(1,len(a)+1):
        for k in range(1,len(b)+1):
            c=max(r[j-1][k-1],r[j-1][k],r[j][k-1])
            if a[j-1]==b[k-1]:
                c=max(r[j-1][k-1]+1,r[j-1][k],r[j][k-1])
            
            r[j][k]=c
            print(r[j][k],end="")
        print(" ",end="\n")
    
    print(r[len(a)][len(b)])

Submission status: Wrong Answer

Solution code:
def ask(X,Y):

 a=len(X)
 b=len(Y)
 Z=[]
 for n in range(a):
  z=0
  c=0
  for i in range(n,a):
   for j in range(c,b):
    if(c==b-1):
     break
    if(X[i]==Y[j]):
     z+=1
     c=j
     break
     
  Z.append(z)

 Z.sort();
 return Z[a-1]


q=int(input())
Z=[]
for p in range(q):
 x=input()
 X=list(x)
 y=input()
 Y=list(y)
 z=ask(X,Y)
 Z.append(z)

for p in range(q):
 print(Z[p])

Submission status: Wrong Answer

Solution code:
def ask(X,Y):

 a=len(X)
 b=len(Y)
 Z=[]
 for n in range(a):
  z=0
  c=0
  for i in range(n,a):
   for j in range(c,b):
    if(c==b-1):
     break
    if(X[i]==Y[j]):
     c=j
     break
     
  Z.append(z)

 Z.sort();
 return Z[a-1]


q=int(input())
Z=[]
for p in range(q):
 x=input()
 X=list(x)
 y=input()
 Y=list(y)
 z=ask(X,Y)
 Z.append(z)

for p in range(q):
 print(Z[p])

Submission status: Wrong Answer

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

q=int(input())
A=[0 for i in range(q)]
for i in range(q):
    X=input()
    Y=input()
    A[i]=lcs(X,Y)

for i in range(q):
    print(A[i]+1)

Submission status: Wrong Answer

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

q=int(input())
A=[0 for i in range(q)]
for i in range(q):
    X=input()
    Y=input()
    A[i]=lcs(X,Y)

for i in range(q):
    print(A[i])

Submission status: Wrong Answer

Solution code:

def main():
    n = int(input())
    for i in range(n):
        a = input()
        b = input()
        na=len(a)
        nb=len(b)
        array = [[0 for i in range(nb)] for j in range(na)]
        for i in range(na):
            for j in range(nb):
                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:
                    c = 0
                    if a[i] == b[j]:
                        c = 1
                    array[i][j] = array[i-1][j-1]+c 
                    """
                    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: Wrong Answer

Solution code:
n=int(input())
x=[]
y=[]
for k in range(n):
	dp=[[0 for i in range(1000)] for j in range(1000)]
	x=list(input())
	y=list(input())
	for i in range(len(x)):
		for j in range(len(y)):
			
			if i is 0:
				if x[i] is y[j]:
					dp[i][j]=1
				else:
					dp[i][j]=dp[i][j-1]
			if j is 0:
				if x[i] is y[j]:
					dp[i][j]=1
				else:
					dp[i][j]=dp[i-1][j]

	for i in range(len(x)):
		tmp=0
		for j in range(len(y)):
			if i is not 0 and j is not 0:
				if x[i] is y[j] and tmp is 0:
					dp[i][j]=max(dp[i][j-1],dp[i-1][j])+1
					tmp+=1
				else:
					dp[i][j]=max(dp[i][j-1],dp[i-1][j])

	print(dp[len(x)-1][len(y)-1])
#	print(x,y)
#	for i in range(7):
#		print(dp[i])

Submission status: Wrong Answer

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)):
        for k in range(len(str2)):
            if(str1[j]==str2[k]):
                A[k+1] = A[k]+1
            else:
                if(A[k] > A[k+1]):
                    A[k+1] = A[k]
    print(A[-1])

Submission status: Wrong Answer

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)):
        for k in range(len(str2)):
            if(str1[j]==str2[k]):
                A[k+1] = A[k+1]+1
            else:
                if(A[k] > A[k+1]):
                    A[k+1] = A[k]
    print(A[-1])

Submission status: Wrong Answer

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]


m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    print(LCS(str1,str2))

Submission status: Wrong Answer

Solution code:
import sys

n=int(input())

for _ in range(n):
	x=sys.stdin.readline().rstrip('\r\n')
	y=sys.stdin.readline().rstrip('\r\n')
	
	list=[0]
	for z in y:
		for i in range(len(list)-1,-1,-1):
			tmp=x.find(z,list[i])
			if tmp+1:
				if i+1<len(list):
					list[i+1]=min(tmp+1,list[i+1])
				else:
					list.append(tmp+1)
print(len(list)-1)

Submission status: Wrong Answer

Solution code:
import sys

n=int(input())

for _ in range(n):
	x=sys.stdin.readline().rstrip('\r\n')
	y=sys.stdin.readline().rstrip('\r\n')
	
	list=[0]
	for z in y:
		for i in range(len(list)-1,-1,-1):
			tmp=x.find(z,list[i])
			if tmp+1:
				if i+1<len(list):
					list[i+1]=min(list[i+1],tmp+1)
				else:
					list.append(tmp+1)
print(len(list)-1)

Submission status: Wrong Answer

Solution code:
def lcs(x,y,l,j,k):
	if(j==0 or k==0):
		return
	if(x[j-1]==y[k-1]):
		lcs(x,y,l,j-1,k-1)
		global c
		c+=1
	else:
		if l[j-1][k]>=l[j][k-1]:
			lcs(x,y,l,j-1,k)
		else:
			lcs(x,y,l,j,k-1)

q=int(input())
c=0
for i in range(q):
	x=list(input())
	y=list(input())
	l=[[0]*(len(y)+1)]*(len(x)+1)

for j in range(1, len(x) + 1):
    for k in range(1, len(y) + 1):
        if x[j - 1] == y[k - 1]:
            a = 1
        else:
            a = 0
        l[j][k] = max(l[j-1][k-1] + a, l[j-1][k], l[j][k-1])
lcs(x,y,l,len(x),len(y))
print(c)

Submission status: Wrong Answer

Solution code:
ans=[]
n=int(input("n="))
for i in range(n):
    X=input("X=")
    Y=input("Y=")
    com=[0]
    for i in X:
        for j in range(len(com)-1,-1,-1):
            tmp=X.find(i,com[j])+1
            if tmp:
                if j+1<len(com):
                    com[j+1]=min(com[j+1],tmp)
                else:
                    com.append(tmp)     
    ans.append(len(com)-1)
for i in range(n):
    print(ans[i])

Submission status: Wrong Answer

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]*na
        #array = [[0 for i in range(nb)] for j in range(na)]
        print(array)
        for i in range(na):
            for j in range(nb):
                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:
                    c = 0
                    if a[i] == b[j]:
                        c = 1
                    array[i][j] = array[i-1][j-1]+c 
                    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: Wrong Answer

Solution code:

def main():
    n = int(input())
    for i in range(n):
        a = input()
        b = input()
        na=len(a)
        nb=len(b)
        array = [[1]*nb]*na
        #array = [[0 for i in range(nb)] for j in range(na)]
        print(array)
        for i in range(na):
            for j in range(nb):
                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:
                    c = 0
                    if a[i] == b[j]:
                        c = 1
                    array[i][j] = array[i-1][j-1]+c 
                    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: Wrong Answer

Solution code:
def main():
    n = int(input())
    for i in range(n):
        a = input()
        b = input()
        na=len(a)
        nb=len(b)
        array = [[1]*nb]*na
        #array = [[0 for i in range(nb)] for j in range(na)]
        print(array)
        for i in range(na):
            for j in range(nb):
                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:
                    c = 0
                    if a[i] == b[j]:
                        c = 1
                    array[i][j] = array[i-1][j-1]+c 
                    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: Wrong Answer

Solution code:

def main():
    n = int(input())
    for i in range(n):
        a = input()
        b = input()
        na=len(a)
        nb=len(b)
        array = [[1]*nb]*na
        #array = [[0 for i in range(nb)] for j in range(na)]
        for i in range(na):
            for j in range(nb):
                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:
                    c = 0
                    if a[i] == b[j]:
                        c = 1
                    array[i][j] = array[i-1][j-1]+c 
                    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: Wrong Answer

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

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)] for j in range(na)]
    for i in range(na):
        for j in range(nb):
            c = 0
            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: Wrong Answer

Solution code:
def lcs(x,y,l,j,k):
	if(j==0 or k==0):
		return
	if(x[j-1]==y[k-1]):
		lcs(x,y,l,j-1,k-1)
		global c
		c+=1
	else:
		if l[j-1][k]>=l[j][k-1]:
			lcs(x,y,l,j-1,k)
		else:
			lcs(x,y,l,j,k-1)

q=int(input())
c=0
for i in range(q):
	x=list(input())
	y=list(input())
	l=[[0 for i in range(len(y)+1)] for j in range(len(x)+1)]

for j in range(1, len(x) + 1):
    for k in range(1, len(y) + 1):
        if x[j - 1] == y[k - 1]:
            a = 1
        else:
            a = 0
        l[j][k] = max(l[j-1][k-1] + a, l[j-1][k], l[j][k-1])
lcs(x,y,l,len(x),len(y))
print(c)

Submission status: Wrong Answer

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

    p = []
    for i, c in enumerate(s1):
        s = 0
        while True:
            j = s2[s:].find(c)
            if j == -1:
                break
            p.append((i, s+j))
            s += j+1

    lis = []
    for _, y in sorted(p):
        i = bisect_left(lis, y)
        if len(lis) <= i:
            lis.append(y)
        else:
            lis[i] = y
    print(len(lis))

Submission status: Wrong Answer

Solution code:
import sys

def lcm(c,i, j):
    if c[i][j]>0: return c[i][j]        
    if i==0 or j==0:
        return 0
    elif x[i]==y[j]:
        c[i][j] = lcm(c,i-1,j-1)+1
        return c[i][j]
    else:
        c[i][j] = max(lcm(c,i,j-1), lcm(c,i-1,j))
        return c[i][j]

for _ in range(int(sys.stdin.readline())):
    x = sys.stdin.readline()
    y = sys.stdin.readline()
    c = [[0 for _ in range(len(y)+1)] for _ in range(len(x)+1)] 
    print(lcm(c,len(x)-1,len(y)-1))

Submission status: Wrong Answer

Solution code:
import sys

def dp_init(m, n):
    return [[0] * n] * m

def solve(str_a, str_b):
    dp = dp_init(len(str_a), len(str_b))
    return rec(0, 0, str_a, str_b)

def rec(i, j, str_a, str_b):
    if i == 0 or j == 0:
        return 0
    if dp[i][j] > 0:
        return dp[i][j]
    if str_a[i-1] == str_b[j-1]:
        dp[i][j] = rec(i-1, j-1, str_a, str_b) + 1
        return dp[i][j]
    dp[i][j] = max(rec(i, j-1, str_a, str_b), rec(i-1, j, str_a, str_b))
    return dp[i][j]

nb_pairs = int(input())
pairs = []
for i in range(0, nb_pairs):
    pairs.append((input(), input()))

for i in range(0, nb_pairs):
    str_a, str_b = pairs[i]
    print(solve(str_a, str_b))

Submission status: Wrong Answer

Solution code:
import sys

def dp_init(m, n):
    return [[0] * n] * m

def solve(str_a, str_b):
    dp = dp_init(len(str_a), len(str_b))
    return rec(len(str_a), len(str_b), str_a, str_b, dp)

def rec(i, j, str_a, str_b, dp):
    if i == 0 or j == 0:
        return 0
    if dp[i-1][j-1] > 0:
        return dp[i-1][j-1]
    if str_a[i-1] == str_b[j-1]:
        dp[i-1][j-1] = rec(i-1, j-1, str_a, str_b, dp) + 1
        return dp[i-1][j-1]
    dp[i-1][j-1] = max(rec(i, j-1, str_a, str_b, dp), rec(i-1, j, str_a, str_b, dp))
    return dp[i-1][j-1]

nb_pairs = int(input())
pairs = []
for i in range(0, nb_pairs):
    pairs.append((input(), input()))

for i in range(0, nb_pairs):
    str_a, str_b = pairs[i]
    print(solve(str_a, str_b))

Submission status: Wrong Answer

Solution code:
import sys

def dp_init(m, n):
    return [[0] * n] * m

def solve(str_a, str_b):
    dp = dp_init(len(str_a), len(str_b))
    return rec(len(str_a), len(str_b), str_a, str_b, dp)

def rec(i, j, str_a, str_b, dp):
    if i-1 == 0 or j-1 == 0:
        return 0
    if dp[i-1][j-1] > 0:
        return dp[i-1][j-1]
    if str_a[i-1] == str_b[j-1]:
        dp[i-1][j-1] = rec(i-1, j-1, str_a, str_b, dp) + 1
        print("(%d, %d) : %d" % (i-1, j-1, dp[i-1][j-1]))
        return dp[i-1][j-1]
    dp[i-1][j-1] = max(rec(i, j-1, str_a, str_b, dp), rec(i-1, j, str_a, str_b, dp))
    print("(%d, %d) : %d" % (i-1, j-1, dp[i-1][j-1]))
    return dp[i-1][j-1]

nb_pairs = int(input())
pairs = []
for i in range(0, nb_pairs):
    pairs.append((input(), input()))

for i in range(0, nb_pairs):
    str_a, str_b = pairs[i]
    print(solve(str_a, str_b))

Submission status: Wrong Answer

Solution code:
import sys

def dp_init(m, n):
    ret = []
    for i in range(m):
        ret.append([None] * n)
    return ret

def solve(str_a, str_b):
    dp = dp_init(len(str_a), len(str_b))
    return rec(len(str_a), len(str_b), str_a, str_b, dp, 0)

def rec(i, j, str_a, str_b, dp, depth):
    if dp[i-1][j-1] is not None:
        #print(dp)
        #print(" "*depth + "(%d, %d) : %d - hit" % (i-1, j-1, dp[i-1][j-1]))
        return dp[i-1][j-1]
    if i-1 == 0 or j-1 == 0:
        dp[i-1][j-1] = 0
        #print(" "*depth + "(%d, %d) : %d - zero" % (i-1, j-1, dp[i-1][j-1]))
        return 0
    if str_a[i-1] == str_b[j-1]:
        dp[i-1][j-1] = rec(i-1, j-1, str_a, str_b, dp, depth+1) + 1
        #print(" "*depth + "(%d, %d) : %d" % (i-1, j-1, dp[i-1][j-1]))
        return dp[i-1][j-1]

    dp[i-1][j-1] = max(rec(i, j-1, str_a, str_b, dp, depth+1), rec(i-1, j, str_a, str_b, dp, depth+1))
    #print(" "*depth + "(%d, %d) : %d" % (i-1, j-1, dp[i-1][j-1]))
    return dp[i-1][j-1]

nb_pairs = int(input())
pairs = []
for i in range(0, nb_pairs):
    pairs.append((input(), input()))

for i in range(0, nb_pairs):
    str_a, str_b = pairs[i]
    print(solve(str_a, str_b))

Submission status: Wrong Answer

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

Solution code:
q = int(input())
for _ in range(q):
    X = input()
    Y = input()
    NX = len(X)
    NY = len(Y)
    dp = [[0] * (NY+1) for _ in range(NX+1)]
    jx = [0 for _ in range(NX)]
    jy = [0 for _ in range(NY)]
    for x in range(NX):
        for y in range(NY):
            if jx[x] == 0 and jy[y] == 0 and X[x] == Y[y]:
                dp[x+1][y+1] = max(dp[x][y+1], dp[x+1][y]) + 1
                jx[x] = 1
                jy[y] = 1
            else:
                dp[x+1][y+1] = max(dp[x][y+1], dp[x+1][y])

    print(dp[NX][NY])

Submission status: Wrong Answer

Solution code:
q = int(input())
ans = []
for _ in range(q):
    X = input()
    Y = input()
    NX = len(X)
    NY = len(Y)
    dp = [[0] * (NY+1) for _ in range(NX+1)]
    jx = [0 for _ in range(NX)]
    jy = [0 for _ in range(NY)]
    for x in range(NX):
        for y in range(NY):
            if jx[x] == 0 and jy[y] == 0 and X[x] == Y[y]:
                dp[x+1][y+1] = max(dp[x][y+1], dp[x+1][y]) + 1
                jx[x] = 1
                jy[y] = 1
            else:
                dp[x+1][y+1] = max(dp[x][y+1], dp[x+1][y])

    ans.append(dp[NX][NY])
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
q = int(input())
alphabet =[chr(ord('a') + i) for i in range(26)]

for _ in range (q):
    S1 = list(input())
    S2 = list(input())
    S1.sort()
    S2.sort()
    count = 0
    for i in alphabet:
        temp = min(S1.count(i),S2.count(i))
        if temp !=0:
            count +=1
    print(count)

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

Solution code:
q = int(input())
alphabet =[chr(ord('a') + i) for i in range(26)]

for _ in range (q):
    S1 = list(input())
    S2 = list(input())
    S1.sort()
    S2.sort()
    count = 0
    for i in alphabet:
        temp = min(S1.count(i),S2.count(i))
        if temp !=0:
            count +=temp
    print(count)

Submission status: Wrong Answer

Solution code:
q = int(input())


for __ in range (q):

    S1 = input()
    S2 = input()
    dp = [[0 for i in range(len(S2)+1+10)] for j in range(len(S1)+1+10)]


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

    print(dp[len(S1)][len(S2)])

Submission status: Wrong Answer

Solution code:
q = int(input())

for __ in range (q):

    S1 = input()
    S2 = input()
    dp = [[0 for i in range(len(S2)+1+10)] for j in range(len(S1)+1+10)]


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

    print(dp[len(S1)][len(S2)])

Submission status: Wrong Answer

Solution code:
from sys import stdin

X = [ 0 for i in range(1000) ]
Y = [ 0 for i in range(1000) ]
Z = [[0 for i in range(1000)]for i in range(1000)]

def getLCS() :
	xlen = len(X[l])
	ylen = len(Y[l])

	for i in range(1,xlen+1) :
		for j in range(1,ylen+1) :
			if X[i-1] == Y[j-1] : Z[i][j] = Z[i-1][j-1] + 1
			elif Z[i-1][j] >= Z[i][j-1] : Z[i][j] = Z[i-1][j]
			else : Z[i][j] = Z[i][j-1]

	return Z[xlen][ylen]

n = int(input())
for l in range(n) :
	X[l] = stdin.readline().strip()
	Y[l] = stdin.readline().strip()
	print(getLCS())

Submission status: Wrong Answer

Solution code:
def lcb():
    A = raw_input()
    B = raw_input()

    m = len(A)
    n = len(B)

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

    maxl = 0

    for i in range(1, m):
        for j in range(1, n):
            if A[i] == B[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            maxl = max(maxl, dp[i][j])

    return maxl

n = input()
for i2 in range(n):
    print lcb()

Submission status: Wrong Answer

Solution code:
def lcb():
    A = raw_input()
    B = raw_input()

    m = len(A)
    n = len(B)

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

    maxl = 0

    for i in range(1, m):
        for j in range(1, n):
            if A[i] == B[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            maxl = max(maxl, dp[i][j])

    return maxl + 1

n = input()
for _ in range(n):
    print lcb()

Submission status: Wrong Answer

Solution code:
def find_substr(s,t):
    flag=False
    i=0
    j=0
    n=0
    while i<len(s) and j<len(t):
        if s[i] == t[j]:
            i+=1
            j+=1
            n+=1
            continue
        elif  j < len(t)-1 and s[i] == t[j+1]:
            j+=2
            i+=1
            n+=1
        elif  i < len(s)-1 and s[i+1] == t[j]:
            i+=2
            j+=1
            n+=1
        else:
            i+=1
            j+=1
    return n

n = int(input())
for i in range(n):
    s = input()
    t = input()
    print(find_substr(s,t))

Submission status: Wrong Answer

Solution code:
def lcs(s, t):
  slen = len(s)
  tlen = len(t)
  dp = [None] * (slen + 1)

  for i in range(slen + 1):
    dp[i] = [0] * (tlen + 1)

  for i in range(1, slen + 1):
    for j in range(1, tlen + 1):
      if s[i-1] == t[j-1]:
        dp[i][j] = dp[i-1][j-1] + 1
      else:
        dp[i][j] = max(dp[i][j-1], dp[i-1][j])

  return dp[slen][tlen]

n = int(raw_input())

for i in range(min(n, 20)):
  x = raw_input()
  y = raw_input()
  print lcs(x, y)

Submission status: Wrong Answer

Solution code:
def find_substr(s,t):
    flag=False
    i=0
    j=0
    n=0
    while i<len(s) and j<len(t):
        if s[i] == t[j]:
            n+=1
            pass
        elif  j < len(t)-1 and s[i] == t[j+1]:
            j+=1
            n+=1
        elif  i < len(s)-1 and s[i+1] == t[j]:
            i+=1
            n+=1
        j+=1
        i+=1

    return n

n = int(input())

for i in range(n):
    s = input()
    t = input()
    print(find_substr(s,t))

Submission status: Wrong Answer

Solution code:
def lcs_size():
  X = raw_input()
  Y = raw_input()
  a = len(X)
  b = len(Y)
  z2 = [0 for i in range(b+1)]

  for i in range(a):
    ch = X[i]
    z1 = z2 + []
    for j in range(b):
      if ch == Y[j]:
        z2[j+1] = z1[j] + 1
      else:
        z2[j+1] = z2[j]

  return z2[-1]

q = input()
for k in range(q):
  print lcs_size()

Submission status: Wrong Answer

Solution code:

def LCS(x, y):
    dp = {}
    for i in range(len(x)+1):
        dp[i] = {0: i}
    for j in range(len(y)+1):
        dp[0][j] = j
    
    for i in range(1, len(x)+1):
        for j in range(1, len(y)+1):
            d = 0 if x[i-1] == y[j-1] else 1
            dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + d)
    
    longer = max(len(x), len(y))
    return (longer - dp[len(x)][len(y)])

q = int(raw_input())
for i in range(q):
    X = raw_input()
    Y = raw_input()
    print(LCS(X, Y))

Submission status: Wrong Answer

Solution code:
def edit_distance(s, t):
 s = raw_input()
 t = raw_input()
 dp = {}
 for i in range(len(s) + 1):
  dp[i] = {0: i}
 for j in range(len(t) + 1):
  dp[0][j] = j
 for i in range(1, len(s) + 1):
  for j in range(1, len(t) + 1):
   if (s[i-1] == t[j-1]): 
    d = 0
   else:
    dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + d)
 return dp[len(s)][len(t)]

Submission status: Wrong Answer

Solution code:
def edit_distance(s, t):
 s = raw_input()
 t = raw_input()
 dp = {}
 for i in range(len(s) + 1):
  dp[i] = {0: i}
 for j in range(len(t) + 1):
  dp[0][j] = j
 for i in range(1, len(s) + 1):
  for j in range(1, len(t) + 1):
   if (s[i-1] == t[j-1]): 
    d = 0
   else:
    dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + d)
 return dp[len(s)][len(t)]
n = input()
for p in range(n):
    print edit_distance

Submission status: Wrong Answer

Solution code:
def edit_distance(s, t):
 s = raw_input()
 t = raw_input()
 dp = {}
 for i in range(len(s) + 1):
  dp[i] = {0: i}
 for j in range(len(t) + 1):
  dp[0][j] = j
 for i in range(1, len(s) + 1):
  for j in range(1, len(t) + 1):
   if (s[i-1] == t[j-1]): 
    d = 0
   else:
    dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + d)
 return dp[len(s)][len(t)]
n = input()

Submission status: Wrong Answer

Solution code:
def solve():
  X = raw_input()
  Y = raw_input()
  a = len(X)
  b = len(Y)
  c1 = [0 for i in range(b+1)]
 
  for i in range(a):
    c2 = c1 + []
    for j in range(b):
      if X[i] == Y[j]:
        c2[j+1] = c1[j] + 1
      elif c2[j+1] < c2[j]:
        c2[j+1] = c2[j]
 
  return c2[-1]
 
n = input()
for k in range(n):
  print solve()

Submission status: Wrong Answer

Solution code:
# coding: UTF-8

# ??¢?´¢????????¢??°
# ?????°???(X?????¢?´¢????§??????????Y?????¢?´¢????§???????????????????X????????????Y)
def LCSSolver():
    X = raw_input().split()
    Y = raw_input().split()
    XN = len(X)
    YN = len(Y)
    LCSlength = 0
    six = 0
    siy = 0

    for iy in range(siy, YN):
        for ix in range(six, XN):
            if X[ix] == Y[iy]:
                LCSlength = LCSlength + 1
                six = ix + 1
                siy = iy + 1
                break

    return LCSlength

# ?????????
Repeat = input()

for i in range(Repeat):
    print LCSSolver()