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: Runtime Error

Solution code:
def lcs(x,y):
    xs = len(x)
    ys = len(y)
    x = " " + x
    y = " " + y
    c = [[0 for i in xrange(len(x))] for j in xrange(len(y))] 
 
 
    for i in xrange (1,ys+1):
        for j in xrange (1,xs+1):
            if x[j] == y[i]:
                a = 1
            else:
                a = 0
            c[i][j] = max(c[i][j-1],c[i-1][j],c[i-1][j-1] + a)
        m = max(m,c[i][j])
    return max(max(c))
 
n = input()
 
for i in xrange (n):
 
    x = raw_input()
    y = raw_input()
 
    print lcs(x,y)

Submission status: Runtime Error

Solution code:
def lcs(x,y):
    xs = len(x)
    ys = len(y)
    x = " " + x
    y = " " + y
    c = [[0 for i in xrange(len(x))] for j in xrange(len(y))]
    for i in xrange (1,ys+1):
        for j in xrange (1,xs+1):
            if x[j] == y[i]:
                a = 1
            else:
                a = 0
            c[i][j] = max(c[i][j-1],c[i-1][j],c[i-1][j-1] + a)
        m = max(m,c[i][j])
    return max(max(c))
 
n = input()
 
for i in xrange (n):
 
    x = raw_input()
    y = raw_input()
 
    print lcs(x,y)

Submission status: Runtime Error

Solution code:
def lcs(x,y):
    xs = len(x)
    ys = len(y)
    x = " " + x
    y = " " + y
    c = [[0 for i in xrange(len(x))] for j in xrange(len(y))]
    for i in xrange (1,ys+1):
        for j in xrange (1,xs+1):
            if x[j] == y[i]:
                a = 1
            else:
                a = 0
            c[i][j] = max(c[i][j-1],c[i-1][j],c[i-1][j-1] + a)
        m = max(m,c[i][j])
    return max(max(c))
n = input() 
for i in xrange (n): 
    x = raw_input()
    y = raw_input() 
    print lcs(x,y)

Submission status: Runtime Error

Solution code:
def lcs(x,y):
    xs = len(x)
    ys = len(y)
    x = " " + x
    y = " " + y
    c = [[0 for i in xrange(len(x))] for j in xrange(len(y))]
    for i in xrange (1,ys+1):
        for j in xrange (1,xs+1):
            if x[j] == y[i]:
                a = 1
            else:
                a = 0
            c[i][j] = max(c[i][j-1],c[i-1][j],c[i-1][j-1] + a)
        m = max(m,c[i][j])
    return max(max(c))
n = input() 
for i in xrange (n): 
    x = raw_input()
    y = raw_input() 
    print lcs(x,y)

Submission status: Runtime Error

Solution code:
def main():
    num = int(stdin.readline())
 
    for _ in xrange(num):
        x = stdin.readline().rstrip()
        y = stdin.readline().rstrip()
 
        n = len(y) + 1
 
        cim1 = [0] * n
        for i, xi in enumerate(x, start=1):
            ci = [0] * n
            for j, yj in enumerate(y, start=1):
                if xi == yj:
                    ci[j] = cim1[j-1] + 1
                elif cim1[j] >= ci[j-1]:
                    ci[j] = cim1[j]
                else:
                    ci[j] = ci[j-1]
            cim1 = ci
 
       print(ci[j])
 
 
main()

Submission status: Runtime Error

Solution code:
import itertools

q = int(input())
for a in range(q):
    X = input()
    Y = input()
    cost = [0]
    for c in Y:
        for i in range(len(cost) - 1, -1, -1):
            index = X.find(c, cost[i]) + 1
            if index:
                if i + 1 < len(cost):
                    cost[i + 1] = min(cost[i + 1], index)
                else:
                    cost.append(index)
    print(len(cost) - 1)

Submission status: Runtime Error

Solution code:
import sys

q = int(input())
for a in range(q):
    X = input()
    Y = input()
    cost = [0]
    for c in Y:
        for i in range(len(cost) - 1, -1, -1):
            index = X.find(c, cost[i]) + 1
            if index:
                if i + 1 < len(cost):
                    cost[i + 1] = min(cost[i + 1], index)
                else:
                    cost.append(index)
    print(len(cost) - 1)

Submission status: Runtime Error

Solution code:
def solve():
    x = raw_input()
    y = raw_input()
 
    a, b = len(x), len(y)
    x1 = [0 for k in range(b+1)]
    for i in xrange(a):
        e1 = x[i]
        x2 = x1+" "
        for j in xrange(b):
            if e1 == y[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1] < x1[j]:
                x1[j+1] = x1[j]
    return x1[-1]
 
n = input()
for i2 in range(n):
    print solve()

Submission status: Runtime Error

Solution code:
q = int(raw_input())
for i in range(0, q):
    X[i] = str(raw_input())
    Y[i] = str(raw_input())

def LCS(Max, X, Y):
    if len(X) == 0 or len(Y) == 0:
        return Max
        break
    else:
        return Max
    if X[len(X)] == Y[len(Y)]:
        Max = LCS(Max, X[:len(X)-1], Y[:len(Y)-1]) + 1
    else:
        Max = max(LCS(Max, X[:len(X)], Y[:len(Y)-1]), LCS(Max, X[:len(X)-1], Y[:len(Y)])

for i in range(0, q):
    Max = 0
    print LCS(Max, X[i], Y[i])

Submission status: Runtime Error

Solution code:
q = input()

X = map(int, raw_input().split))
Y = map(int, raw_input().split))

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

   print dp[len(s)][len(t)]

edit_distance(X, Y)

Submission status: Runtime Error

Solution code:
q = input()
 
X = map(int, raw_input().split))
Y = map(int, raw_input().split))
 
def edit_distance(s, t)
   dp = {}
    
   for i in range(0. len(s)):
      dp[i] = {0: i}
   for j in range(0, len(t)):
      dp[0][j] = j
    
   for i in range(1, len(s)):
      for j in range(1, len(t)):
          d = 0 if s[i-1] == j[i-1] else 1
          dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+d)
 
   print dp[len(s)][len(t)]

for k in range(0, q-1):
   edit_distance(X, Y)

Submission status: Runtime Error

Solution code:
n = int(input())
p = []
a,b = [int(x) for x in input().split()]
p.append(a)
p.append(b)
for i in range(1, n):
    c,d = [int(x) for x in input().split()]
    p.append(d)
# end input
# create dp table
dp = []
for x in range(n+1):
    dp.append([0] * (n+1))

for l in range(2, n+1):
    for i in range(1, n-l+2):
        j = i + l -1
        dp[i][j] = 9999999999

        for k in range(i, j):
            tmp = dp[i][k] + dp[k+1][j] + (p[i-1] * p[k] * p[j])
            if dp[i][j] > tmp:
                dp[i][j] = tmp
#print(dp)
print(dp[1][n])

Submission status: Runtime Error

Solution code:
q = input()
  
def edit_distance()
   X = raw_input()
   Y = raw_input()
     
   for i in range(0. len(X)):
      s[i] = i
     
   for i in range(1, len(X)):
      t = s + []
      for j in range(1, len(Y)):
         if s[i-1] == j[i-1]:
            s[j+1] = t[j] + 1
         elif [j+1] < s[j]:
            s[j+1] = t[j]
  
   return s[-1]
 
for k in range(0, q-1):
   edit_distance()

Submission status: Runtime Error

Solution code:
q = input()
   
def common()
   X = raw_input()
   Y = raw_input()
      
   for i in range(0. len(X)):
      s[i] = 0
      
   for i in range(1, len(X)):
      t = s + []
      for j in range(1, len(Y)):
         if s[i-1] == j[i-1]:
            s[j+1] = t[j] + 1
         elif [j+1] < s[j]:
            s[j+1] = t[j]
   
   return s[-1]
  
for k in range(0, q-1):
   common()

Submission status: Runtime Error

Solution code:
q = input()
    
def common()
   X = raw_input()
   Y = raw_input()
       
   for i in range(0. len(X)+1):
      s[i] = 0
       
   for i in range(1, len(X)):
      t = s + []
      for j in range(1, len(Y)):
         if s[i-1] == j[i-1]:
            s[j+1] = t[j] + 1
         elif s[j+1] < s[j]:
            s[j+1] = s[j]
    
   return s[-1]
   
for k in range(0, q):
   common()

Submission status: Runtime Error

Solution code:
q = input()
     
def common()
   X = raw_input()
   Y = raw_input()
        
   for i in range(0. len(X)+1):
      s[i] = 0
        
   for i in range(0, len(X)):
      t = s + []
      for j in range(1, len(Y)):
         if s[i] == j[i]:
            s[j+1] = t[j] + 1
         elif s[j+1] < s[j]:
            s[j+1] = s[j]
     
   return s[-1]
    
for k in range(0, q):
   common()

Submission status: Runtime Error

Solution code:
def common():
   X = raw_input()
   Y = raw_input()
         
   for i in range(0. len(X)+1):
      s[i] = 0
         
   for i in range(0, len(X)):
      t = s + []
      for j in range(1, len(Y)):
         if s[i] == j[i]:
            s[j+1] = t[j] + 1
         elif s[j+1] < s[j]:
            s[j+1] = s[j]
      
   return s[-1]

q = input()     
for k in range(0, q):
   common()

Submission status: Runtime Error

Solution code:
def common():
   X = raw_input()
   Y = raw_input()
          
   for i in range(0. len(X)+1):
      s[i] = 0
          
   for i in range(0, len(X)):
      t = s + []
      for j in range(0, len(Y)):
         if s[i] == j[i]:
            s[j+1] = t[j] + 1
         elif s[j+1] < s[j]:
            s[j+1] = s[j]
       
   return s[-1]
 
q = input()     
for k in range(0, q):
   common()

Submission status: Runtime Error

Solution code:
def common():
   X = raw_input()
   Y = raw_input()
           
   for i in range(0. len(X)+1):
      s[i] = 0
           
   for j in range(0, len(X)):
      t = s + []
      for k in range(0, len(Y)):
         if s[j] == j[k]:
            s[k+1] = t[k] + 1
         elif s[k+1] < s[k]:
            s[k+1] = s[k]
        
   return s[-1]
  
q = input()     
for l in range(0, q):
   common()

Submission status: Runtime Error

Solution code:
def common():
   X = raw_input()
   Y = raw_input()
            
   for i in range(0. len(Y)+1):
      s[i] = 0
            
   for j in range(0, len(X)):
      t = s + []
      for k in range(0, len(Y)):
         if s[j] == j[k]:
            s[k+1] = t[k] + 1
         elif s[k+1] < s[k]:
            s[k+1] = s[k]
         
   return s[-1]
   
q = input()     
for l in range(0, q):
   common()

Submission status: Runtime Error

Solution code:
def common():
   X = raw_input()
   Y = raw_input()
             
   for i in range(0, len(Y)+1):
      s[i] = 0
             
   for j in range(0, len(X)):
      t = s + []
      for k in range(0, len(Y)):
         if s[j] == j[k]:
            s[k+1] = t[k] + 1
         elif s[k+1] < s[k]:
            s[k+1] = s[k]
          
   return s[-1]
    
q = input()     
for l in range(0, q):
   common()

Submission status: Runtime Error

Solution code:
def common():
??????X = raw_input()
??????Y = raw_input()
????????????????????????????
??????for i in range(0, len(Y)+1):
????????????s[i] = 0
????????????????????????????
??????for j in range(0, len(X)):
????????????t = s + []
????????????for k in range(0, len(Y)):
??????????????????if X[j] == Y[k]:
????????????????????????s[k+1] = t[k] + 1
??????????????????elif s[k+1] < s[k]:
????????????????????????s[k+1] = s[k]
??????????????????????
??????return s[-1]
??????????
q = input()???????? 
for l in range(0, q):
??????common()

Submission status: Runtime Error

Solution code:
def common():
   X = raw_input()
   Y = raw_input()

   for i in range(0, len(Y)+1):
      s[i] = 0

   for j in range(0, len(X)):
      t = s + []
      for k in range(0, len(Y)):
         if X[j] == Y[k]:
            s[k+1] = t[k] + 1
         elif s[k+1] < s[k]:
            s[k+1] = s[k]

   return s[-1]
??????????
q = input()???????? 
for l in range(0, q):
   common()

Submission status: Runtime Error

Solution code:
ans = {}

roop = input()
for k in range(roop):
    str1 = raw_input()
    str2 = raw_input()
    for i in range(len(str1)):
        ans[i, -1] = 0
    for j in range(len(str2)):
        ans[-1, j] = 0
    for i in range (len(str1)):
        for j in range(len(str2)):
            if(str1[i] == str2[j]):
                ans[i, j] = ans[i - 1, j - 1] + 1
            else:
                ans[i, j] = max(ans[i - 1, j], ans[i, j - 1])
    print ans[len(str1) - 1, len(str2) - 1]

Submission status: Runtime Error

Solution code:
ans = [None] * 1000
for i in xrange(1000):
    ans[i] = [None] * 1000
for i in range(len1):
        ans[i][0] = 0
    for j in range(len2):
        ans[0][j] = 0
roop = input()
for k in range(roop):
    str1 = raw_input()
    str2 = raw_input()
    len1 = len(str1) + 1
    len2 = len(str2) + 1
    for i in range (1, len1):
        for j in range(1, len2):
            if(str1[i - 1] == str2[j - 1]):
                ans[i][j] = ans[i -1][j - 1] + 1
            else:
                ans[i][j] = max(ans[i - 1][j], ans[i][j - 1])
    print ans[len1 - 1][len2 - 1]

Submission status: Runtime Error

Solution code:
ans = [None] * 1000
for i in xrange(1000):
    ans[i] = [None] * 1000
for i in range(1000):
        ans[i][0] = 0
    for j in range(1000):
        ans[0][j] = 0
roop = input()
for k in range(roop):
    str1 = raw_input()
    str2 = raw_input()
    len1 = len(str1) + 1
    len2 = len(str2) + 1
    for i in range (1, len1):
        for j in range(1, len2):
            if(str1[i - 1] == str2[j - 1]):
                ans[i][j] = ans[i -1][j - 1] + 1
            else:
                ans[i][j] = max(ans[i - 1][j], ans[i][j - 1])
    print ans[len1 - 1][len2 - 1]

Submission status: Runtime Error

Solution code:
ans = [None] * 1000
for i in xrange(1000):
    ans[i] = [None] * 1000
for i in range(1000):
    ans[i][0] = 0
for j in range(1000):
    ans[0][j] = 0
    
roop = input()
for k in range(roop):
    str1 = raw_input()
    str2 = raw_input()
    len1 = len(str1) + 1
    len2 = len(str2) + 1
    for i in range (1, len1):
        for j in range(1, len2):
            if(str1[i - 1] == str2[j - 1]):
                ans[i][j] = ans[i -1][j - 1] + 1
            else:
                ans[i][j] = max(ans[i - 1][j], ans[i][j - 1])
    print ans[len1 - 1][len2 - 1]

Submission status: Runtime Error

Solution code:
def solve():
   x = raw_input()
   y = raw_input()
   lenx = len(x)
   leny = len(y)
   
   z = [0 for k in range(b+1)]
   for i in range(lenx):
      a = x[i]
      b = z + []
      for j in range(leny):
         if a == y[i]:
               z[j+1] = b[j] + 1
         elif z[j+1] < z[j]:
               
   print max(zz)

n = input()
for i in xrange(n):
   solve()

Submission status: Runtime Error

Solution code:
def solve():
   x = raw_input()
   y = raw_input()
   lenx = len(x)
   leny = len(y)
   
   z = [0 for k in range(b+1)]
   for i in range(lenx):
      a = x[i]
      b = z + []
      for j in range(leny):
         if a == y[i]:
               z[j+1] = b[j] + 1
         elif z[j+1] < z[j]:
               
   print max(z)

n = input()
for i in xrange(n):
   solve()

Submission status: Runtime Error

Solution code:
def solve():
   x = raw_input()
   y = raw_input()
   lenx = len(x)
   leny = len(y)
   
   z = [0 for k in range(b+1)]
   for i in range(lenx):
      a = x[i]
      b = z + []
      for j in xrange(leny):
         if a == y[i]:
               z[j+1] = b[j] + 1
         elif z[j+1] < z[j]:
               z[j+1] = z[j]
               
   print max(z)

n = input()
for i in xrange(n):
   solve()

Submission status: Runtime Error

Solution code:
def solve():
   x = raw_input()
   y = raw_input()
   lenx = len(x)
   leny = len(y)
   
   z = [0 for k in range(lenx)]
   for i in range(lenx):
      a = x[i]
      b = z + []
      for j in xrange(leny):
         if a == y[i]:
               z[j+1] = b[j] + 1
         elif z[j+1] < z[j]:
               z[j+1] = z[j]
               
   print max(z)

n = input()
for i in xrange(n):
   solve()

Submission status: Runtime Error

Solution code:
def solve():
   x = raw_input()
   y = raw_input()
   lenx = len(x)
   leny = len(y)
   
   z = [0 for k in range(lenx)]
   for i in range(lenx):
      a = x[i]
      b = z + []
      for j in range(leny):
         if a == y[i]:
               z[j+1] = b[j] + 1
         elif z[j+1] < z[j]:
               z[j+1] = z[j]
               
   print max(z)

n = input()
for i in range(n):
   solve()

Submission status: Runtime Error

Solution code:
def solve():
   x = raw_input()
   y = raw_input()
   lenx = len(x)
   leny = len(y)
   
   x1 = [0 for k in range(lenx)]
   for i in range(lenx):
      a = x[i]
      x2 = x1 + []
      for j in range(leny):
         if a == y[i]:
               x1[j+1] = x2[j] + 1
         elif x1[j+1] < x1[j]:
               x1[j+1] = x1[j]
               
   print max(x1)

n = input()
for i in range(n):
   solve()

Submission status: Runtime Error

Solution code:
def solve():
  x = raw_input()
  y = raw_input()
  a, b = len(x), len(y)
  
  dsp1 = [0 for i in xrange(b+1)]
  for i in xrange(a):
    dsp2 = dsp1+[]
    for j in xrange(b):
      if x[i] == y[j]:
      dsp1[j+1] = dsp2[j] + 1
    elif dsp1[j+1] < dsp1[j]:
      dsp1[j+1] = dsp1[j]
  print max(dsp1)
   
  n = input()
  for a in xrange(n):
    solve()

Submission status: Runtime Error

Solution code:
def solveZ(X, Y, Z, x, y):
	if x < len(X) and y < len(Y):
		ans = [solveZ(X, Y, Z, x, y+1)]
		Z.append(Y[y])
		for j in range(x, len(X)):
			if Y[y] == X[j]:
				ans.append(solveZ(X, Y, Z, j+1, y+1))
		return max(ans)
	else:
		return len(Z)

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

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

Submission status: Runtime Error

Solution code:
def solveZ(X, Y, Z, x, y):
	if x < len(X) and y < len(Y):
		ans = [solveZ(X, Y, Z, x, y+1)]
		for j in range(x, len(X)):
			if Y[y] == X[j]:
                                Z2 = Z + str(Y[y])
				ans.append(solveZ(X, Y, Z2, j+1, y+1))
                                break
                return max(ans)
	else:
                print(Z)
		return len(Z)

q = int(input())
ans = [[] for i in range(q)]
for i in range(q):
	X = str(input())
	Y = str(input())
	ans[i] = solveZ(X, Y, "", 0, 0)

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

Submission status: Runtime Error

Solution code:
def solveZ(X, Y, Z, x, y):
	if x < len(X) and y < len(Y):
		ans = [solveZ(X, Y, Z, x, y+1)]
		for j in range(x, len(X)):
			if Y[y] == X[j]:
                                Z2 = Z + str(Y[y])
				ans.append(solveZ(X, Y, Z2, j+1, y+1))
                                break
                return max(ans)
	else:
                print(Z)
		return len(Z)

q = int(input())
ans = [[] for i in range(q)]
for i in range(q):
	X = str(raw_input())
	Y = str(raw_input())
	ans[i] = solveZ(X, Y, "", 0, 0)

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

Submission status: Runtime Error

Solution code:
def solveZ(X, Y, Z, x, y):
	if x < len(X) and y < len(Y):
		ans = [solveZ(X, Y, Z, x, y+1)]
		for j in range(x, len(X)):
			if Y[y] == X[j]:
                                Z2 = Z + str(Y[y])
				ans.append(solveZ(X, Y, Z2, j+1, y+1))
                                break
                return max(ans)
	else:
                print(Z)
		return len(Z)

q = int(input())
ans = [[] for i in range(q)]
for i in range(q):
	X = raw_input()
	Y = raw_input()
	ans[i] = solveZ(str(X), str(Y), "", 0, 0)

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

Submission status: Runtime Error

Solution code:
def lcs():
???x, y = raw_input()
???x_len = len(x)
???y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

???for j in range(x_len):
    ???z1 = z2 + []
      for k in range(y_len):
         if x[k] = y[k]:
            z2[k+1] = z2[k] + 1
         elif z2[j+1] = z2[j]:???
?????????      z2[j+1] = z2[j]

  return z2[-1]

num = input()
for l in range(num):
   print lcs()

Submission status: Runtime Error

Solution code:
def lcs():
???x, y = raw_input()
???x_len = len(x)
  y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

???for j in range(x_len):
   z1 = z2 + []
    for k in range(y_len):
       if x[k] = y[k]:
          z2[k+1] = z2[k] + 1
       elif z2[j+1] = z2[j]:???
?????????    z2[j+1] = z2[j]

  return z2[-1]

num = input()
for l in range(num):
  print lcs()

Submission status: Runtime Error

Solution code:
def lcs():
???x, y = raw_input()
???x_len = len(x)
  y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

???for j in range(x_len):
   z1 = z2 + []
    for k in range(y_len):
       if x[k] = y[k]:
          z2[k+1] = z2[k] + 1
       elif z2[j+1] < z2[j]:???
?????????    z2[j+1] = z2[j]

  return z2[-1]

num = input()
for l in range(num):
  print lcs()

Submission status: Runtime Error

Solution code:
def lcs():
???x = raw_input()
  y = raw_input()
???x_len = len(x)
  y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

???for j in range(x_len):
   z1 = z2 + []
    for k in range(y_len):
       if x[k] = y[k]:
          z2[k+1] = z2[k] + 1
       elif z2[j+1] < z2[j]:???
?????????    z2[j+1] = z2[j]

  return z2[-1]

num = input()
for l in range(num):
  print lcs()

Submission status: Runtime Error

Solution code:
def lcs():
???x = raw_input()
  y = raw_input()
???x_len = len(x)
  y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

???for j in range(x_len):
   z1 = z2 + []
   for k in range(y_len):
      if x[k] = y[k]:
         z2[k+1] = z2[k] + 1
      elif z2[j+1] < z2[j]:???
?????????   z2[j+1] = z2[j]

  return z2[-1]

num = input()
for l in range(num):
  print lcs()

Submission status: Runtime Error

Solution code:
def lcs():
???x = raw_input()
  y = raw_input()
???x_len = len(x)
  y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

???for j in range(x_len):
   z1 = z2 + []
   for k in range(y_len):
      if x[k] = y[k]:
         z2[k+1] = z2[k] + 1
      elif z2[k+1] < z2[k]:???
?????????   z2[k+1] = z2[k]

  return z2[-1]

num = input()
for l in range(num):
  print lcs()

Submission status: Runtime Error

Solution code:
def lcs():
???x = raw_input()
  y = raw_input()
???x_len = len(x)
  y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

???for j in range(x_len):
   z1 = z2 + []
   for k in range(y_len):
      if x[i] = y[k]:
         z2[k+1] = z2[k] + 1
      elif z2[k+1] < z2[k]:???
?????????   z2[k+1] = z2[k]

  return z2[-1]

num = input()
for l in range(num):
  print lcs()

Submission status: Runtime Error

Solution code:
def lcs():
???x = raw_input()
  y = raw_input()
???x_len = len(x)
  y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

???for j in range(x_len):
   z1 = z2 + []
   for k in range(y_len):
      if x[i] == y[k]:
         z2[k+1] = z2[k] + 1
      elif z2[k+1] < z2[k]:???
?????????   z2[k+1] = z2[k]

  return z2[-1]

num = input()
for l in range(num):
  print lcs()

Submission status: Runtime Error

Solution code:
def lcs():
???x = raw_input()
  y = raw_input()
???x_len = len(x)
  y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

???for j in range(x_len):
   z1 = z2 + []
   for k in range(y_len):
      if x[i] == y[k]:
         z1[k+1] = z2[k] + 1
      elif z1[k+1] < z1[k]:???
?????????   z1[k+1] = z1[k]

  return z2[-1]

num = input()
for l in range(num):
  print lcs()

Submission status: Runtime Error

Solution code:
def lcs():
???x = raw_input()
  y = raw_input()
???x_len = len(x)
  y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

???for j in range(x_len):
   z2 = z1 + []
   for k in range(y_len):
      if x[i] == y[k]:
         z1[k+1] = z2[k] + 1
      elif z1[k+1] < z1[k]:???
?????????   z1[k+1] = z1[k]

  return z2[-1]

num = input()
for l in range(num):
  print lcs()

Submission status: Runtime Error

Solution code:
def lcs():
???x = raw_input()
  y = raw_input()
???x_len = len(x)
  y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

???for j in range(x_len):
   z2 = z1 + []
   for k in range(y_len):
      if x[i] == y[k]:
         z1[k+1] = z2[k] + 1
      elif z1[k+1] < z1[k]:???
?????????   z1[k+1] = z1[k]

  return z1[-1]

num = input()
for l in range(num):
  print lcs()

Submission status: Runtime Error

Solution code:
def lcs():
???x = raw_input()
  y = raw_input()
???x_len = len(x)
  y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

???for i in range(x_len):
   z1 = z2 + []
   ele = x[i]
   for k in range(y_len):
      if x[i] == y[k]:
         z1[k+1] = z2[k] + 1
      elif z1[k+1] < z1[k]:???
?????????   z1[k+1] = z1[k]

  return z1[-1]

num = input()
for l in range(num):
  print lcs()

Submission status: Runtime Error

Solution code:
def lcs():
???x = raw_input()
  y = raw_input()
???x_len = len(x)
  y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

???for i in range(x_len):
   z1 = z2 + []
   ele = x[i]
   for k in range(y_len):
      if ele == y[k]:
         z2[k+1] = z1[k] + 1
      elif z2[k+1] < z2[k]:???
?????????   z2[k+1] = z2[k]

  return z2[-1]

num = input()
for l in range(num):
  print lcs()

Submission status: Runtime Error

Solution code:
def lcs():
???x = raw_input()
  y = raw_input()
???x_len = len(x)
  y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

  for i in range(x_len):
    z1 = z2 + []
    ele = x[i]
    for k in range(y_len):
      if ele == y[k]:
         z2[k+1] = z1[k] + 1
      elif z2[k+1] < z2[k]:???
?????????   z2[k+1] = z2[k]

  return z2[-1]

num = input()
for l in range(num):
  print lcs()

Submission status: Runtime Error

Solution code:
def lcs():
???x = raw_input()
  y = raw_input()
???x_len = len(x)
  y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

  for i in range(x_len):
    z1 = z2 + []
    ele = x[i]
    for k in range(y_len):
      if ele == y[k]:
         z2[k+1] = z1[k] + 1
      elif z2[k+1] < z2[k]:???
?????????   z2[k+1] = z2[k]

  return z2[-1]

num = input()
for j in range(num):
  print lcs()

Submission status: Runtime Error

Solution code:
def lcs()
  x = raw_input()
  y = raw_input()
  x_len = len(x)
  y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

  for i in range(x_len):
    z1 = z2 + []
    ele = x[i]
    for k in range(y_len):
      if ele == y[k]:
        z2[k+1] = z1[k] + 1
      elif z2[k+1] < z2[k]:???
        z2[k+1] = z2[k]

  return z2[-1]

num = input()
for j in range(num):
  print lcs()

Submission status: Runtime Error

Solution code:
def lcs():
  x = raw_input()
  y = raw_input()
  x_len = len(x)
  y_len = len(y)
  z2 = [0 for i in range(y_len+1)]

  for i in range(x_len):
    z1 = z2 + []
    ele = x[i]
    for k in range(y_len):
      if ele == y[k]:
        z2[k+1] = z1[k] + 1
      elif z2[k+1] < z2[k]:???
        z2[k+1] = z2[k]

  return z2[-1]

num = input()
for j in range(num):
  print lcs()

Submission status: Runtime Error

Solution code:
q = int(input())

def Longest_Common(q) :
    X = raw_input()
    Y = raw_input()
    dp = [ [0 for i in range( len(X) )] for j in range( len(Y) )] #???X??????Y?????????????????????
    
    for j in range( len(Y) ):
        if Y[j] == X[0] :
            dp[j][0] += 1
        if( j+1 <= len(Y) - 1 ) :
            dp[j+1][0] = dp[j][0]

    for i in range( 1,len(X) ):
        if X[i] == Y[0] :
            dp[0][i] += 1
        if( i+1 <= len(X) - 1 ) :
            dp[i+1][0] = dp[i][0]
        
    for i in range( 1,len(X) ): 
        for j in range( 1,len(Y) ):
            if X[i] == Y[j] : dp[j][i] = max( dp[j-1][i-1], dp[j-1][i], dp[j][i-1]) + 1 
            else : dp[j][i] = max( dp[j-1][i-1], dp[j-1][i], dp[j][i-1])
                
    print dp[ len(Y)-1 ][ len(X)-1 ]    
    
    if( q == 1 ) :
        return
    else :
        Longest_Common(q-1)
        
Longest_Common(q)

Submission status: Runtime Error

Solution code:

q = int(input())

def Longest_Common(q) :
    X = raw_input()
    Y = raw_input()
    dp = [ [0 for i in range( len(X) )] for j in range( len(Y) )] #???X??????Y?????????????????????
    
    for j in range( len(Y) ):
        if Y[j] == X[0] :
            dp[j][0] += 1
        if( j+1 <= len(Y) - 1 ) :
            dp[j+1][0] = dp[j][0]

    for i in range( 1,len(X) ):
        if X[i] == Y[0] :
            dp[0][i] += 1
        if( i+1 <= len(X) - 1 ) :
            dp[0][i+1] = dp[0][i+1]
        
    for i in range( 1,len(X) ): 
        for j in range( 1,len(Y) ):
            if X[i] == Y[j] : dp[j][i] = max( dp[j-1][i-1], dp[j-1][i], dp[j][i-1]) + 1 
            else : dp[j][i] = max( dp[j-1][i-1], dp[j-1][i], dp[j][i-1])
                
    print dp[ len(Y)-1 ][ len(X)-1 ]    
    
    if( q == 1 ) :
        return
    else :
        Longest_Common(q-1)
        
Longest_Common(q)

Submission status: Runtime Error

Solution code:
q = int(input())

def Longest_Common(q) :
    X = raw_input()
    Y = raw_input()
    dp = [ [0 for i in range( len(X) )] for j in range( len(Y) )] #???X??????Y?????????????????????
    
    for j in range( len(Y) ):
        if Y[j] == X[0] :
            dp[j][0] += 1
        if( j+1 <= len(Y) - 1 ) :
            dp[j+1][0] = dp[j][0]

    for i in range( 1,len(X) ):
        if X[i] == Y[0] :
            dp[0][i] += 1
        if( i+1 <= len(X) - 1 ) :
            dp[0][i+1] = dp[0][i+1]
        
    for i in range( 1,len(X) ): 
        for j in range( 1,len(Y) ):
            if X[i] == Y[j] : dp[j][i] = max( dp[j-1][i-1], dp[j-1][i], dp[j][i-1]) + 1 
            else : dp[j][i] = max( dp[j-1][i-1], dp[j-1][i], dp[j][i-1])
                
    print dp[ len(Y)-1 ][ len(X)-1 ]    
    
    if( q == 1 ) :
        return
    else :
        Longest_Common(q-1)
        
Longest_Common(q)

Submission status: Runtime Error

Solution code:
q = input()


for i in range(q):
  X[i] = raw_input()
  Y[i] = raw_input()

for i in range(q):
  count = 0
  for j in range(q):
    if X[i][j] == Y[i][j]:
      count += 1

  print count

Submission status: Runtime Error

Solution code:
def com():
????x = raw_input()
????a = len(x)
  y = raw_input()
????b = len(y)

????k1 = [0 for i in range(b+1)]
????
????for i in range(a):
????????k2 = k1 + [ ]
????????for j in range(b):
????????????if k1[j+1] < k1[j]:
???????????????? k1[j+1] = k1[j]
????    elif x[i] == y[j]:
????????????????    k1[j+1] = k2[j] + 1
??????????return k1[-1]

n = input()
for l in range(n):
????print com()

Submission status: Runtime Error

Solution code:
def com():
????x = raw_input()
????a = len(x)
  y = raw_input()
????b = len(y)

????k1 = [0 for i in range(b+1)]
????
????for i in range(a):
????????k2 = k1 + [ ]
????????for j in range(b):
????????????if k1[j+1] < k1[j]:
???????????????? k1[j+1] = k1[j]
????    elif x[i] == y[j]:
????????????????    k1[j+1] = k2[j] + 1
  return k1[-1]

n = input()
for l in range(n):
????print com()

Submission status: Runtime Error

Solution code:
def com():
????x = raw_input()
????a = len(x)
  y = raw_input()
????b = len(y)

????k1 = [0 for i in range(b+1)]
????
????for i in range(a):
????????k2 = k1 + [ ]
????????for j in range(b):
????????????if k1[j+1] < k1[j]:
????????????????k1[j+1] = k1[j]
????    elif x[i] == y[j]:
?????????????? k1[j+1] = k2[j] + 1
  
  return k1[-1]

n = input()
for l in range(n):
????print com()