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 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 x[i] == y[j]:
?????????????? k1[j+1] = k2[j] + 1
      elif k1[j+1] < k1[j]:
????????????????k1[j+1] = k1[j]
  
  return k1[-1]

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

Submission status: Runtime Error

Solution code:
def solve_lcs():
    x = raw_input()
    y = raw_input()
 
    a = len(x)
    y = len(y)
    c1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = x[i]
        c2 = c1+[]
        for j in range(b):
            if e1 == y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
 
n = input()
for i2 in range(n):
    print solve_lcs()

Submission status: Runtime Error

Solution code:
def lcs(x, y)
  for i in range(1, len(x)):
    for j in range(1, lem(y)):
      if x[i] = y[j]:
        c[i][j] = c[i-1][j-1] + 1
      elif c[i-1][j]>c[i][j-1]:
        c[i][j] = c[i-1][j]
      else:
        c[i][j] = c[i][j-1]
      if maxl<c[i][j]:
        maxl = c[i][j]

  return maxl




q  = input()
x = [' ' for row in range(n+1)]
y = [' ' for row in range(n+1)]
c = [[' ' for col in range(1000)] for row in range(1000)]
maxl = 0
for i in range(q):
  x = input()
  y = input()
  print lcs(x, y)

Submission status: Runtime Error

Solution code:
def sakujo();
url1 = raw_input()
url2 = raw_input()

a, b = len(url1), len(url2)
x = [0 for i in range(b+1)]
for i in range(a):
e1 = url1[i]
y = x+[]
for j in range(b):
if e1 == url2[j]:
x[j+1] = y[j] + 1
elif x1[j+1] < x[j]:
x[j+1] = x[j]
return x[-1]


n=input()
for ix in range(n):
def sakujo

Submission status: Runtime Error

Solution code:
def sakujo();
seq1 = raw_input()
seq2 = raw_input()

a, b = len(seq1), len(seq2)
x1 = [0 for i in range(b+1)]
for i in range(a):
e1 = seq1[i]
x2 = x1+[]
for j in range(b):
if e1 == seq2[j]:
x1[j+1] = x2[j] + 1
elif x1[j+1] < x1[j]:
x1[j+1] = x1[j]
return x1[-1]


n=input()
for ix in range(n):
def sakujo

Submission status: Runtime Error

Solution code:
def sakujo();
seq1 = raw_input()
seq2 = raw_input()

a, b = len(seq1), len(seq2)
x1 = [0 for i in range(b+1)]
for i in range(a):
e1 = seq1[i]
x2 = x1+[]
for j in range(b):
if e1 == seq2[j]:
x1[j+1] = x2[j] + 1
elif x1[j+1] < x1[j]:
x1[j+1] = x1[j]
return x1[-1]


n=input()
for i in range(n):
def sakujo

Submission status: Runtime Error

Solution code:
def lcs(x, y):
  for i in range(1, len(x)):
    for j in range(1, len(y)):
      if x[i] == y[j]:
        c[i][j] = c[i-1][j-1] + 1
      elif c[i-1][j]>c[i][j-1]:
        c[i][j] = c[i-1][j]
      else:
        c[i][j] = c[i][j-1]
      if maxl<c[i][j]:
        maxl = c[i][j]

  return maxl




q  = input()
x = [' ' for row in range(q+1)]
y = [' ' for row in range(q+1)]
c = [[' ' for col in range(1000)] for row in range(1000)]
maxl = 0
for i in range(q):
  x = raw_input()
  y = raw_input()
  print lcs(x, y)

Submission status: Runtime Error

Solution code:
def sakujo():
 moji1 = raw_input()
 moji2 = raw_input()
  
 a, b = len(moji1), len(moji2)
 x1 = [for i in range(b+1)]
 for i in range(a):
  e1 = seq1[i]
  x2 = x1+[]
  for j in range(b):
   if e1 == moji2[j]:
    x1[j+1] = x2[j] + 1
   elif x1[j+1] < x1[j]:
    x1[j+1] = x1[j]
 return x1[-1]

 
n=input()
for ix in range(n):
 def sakujo

Submission status: Runtime Error

Solution code:
def sakujo():
 moji1 = raw_input()
 moji2 = raw_input()
  
 a, b = len(moji1), len(moji2)
 x1 = [0 for i in range(b+1)]
 for i in range(a):
  e1 = seq1[i]
  x2 = x1+[]
  for j in range(b):
   if e1 == moji2[j]:
    x1[j+1] = x2[j] + 1
   elif x1[j+1] < x1[j]:
    x1[j+1] = x1[j]
 return x1[-1]

 
n=input()
for ix in range(n):
 def sakujo

Submission status: Runtime Error

Solution code:
def sakujo():
 moji1 = raw_input()
 moji2 = raw_input()
  
 a, b = len(moji1), len(moji2)
 x1 = [0 for i in range(b+1)]
 for i in range(a):
  e1 = moji1[i]
  x2 = x1+[]
  for j in range(b):
   if e1 == moji2[j]:
    x1[j+1] = x2[j] + 1
   elif x1[j+1] < x1[j]:
    x1[j+1] = x1[j]
 return x1[-1]

 
n=input()
for ix in range(n):
 def sakujo

Submission status: Runtime Error

Solution code:
def lcs(maxl):
  for i in range(1, len(x)):
    for j in range(1, len(y)):
      if x[i] == y[j]:
        c[i][j] = c[i-1][j-1] + 1
      elif c[i-1][j]>c[i][j-1]:
        c[i][j] = c[i-1][j]
      else:
        c[i][j] = c[i][j-1]
      if maxl<c[i][j]:
        maxl = c[i][j]

  return maxl



q  = input()
x = [' ' for row in range(q+1)]
y = [' ' for row in range(q+1)]
c = [[0 for col in range(1000)] for row in range(1000)]
maxl = 0
for i in range(q):
  x = ' ' + raw_input()
  y = ' ' + raw_input()
  print lcs(maxl)

Submission status: Runtime Error

Solution code:
def lcs():
  for i in range(1, len(x)):
    for j in range(1, len(y)):
      if x[i] == y[j]:
        c[i][j] = c[i-1][j-1] + 1
      elif c[i-1][j]>c[i][j-1]:
        c[i][j] = c[i-1][j]
      else:
        c[i][j] = c[i][j-1]
      if maxl<c[i][j]:
        maxl = c[i][j]

  return maxl



q  = input()
x = [' ' for row in range(q+1)]
y = [' ' for row in range(q+1)]
c = [[0 for col in range(1001)] for row in range(1001)]
maxl = 0
for i in range(q):
  x = ' ' + raw_input()
  y = ' ' + raw_input()
  print lcs()

Submission status: Runtime Error

Solution code:
def lcs(maxl):
  for i in range(1, len(x)):
    for j in range(1, len(y)):
      if x[i] == y[j]:
        c[i][j] = c[i-1][j-1] + 1
      elif c[i-1][j]>c[i][j-1]:
        c[i][j] = c[i-1][j]
      else:
        c[i][j] = c[i][j-1]
      if maxl<c[i][j]:
        maxl = c[i][j]

  return maxl



q  = input()
x = [' ' for row in range(q+1)]
y = [' ' for row in range(q+1)]
#c = [[0 for col in range(1001)] for row in range(1001)]
maxl = 0
for i in range(q):
  x = ' ' + raw_input()
  y = ' ' + raw_input()
  print lcs(maxl)

Submission status: Runtime Error

Solution code:
def longest():
    moji1 = raw_input()
    moji2 = raw_input()
  
    a, b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]

    for i in range(a):
        e1 = moji1[i]
        x2 = x1+[]
        for j in range(b):
            if e1 == moji2[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1] < x1[j]:
                x1[j+1] = x1[j]

    return x1[-1]
  
n = input()
for i in range(n):
    print longest()

Submission status: Runtime Error

Solution code:
def lcs(count):
  while 1:
    if i>len(x) or j>len(y):
      break
    if x[i] == y[j]:
      count += 1
      i += 1
      j += 1
    elif j<len(y) and x[i] == y[j+1]:
      count += 1
      i += 1
      j += 2
    elif i<len(x) and x[i+1] == y[j]:
      count += 1
      i += 2
      j += 1

  return count



q  = input()
x = ['' for row in range(q+1)]
y = ['' for row in range(q+1)]
c = [[0 for col in range(1001)] for row in range(1001)]
count = 0
for i in range(q):
  x = ' ' + raw_input()
  y = ' ' + raw_input()
  print lcs(maxl)

Submission status: Runtime Error

Solution code:
def LCS():
  x = raw_input()
  y = raw_input()
  X = len(x)
  Y = len(y)
  
  for i in range(X):
    c[i][0] = 0
  for j in range(Y):
    c[0][j] = 0

  for i in range(X):
    for j in range(Y):
      if X[i] == Y[i]: 
        c[i][j] = c[i - 1][j - 1] + 1
      elif c[i - 1][j] >= c[i][j - 1]:
        c[i][j] = c[i - 1][j]
      else:
        c[i][j] = c[i][j - 1]
  print c[X][Y]

q = input()

for i in range(q):
  LCS()

Submission status: Runtime Error

Solution code:
def LCS():
  x = raw_input()
  y = raw_input()
  X = len(x)
  Y = len(y)
  
  for i in range(X):
    c[i][0] = 0
  for j in range(Y):
    c[0][j] = 0

  for i in range(X):
    for j in range(Y):
      if X[i] == Y[i]: 
        c[i][j] = c[i - 1][j - 1] + 1

      elif c[i - 1][j] >= c[i][j - 1]:
        c[i][j] = c[i - 1][j]

      else:
        c[i][j] = c[i][j - 1]

  print c[X][Y]

q = input()

for i in range(q):
  LCS()

Submission status: Runtime Error

Solution code:
def LCS():
  x = raw_input()
  y = raw_input()
  X = len(x)
  Y = len(y)
  
  for i in range(X):
    c[i][0] = 0
  for j in range(Y):
    c[0][j] = 0

  for i in range(X):
    for j in range(Y):
      if X[i] == Y[i]: 
        c[i][j] = c[i - 1][j - 1] + 1

      elif:
        max(c[i - 1][j], c[i][j - 1])
        

  print c[X][Y]

q = input()

for i in range(q):
  LCS

Submission status: Runtime Error

Solution code:
def LCS():
  x = raw_input()
  y = raw_input()
  X = len(x)
  Y = len(y)
  
  for i in range(X):
    c[i][0] = 0
  for j in range(Y):
    c[0][j] = 0

  for i in range(X):
    for j in range(Y):
      if X[i] == Y[i]: 
        c[i][j] = c[i - 1][j - 1] + 1

      elif:
        c[i][j] = max(c[i - 1][j], c[i][j - 1])
        

  print c[X][Y]

q = input()

for i in range(q):
  LCS

Submission status: Runtime Error

Solution code:
def count(str1, str2):
    cnt = 0
    count_map = [[for j in range(len(str2) + 1)] for i in range(len(str1) + 1)]

    for i in range(len(str1) + 1):
        count_map[i][0] = 0
    for j in range(len(str2) + 1):
        count_map[0][j] = 0


    for i in range(len(str1)):
        for j in range(len(str2)):
            if str1[i] == str2[j]:
                count_map[i][j] = count_map[i - 1][j - 1] + 1
            else:
                count_map[i][j] = max(count_map[i - 1][j], count_map[i][j - 1])
        cnt = max(max, count_map[i][j])

    return count_map[i][j]

p = input()

for i in range(p):
    X = raw_input()
    Y = raw_input()
    ans = count(X, Y)
    print ans

Submission status: Runtime Error

Solution code:
def LCS():
  x = raw_input()
  y = raw_input()
  X = len(x)
  Y = len(y)

  lcs = 0
  for i in range(X + 1):
    c[i][0] = 0
  for j in range(Y + 1):
    c[0][j] = 0

  for i in range(1,X + 1):
    for j in range(1, Y + 1):
      if X[i] == Y[j]: 
        c[i][j] = c[i - 1][j - 1] + 1

      else:
        c[i][j] = max(c[i - 1][j], c[i][j - 1])
  lcs = max(c[i][j], lcs)

  print lcs

q = input()

for i in range(q):
  LCS()

Submission status: Runtime Error

Solution code:
def LCS():
    seq1 = raw_input()
    seq2 = raw_input()
 
    a, b = len(seq1), len(seq2)
    for i in range(b + 1):
      x1[i] = 0 
    for i in range(a):
        e1 = seq1[i]
        c2 = c1+[]
        for j in range(b):
            if e1 == seq2[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
 
n = input()
for i in range(n):
    print LCS()

Submission status: Runtime Error

Solution code:
def LCS():
    seq1 = raw_input()
    seq2 = raw_input()
 
    a, b = len(seq1), len(seq2)
    for i in range(b + 1):
      c1[i] = 0 
    for i in range(a):
        e1 = seq1[i]
        c2 = c1+[]
        for j in range(b):
            if e1 == seq2[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
 
n = input()
for i in range(n):
    print LCS()

Submission status: Runtime Error

Solution code:
def LCS():
    seq1 = raw_input()
    seq2 = raw_input()
 
    a, b = len(seq1), len(seq2)
    for i in range(b + 1):
      c1[i] = 0 
    for i in range(a):
        e1 = seq1[i]
        c2 = c1+[]
        for j in range(b):
            if e1 == seq2[j]:
                c1[j + 1] = c2[j] + 1
            elif c1[j + 1] < c1[j]:
                c1[j + 1] = c1[j]
    return c1[-1]
 
n = input()
for i in range(n):
    print LCS()

Submission status: Runtime Error

Solution code:
def LCS():
    seq1 = raw_input()
    seq2 = raw_input()
 
    a, b = len(seq1), len(seq2)
    for i in range(b + 1):
      c1[i] = 0 
    for i in range(a):
        e1 = seq1[i]
        c2 = c1+[]
        for j in range(b):
            if e1 == seq2[j]:
                c1[j + 1] = c2[j] + 1
            elif c1[j + 1] < c1[j]:
                c1[j + 1] = c1[j]
    return c1[-1]
 
n = input()
for i2 in range(n):
    print LCS()

Submission status: Runtime Error

Solution code:

def LCS():
  x = raw_input()
  y = raw_input()
  X = len(x)
  Y = len(y)
  
  for i in range(X):
    c[i][0] = 0
  for j in range(Y):
    c[0][j] = 0


  for i in range(X):
    for j in range(Y):
      if X[i] == Y[i]: 
        c[i][j] = c[i - 1][j - 1] + 1
      elif c[i - 1][j] >= c[i][j - 1]:
        c[i][j] = c[i - 1][j]
      else:
        c[i][j] = c[i][j - 1]
  print c[X][Y]


q = input()


for i in range(q):
  LCS()

Submission status: Runtime Error

Solution code:

def LCS():
  x = raw_input()
  y = raw_input()
  X = len(x)
  Y = len(y)
  
  for i in range(X):
    c[i][0] = 0
  for j in range(Y):
    c[0][j] = 0
???x = ' ' + x
  y = ' ' + y

  for i in range(1,X+1):
    for j in range(1,Y+1):
      if X[i] == Y[i]: 
        c[i][j] = c[i-1][j-1] + 1

      elif c[i-1][j] >= c[i][j-1]:
        c[i][j] = c[i-1][j]
      else:
        c[i][j] = c[i][j-1]
  print c[X][Y]

q = input()


for i in range(q):
  LCS()

Submission status: Runtime Error

Solution code:
def LCS():
  x = raw_input()
  y = raw_input()
  X = len(x)
  Y = len(y)
  
  for i in range(X):
    c[i][0] = 0
  for j in range(Y):
    c[0][j] = 0
???x = ' ' + x
  y = ' ' + y

  for i in range(1,X+1):
    for j in range(1,Y+1):
      if X[i] == Y[i]:
        c[i][j] = c[i-1][j-1] + 1

      elif c[i-1][j] >= c[i][j-1]:
        c[i][j] = c[i-1][j]

      else:
        c[i][j] = c[i][j-1]
q = input()
for i in range(q):
  LCS()

Submission status: Runtime Error

Solution code:

def LCS():
  x = ' ' + raw_input()
  y = ' ' + raw_input()
  X = len(x)
  Y = len(y)
  
  for i in range(X):
    c[i][0] = 0
  for j in range(Y):
    c[0][j] = 0


  for i in range(X):
    for j in range(Y):
      if X[i] == Y[i]: 
        c[i][j] = c[i - 1][j - 1] + 1
      elif c[i - 1][j] >= c[i][j - 1]:
        c[i][j] = c[i - 1][j]
      else:
        c[i][j] = c[i][j - 1]
  print c[X][Y]


q = input()


for i in range(q):
  LCS()

Submission status: Runtime Error

Solution code:
\def LCS():
  x = raw_input()
  y = raw_input()
  X = len(x)
  Y = len(y)
  for i in range(X):
    c[i][0] = 0
  for j in range(Y):
    c[0][j] = 0
 
  for i in range(X):
    for j in range(Y):
      if X[i] == Y[i]: 
        c[i][j] = c[i - 1][j - 1] + 1
 
      else:
        c[i][j] = max(c[i - 1][j], c[i][j - 1])
         
 
  print max(c)
 
q = input()
 
for i in xrange(q):
  LCS

Submission status: Runtime Error

Solution code:
def LCS():
  x = ' ' + raw_input()
  y = ' ' + raw_input()
  X = len(x)
  Y = len(y)
  maxl = 0
  for i in range(1,X+1):
    c[i][0] = 0
  for j in range(1,Y+1):
    c[0][j] = 0
 
  for i in range(1,X+1):
    for j in range(1,Y+1):
      if X[i] == Y[i]: 
        c[i][j] = c[i - 1][j - 1] + 1
 
      else:
        c[i][j] = max(c[i - 1][j], c[i][j - 1])

    maxl = (c[i][j], maxl)     
 return maxl
 
q = input()
 
for i in xrange(q):
  print LCS

Submission status: Runtime Error

Solution code:
def LCS():
    X = raw_input()
    Y = raw_input()
 
    a, b = len(X), 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]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1] < x1[j]:
                x1[j+1] = x1[j]
    return c1[-1]
 
n = input()
for i in range(n):
    print LCS()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
 solve():
    seq1 = raw_input()
    seq2 = raw_input()
 
    x, y = len(seq1), len(seq2)
    a1 = [0 for i in range(y+1)]
    for i in range(x):
        e1 = seq1[i]
        a2 = a1+[]
        for j in range(y):
            if e1 == seq2[j]:
                a1[j+1] = a2[j] + 1
            elif a1[j+1] < a1[j]:
                a1[j+1] = a1[j]
    return a1[-1]
 
n = input()
for i2 in range(n):
    print solve()

Submission status: Runtime Error

Solution code:
def solve():
    seq1 = raw_input()
    seq2 = raw_input()
 
    x, y = len(seq1), len(seq2)
    a1 = [0 for i in range(y+1)]
    for i in range(x):
        e1 = seq1[i]
        a2 = a1+[]
        for j in range(y):
            if e1 == seq2[j]:
                a1[j+1] = a2[j] + 1
            elif a1[j+1] < a1[j]:
                a1[j+1] = a1[j]
    return a1[-1]
 
n = imput()
for i2 in range(n):
    print solve()

Submission status: Runtime Error

Solution code:
def common():
????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 x[i] == y[j]:
?????????????? k1[j+1] = k2[j] + 1
      elif k1[j+1] < k1[j]:
????????????????k1[j+1] = k1[j]
  
  return k1[-1]

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

Submission status: Runtime Error

Solution code:
def common():
????X = raw_input()
  Y = raw_input()
????a = len(x)
????b = len(y)
????k1 = [0 for i in range(b+1)]
????
????for i in range(a):
????????k2 = k1 + []
????????for j in range(b):
????    if X[i] == Y[j]:
?????????????? k1[j+1] = k2[j] + 1
      elif k1[j+1] < k1[j]:
????????????????k1[j+1] = k1[j]
  
  return k1[-1]

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

Submission status: Runtime Error

Solution code:
def common():
????X = raw_input()
  Y = raw_input()
????a = len(X)
????b = len(Y)
????k1 = [0 for i in range(b+1)]
????
????for i in range(a):
????????k2 = k1 + []
????????for j in range(b):
????    if X[i] == Y[j]:
?????????????? k1[j+1] = k2[j] + 1
      elif k1[j+1] < k1[j]:
????????????????k1[j+1] = k1[j]
  
  return k1[-1]

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

Submission status: Runtime Error

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

????for i in range(a):
????????k2 = k1 + []
????????for j in range(b):
????    if X[i] == Y[j]:
?????????????? k1[j+1] = k2[j] + 1
      elif k1[j+1] < k1[j]:
????????????????k1[j+1] = k1[j]

  return k1[-1]

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

Submission status: Runtime Error

Solution code:
def common():
????X = raw_input()
  Y = raw_input()
????a = len(X)
????b = len(Y)
????k1 = [0 for t in range(b+1)]

????for i in range(a):
????????k2 = k1 + []
????????for j in range(b):
????    if X[i] == Y[j]:
?????????????? k1[j+1] = k2[j] + 1
      elif k1[j+1] < k1[j]:
????????????????k1[j+1] = k1[j]

  return k1[-1]

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

Submission status: Runtime Error

Solution code:
def common():
????X = raw_input()
  Y = raw_input()
????a = len(X)
????b = len(Y)
????k1 = [0 for c in range(b+1)]

????for i in range(a):
????????k2 = k1 + []
????????for j in range(b):
????    if X[i] == Y[j]:
?????????????? k1[j+1] = k2[j] + 1
      elif k1[j+1] < k1[j]:
????????????????k1[j+1] = k1[j]

  return k1[-1]

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

Submission status: Runtime Error

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

????for i in range(a):
????????k2 = k1 + []
????????for j in range(b):
????    if X[i] == Y[j]:
?????????????? k1[j+1] = k2[j] + 1
      elif k1[j+1] < k1[j]:
????????????????k1[j+1] = k1[j]

  return k1[-1]

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

Submission status: Runtime Error

Solution code:
def lcs(X, Y):
    #X = " " + X
    #Y = " " + Y
    #c = [[0 for j in xrange(len(Y))] for i in xrange(len(X))]
    c2 = [0???for i in xrange(len(Y))]
    #maxl = 0
     
    for i in xrange(1,len(X)):
        c1 = c2 + []
        for j in xrange(1,len(Y)):
            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 = int(raw_input())
  
for i in xrange(n):
    s1 = raw_input()
    s2 = raw_input()
    print lcs(s1, s2)

Submission status: Runtime Error

Solution code:
dp = [0] * 1000

for i in range(1000):
  dp[i] = [0] * 1000


def lcs(s, t):
  slen = len(s)
  tlen = len(t)

  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(n):
  x = raw_input()
  y = raw_input()
  print lcs(x, y)

Submission status: Runtime Error

Solution code:
dp = [0] * 1000

for i in range(1000):
  dp[i] = [0] * 1000

def lcs(s, t):
  slen = len(s)
  tlen = len(t)

  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(n):
  x = raw_input()
  y = raw_input()
  if i >= 20 and (len(y) >= 100 or len(x) >= 100):
    continue
  print lcs(x, y)

Submission status: Runtime Error

Solution code:
def num_substr(s, t):
    sl = len(s)
    tl = len(t)
    dp = {}
    for i in range(sl + 1):
        dp[i] = {0: 0}
    for j in range(st + 1):
        dp[0][j] = 0
     
    for i in range(1,sl+1):
        si_1 = s[i-1]
        dpi = dp[i]
        dpi_1 = dp[i-1]
        for j in range(1,tl+1):
            d=1 if si_1 == t[j-1] and dpi_1[j-1] == dpi[j-1] else 0
            dpi[j] = max(dpi_1[j] ,
                           dpi[j-1] +d)
    return dp[len(s)][len(t)]
 
n = int(input())
for i in range(n):
    s = input()
    t = input()
    print(num_substr(s,t))

Submission status: Runtime Error

Solution code:
def num_substr(s, t):
    sl = len(s)
    tl = len(t)
    dp = {}
    for i in range(sl + 1):
        dp[i] = {0: 0}
    for j in range(sl + 1):
        dp[0][j] = 0
     
    for i in range(1,sl+1):
        si_1 = s[i-1]
        dpi = dp[i]
        dpi_1 = dp[i-1]
        for j in range(1,tl+1):
            d=1 if si_1 == t[j-1] and dpi_1[j-1] == dpi[j-1] else 0
            dp[i][j] = max(dpi_1[j] ,
                           dpi[j-1] +d)
    return dp[len(s)][len(t)]
 
n = int(input())
for i in range(n):
    s = input()
    t = input()
    print(num_substr(s,t))

Submission status: Runtime Error

Solution code:
def lcd(x0, y0):
    lx, ly = len(x0), len(y0)
    memo = [[None] * ly for _ in range(lx)]

    def memoize(x, y):
        if x < 0 or y < 0:
            return 0
        if memo[x][y] is not None:
            return memo[x][y]
        result = memo[x][y] = main(x, y)
        return result

    def main(x, y):
        return memoize(x - 1, y - 1) + 1 if x0[x] == y0[y] else max(memoize(x - 1, y), memoize(x, y - 1))

    return main(lx - 1, ly - 1)


n = int(input())
while n:
    print(lcd(input(), input()))
    n -= 1

Submission status: Runtime Error

Solution code:
from sys import stdin
def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0]*(m + 2) for a in range(n + 2)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i-1] == y[j-1]:
                c[i][j] = (c[i - 1][j - 1]) + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
    return max(max(c))

n = int(input().rstrip())
strs = stdin.readlines()
ret = []
for i in range(n):
    # s1 = strs[i*2].rstrip()
    # s2 = strs[i*2+1].rstrip()
    ret.append(lcs(strs[i*2].rstrip(), strs[i*2+1].rstrip()))
print(*ret, sep="\n")

Submission status: Runtime Error

Solution code:
def lcs(x, y):
    lx = len(x)
    ly = len(y)
    pcsl = [[0 for j in range(ly + 1)] for i in range(lx + 1)]
    for i in range(lx):
        for j in range(ly):
            if x[i] == y[j]:
                pcsl[i][j] = pcsl[i - 1][j - 1] + 1
            else:
                pcsl[i][j] = max(pcsl[i - 1][j], pcsl[i][j - 1])
    print(pcsl[i][j])


import sys

q = sys.stdin.readline()

while True:
    ax = sys.stdin.readline()[:-1]
    ay = sys.stdin.readline()[:-1]
    lcs(ax, ay)

Submission status: Runtime Error

Solution code:
def len_LCS(X,Y):
    D = {}
    def main(X,Y):
        if len(X) == 0: return 0
        if (X,Y) in D: return D[(X,Y)]
        if len(X) == 1:
            D[(X,Y)] = 1 if X[0] in Y else 0
        elif X[0] in Y:
            if Y.index(X[0]) == len(Y)-1:
                D[(X,Y)] = max(1,main(X[1:],Y[:])) 
            else: 
                D[(X,Y)]=  max(main(X[1:],Y[Y.index(X[0])+1:]) + 1,\
                               main(X[1:],Y[:]))
        else:
             D[(X,Y)] = main(X[1:],Y[:]) 
        return D[(X,Y)]
    return main(X,Y)
        
if __name__=='__main__':
    n = int(input())
    for _ in range(n):
        X = input()
        Y = input()
        print(len_LCS(X,Y))

Submission status: Runtime Error

Solution code:
def lcs(a,b):
    dp = [[0 for i in range(len(a)+1)] for j in range(len(b)+1)]
    for i in range(1,len(a)+1):
        for j in range(1,len(b)+1):
            x = 0
            if a[i-1]==b[j-1]:
                x = 1
            dp[i][j] = max(dp[i-1][j-1]+x, dp[i][j-1], dp[i-1][j])
    return dp[len(a)][len(b)]

n = int(raw_input())
s = []
for _ in range(n):
    a = raw_input()
    b = raw_input()
    s.append((a,b))

for a,b in s:
    print lcs(a,b)

Submission status: Runtime Error

Solution code:
def lcs(X, Y):
    if not len(X) or not len(Y):
        return 0
    if X[-1] == Y[-1]:
        return 1 + lcs(X[:-1], Y[:-1])
    else:
        return max(lcs(X[:-1], Y), lcs(X, Y[:-1]))

q = int(input())
for i in range(q):
    X = input()
    Y = input()
    print(lcs(X, Y))

Submission status: Runtime Error

Solution code:
import sys
def lcs(X, Y):
    c = [0 for _ in range(len(Y) + 1)]

    for i in X:
        tmp = c[:]
        for ji, yc in enumerate(Y):
            j = ji + 1
            if i == yc:
                c[j] = tmp[j - 1] + 1
            else:
                c[j] = max(tmp[j], c[j - 1])
    return c[y - 1]

n = int(input())

for i in range(n):
    X = sys.stdin.readline()[:-1]
    Y = sys.stdin.readline()[:-1]
    print(lcs(X, Y))

Submission status: Runtime Error

Solution code:
def lcs(X,Y):
    Xlength = len(X)
    Ylength = len(Y)
    # print(X,Y)
    if Xlength == 0 or Ylength == 0:
        c[Xlength][Ylength] = 0
        return c[Xlength][Ylength]



    if X[Xlength -1] == Y[Ylength -1]:
        if c[Xlength-1][Ylength-1] is not None:
            c[Xlength][Ylength] = c[Xlength-1][Ylength-1]+1
        else:
            c[Xlength][Ylength] = lcs(X[:Xlength-1], Y[:Ylength-1])+1
    else:
        if c[Xlength-1][Ylength] is not None and c[Xlength][Ylength-1] is not None:
            c[Xlength][Ylength] = max(c[Xlength][Ylength-1],c[Xlength-1][Ylength])
        elif c[Xlength-1][Ylength] is not None:
            c[Xlength][Ylength] = max(lcs(X,Y[:Ylength-1]),c[Xlength-1][Ylength])
        elif c[Xlength][Ylength-1] is not None:
            c[Xlength][Ylength] = max(c[Xlength][Ylength-1],lcs(X[:Xlength-1],Y))
        else:
            c[Xlength][Ylength] = max(lcs(X,Y[:Ylength-1]),lcs(X[:Xlength-1],Y))

    return c[Xlength][Ylength]


n = int(input())
X = []
Y = []
c = [[None]*1001 for i in range(1001)]


for i in range(n):
    X.append(input())
    Y.append(input())

for i in range(n):
    # print(i)
    print(lcs(X[i],Y[i]))
    c = [[None]*1001 for i in range(1001)]

Submission status: Runtime Error

Solution code:
n=int(input())
al=[]
bl=[]
for i in range(n):
	al.append(list(input()))
	bl.append(list(input()))

for i in range(n):
	a=al.pop(0)
	b=bl.pop(0)
	dp=[[0 for i in range(len(b))] for j in range(len(a))]

	if a[0]==b[0]:
		dp[0][0]=1
	for i in range(1,len(a)):
		if a[i]=b[0]:
			dp[i][0]=1
		else:
			dp[i][0]=dp[i-1][0]
	for i in range(1,len(b)):
		if a[0]=b[i]:
			dp[0][i]=1
		else:
			dp[0][i]=dp[0][i-1]
	for i in range(1, len(a)):
		for j in range(1, len(b)):
			if a[i]!=b[j]:
				dp[i][j]=max(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])
			else:
				dp[i][j]=dp[i-1][j-1]+1

	print(dp[len(a)-1][len(b)-1])

Submission status: Runtime Error

Solution code:
n=int(input())

l=[]

for i in range(n):
	a=al.list(input())
	b=bl.list(input())
	dp=[[0 for i in range(len(b))] for j in range(len(a))]

	if a[0]==b[0]:
		dp[0][0]=1
	for i in range(1,len(a)):
		if a[i]==b[0]:
			dp[i][0]=1
		else:
			dp[i][0]=dp[i-1][0]
	for i in range(1,len(b)):
		if a[0]==b[i]:
			dp[0][i]=1
		else:
			dp[0][i]=dp[0][i-1]
	for i in range(1, len(a)):
		for j in range(1, len(b)):
			if a[i]==b[j]:
				dp[i][j]=dp[i-1][j-1]+1
			else:
				dp[i][j]=max(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])

	l.append(dp[len(a)-1][len(b)-1])

for i in l:
	print(l)

Submission status: Runtime Error

Solution code:
def calc_lcs(X, Y):
    m = len(X)
    n = len(Y)
    c = [[0 for _ in range(n)] for i in range(m)]
    for i in range(m):
        for j in range(n):
            if X[i] == Y[j]:
                c[i][j] = c[i-1][j-1] + 1
            elif c[i-j][j] >= c[j][j-1]:
                c[i][j] = c[i - 1][j]
            else:
                c[i][j] = c[i][j -1]
    max_lcs = 0
    for row in c:
        temp = max(row)
        if temp > max_lcs:
            max_lcs = temp
    return max_lcs


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    # X = 'abcbdab'
    # Y = 'bdcaba'

    for _ in range(num):
        X = input()
        Y = input()

        # ???????????????
        result = calc_lcs(X, Y)

        # ???????????¨???
        print(result)