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:
def lcs(x,y):
    x = " " + x
    y = " " + y    
    c = [[0]*(1001)]*(1001)
#    for i in xrange (len(x)-1):
#        c[i][0] = 0
#    for j in xrange (len(y)-1):
#        c[0][j] = 0
    for i in xrange (len(x)):
        for j in xrange (len(y)):
            if i >= 1 and j >= 1 and x[i] == y[j]:
                c[i][j] = c[i-1][j-1] + 1
            elif i >= 1 and j >= 1 and x[i] != y[j]:
                c[i][j] = max(c[i][j-1],c[i-1][j])
    return max(max(c))

n = input()

for i in xrange (n):

    x = raw_input()
    y = raw_input()

    print lcs(x,y)

Submission status: Wrong Answer

Solution code:
def lcs(x,y):
    x = " " + x
    y = " " + y    
    c = [[0]*(1001)]*(1001)
    for i in xrange (len(x)):
        for j in xrange (len(y)):
            if i >= 1 and j >= 1 and x[i] == y[j]:
                c[i][j] = c[i-1][j-1] + 1
            elif i >= 1 and j >= 1 and x[i] != y[j]:
                c[i][j] = max(c[i][j-1],c[i-1][j])
    return max(max(c))

n = input()

for i in xrange (n):

    x = raw_input()
    y = raw_input()

    print lcs(x,y)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Here your code !

def lcs(x,y):
    xs = len(x)
    ys = len(y)
    x = " " + x
    y = " " + y
    c = [[0]*(1001)]*(1001)
    m = 0
#    for i in xrange (xs+1):
#        c[i][0] = 0
#    for j in xrange (ys+1):
#        c[0][j] = 0


    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)),m

n = input()

for i in xrange (n):

    x = raw_input()
    y = raw_input()

    print lcs(x,y)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys

def lcs():
    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] + i
            if x1[j+1] < x1[j] :
                x1[j+1] = x1[j]
    return x1[-1]

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

Submission status: Wrong Answer

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

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

Solution code:
ans = {}

roop = input('n : ')
for k in range(roop):
    str1 = raw_input('str1 : ')
    str2 = raw_input('str2 : ')
    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(ans[i - 1, j] == ans[i, j - 1]):
                if(str1[i] == str2[j]):
                    ans[i, j] = ans[i - 1, j] + 1
                else:
                    ans[i, j] = ans[i - 1, j]
            else:
                ans[i, j] = max(ans[i - 1, j], ans[i, j - 1])
    print ans[len(str1) - 1, len(str2) - 1]

Submission status: Wrong Answer

Solution code:
ans = {}

roop = input('n : ')
for k in range(roop):
    str1 = raw_input('str1 : ')
    str2 = raw_input('str2 : ')
    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(ans[i - 1, j] == ans[i, j - 1]):
                if(str1[i] == str2[j]):
                    ans[i, j] = ans[i - 1, j] + 1
                else:
                    ans[i, j] = ans[i - 1, j]
            else:
                ans[i, j] = max(ans[i - 1, j], ans[i, j - 1])
    print str(ans[len(str1) - 1, len(str2) - 1])

Submission status: Wrong Answer

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(ans[i - 1, j] == ans[i, j - 1]):
                if(str1[i] == str2[j]):
                    ans[i, j] = ans[i - 1, j] + 1
                else:
                    ans[i, j] = ans[i - 1, j]
            else:
                ans[i, j] = max(ans[i - 1, j], ans[i, j - 1])
    print ans[len(str1) - 1, len(str2) - 1]

Submission status: Wrong Answer

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(ans[i - 1, j] == ans[i, j - 1]):
                if(str1[i] == str2[j]):
                    ans[i, j] = ans[i - 1, j] + 1
                else:
                    ans[i, j] = ans[i - 1, j]
            else:
                ans[i, j] = max(ans[i - 1, j], ans[i, j - 1])
    print str(ans[len(str1) - 1, len(str2) - 1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
roop = input('n : ')
for k in range(roop):
    str1 = raw_input('str1 : ')
    str2 = raw_input('str2 : ')
    len1 = len(str1) + 1
    len2 = len(str2) + 1
    ans = [None] * (len1)
    for i in xrange(len1):
        ans[i] = [None] * (len2)
    for i in range(len1):
        ans[i][0] = 0
    for j in range(len2):
        ans[0][j] = 0
    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: Wrong Answer

Solution code:
def LCS():
   x = raw_input()
   y = raw_input()

   a, b = len(x), len(y)
 
   c1 = [0 for i in xrange(b+1)]
   for i in xrange(a):
      c2  = c1+[]
      for j in xrange(b):
        if x[i] == y[j]:
           c1[j+1] = c2[j] + 1
        elif c1[j+1] < c1[j]:
           c1[j+1] = c1[j]
   print max(c1)
   
   n = input()
   for a in xrange(n):
      LCS()

Submission status: Wrong Answer

Solution code:
n = input()
for k in xrange(n):
    str1 = raw_input()
    str2 = raw_input()
    
    after = [0] * (len(str2) + 1)
    
    for i in xrange(1, len(str1) + 1):
        before = after + []
        for j in xrange(1, len(str2) + 1):
            if str1[i - 1] == str2[j - 1]:
                after[j] = before[j - 1] + 1
            else:
                after[j] = max(before[j], after[j - 1])
print after[j]

Submission status: Wrong Answer

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

def LCS(X, Y):
    c = [[0 for i in range(0, 1001)] for j in range(0, 1001)]
    m = len(X)
    n = len(Y)
    maxl = 0
    frag = 1
    X = ' ' + X
    Y = ' ' + Y
    
    for i in range(1, m+1):
        for j in range(frag, n+1):
            if X[i] == Y[j]:
                frag = i
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i-1][j], c[i][j-1])
            maxl = max(maxl, c[i][j])
    return maxl

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

Submission status: Wrong Answer

Solution code:
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()
  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]
  print maxl

Submission status: Wrong Answer

Solution code:
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 k in range(q):
  x = ' ' + raw_input()
  y = ' ' + raw_input()
  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]
  print maxl

Submission status: Wrong Answer

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

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 c[X][Y]

q = input()

for i in range(q):
  LCS

Submission status: Wrong Answer

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

  return count



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

Submission status: Wrong Answer

Solution code:
def LCS():
  x = raw_input()
  y = raw_input()
  X = len(x)
  Y = len(y)
  x = " " + x
  y = " " + 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 c[X][Y]

q = input()

for i in range(q):
  LCS

Submission status: Wrong Answer

Solution code:
def LCS():
  x = raw_input()
  y = raw_input()
  X = len(x)
  Y = len(y)
  x = " " + x
  y = " " + 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 c[X + 1][Y + 1]

q = input()

for i in range(q):
  LCS

Submission status: Wrong Answer

Solution code:
def LCS():
  x = raw_input()
  y = raw_input()
  X = len(x)
  Y = len(y)
  x = " " + x
  y = " " + 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 range(q):
  LCS

Submission status: Wrong Answer

Solution code:
def LCS():
  x = raw_input()
  y = raw_input()
  X = len(x)
  Y = len(y)
  x = " " + x
  y = " " + 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: Wrong Answer

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

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 + 1] == Y[i + 1]: 
        c[i + 1][j + 1] = c[i][j] + 1

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

  print max(c)

q = input()

for i in xrange(q):
  LCS

Submission status: Wrong Answer

Solution code:
def LCS():
  x = raw_input()
  y = raw_input()
  X = len(x)
  Y = len(y)
  x = " " + x
  y = " " + 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 + 1] == Y[i + 1]: 
        c[i + 1][j + 1] = c[i][j] + 1

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

  print max(c)

q = input()

for i in range(q):
  LCS

Submission status: Wrong Answer

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

  lsc = 0
  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 + 1] == Y[i + 1]: 
        c[i + 1][j + 1] = c[i][j] + 1

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

  print lcs

q = input()

for i in range(q):
  LCS

Submission status: Wrong Answer

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

  lsc = 0
  for i in range(X):
    c[i][0] = 0
  for j in range(Y):
    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])
  lcs = max(c)

  print lcs

q = input()

for i in range(q):
  LCS

Submission status: Wrong Answer

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

  lcs = 0
  for i in range(X):
    c[i][0] = 0
  for j in range(Y):
    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])
  lcs = max(c[i][j], lcs)

  print lcs

q = input()

for i in range(q):
  LCS

Submission status: Wrong Answer

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

  lcs = 0
  for i in range(X):
    c[i][0] = 0
  for j in range(Y):
    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: Wrong Answer

Solution code:
def LCS():
  x = raw_input()
  y = raw_input()
  X = len(x)
  Y = len(y)
  x = " " + x
  y = " " + 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: Wrong Answer

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

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

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

Solution code:
def LCS():
  x = ' ' + raw_input()
  y = ' ' + raw_input()
  X = len(x)
  Y = len(y)
  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[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: Wrong Answer

Solution code:
def LCS():
  x = ' ' + raw_input()
  y = ' ' + raw_input()
  X = len(x)
  Y = len(y)
  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[i]: 
        c[i][j] = c[i - 1][j - 1] + 1
 
      else:
        c[i][j] = max(c[i - 1][j], c[i][j - 1])
         
 
  return max(c)
 
q = input()
 
for i in xrange(q):
  print LCS

Submission status: Wrong Answer

Solution code:
def LCS():
  x = ' ' + raw_input()
  y = ' ' + raw_input()
  X = len(x)
  Y = len(y)
  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])
         
 
  return max(c)
 
q = input()
 
for i in xrange(q):
  print LCS

Submission status: Wrong Answer

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)     
 
 
q = input()
 
for i in xrange(q):
  print LCS

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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 (y >= 100 or x >= 100):
    continue
  print lcs(x, y)

Submission status: Wrong Answer

Solution code:
def lcs(X, Y):
    m, n = len(X), len(Y)
    cost = [[1] * (n) for _ in range(m)]
    for i in range(0, m):
        if i == 0:
            continue
        for j in range(0, n):
            if j == 0:
                continue
            if X[i - 1] == Y[j - 1]:
                cost[i][j] = cost[i - 1][j - 1] + 1
            else:
                cost[i][j] = max(cost[i][j - 1], cost[i - 1][j])
    return cost[-1][-1]

n = int(input())
for _ in range(n):
    X, Y = input(), input()
    print(lcs(X, Y))

Submission status: Wrong Answer

Solution code:
pcsl = [[0] * 1001] * 1001

def lcs(x, y):
    m = len(x)
    n = len(y)
    for i in range(m):
        for j in range(n):
            if x[i] == y[j]:
                pcsl[i][j] = pcsl[i - 1][j - 1] + 1
            elif pcsl[i - 1][j] > pcsl[i][j - 1]:
                pcsl[i][j] = pcsl[i - 1][j]
            else:
                pcsl[i][j] = pcsl[i][j - 1]
    print(pcsl[i][j])


q = int(input())

for i in range(q):
    ax = input()
    ay = input()
    lcs(ax, ay)

Submission status: Wrong Answer

Solution code:
def longest_common_seq(x, y):
    m, n = len(x), len(y)
    
    dp = []
    for _ in range(m+1):
        dp.append([0]*(n+1))

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

    return dp[m-1][n-1]



if __name__ == '__main__':
    q = int(input())  # 1 .. 150
    for _ in range(q):
        x = input()
        y = input()
        print(x, y)
        l = longest_common_seq(x,y)
        print(l)

Submission status: Wrong Answer

Solution code:
def findlcs(x, y):
    dp = [0]*(len(y)+1)

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

    return dp[len(y)]


q = int(input())
for k in range(q):
    X = input()
    Y = input()
    print(findlcs(X, Y))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys


def lcs(A, B):
    m, n = len(A), len(B)
    count_list = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                count_list[i][j] = count_list[i - 1][j - 1] + 1
            elif count_list[i - 1][j] >= count_list[i][j - 1]:
                count_list[i][j] = count_list[i - 1][j]
            else:
                count_list[i][j] = count_list[i][j - 1]

    return count_list[m][n]


def lcs_better(A, B):
    costs = [0]
    for c in B:
        for index in range(len(costs) - 1, -1, -1):
            print(costs, index + 1)
            x_findex_index = A.find(c, costs[index])
            if x_findex_index != -1:
                if index + 1 < len(costs):
                    costs[index + 1] = min(costs[index + 1], x_findex_index + 1)
                else:
                    costs.append(x_findex_index + 1)
    return len(costs) - 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num
    for k in range(0, len(word_list), 2):
        print(lcs_better(word_list[k].strip(), word_list[k + 1].strip()))

Submission status: Wrong Answer

Solution code:
#coding:UTF-8
def LCS(X,Y):
    count=0
    xlist=list(X)
    ylist=list(Y)
    anslist=[]
    ynum=0
    xnum=0
    yflag=False
    for i in range(len(ylist)):
        for j in range(i,len(xlist)):
            anslist.append([j,i])
    for i in range(len(anslist)):
        if xlist[anslist[i][0]]==ylist[anslist[i][1]] and ynum==anslist[i][1] and anslist[i][0]>xnum:
            count+=1
            yflag=True
            ynum+=1
            xnum=anslist[i][0]
        if anslist[i][0]==len(xlist)-1:
            if yflag==True:
                yflag=False
            else:
                ynum+=1
    print(count)
if __name__=="__main__": 
    n=int(input())
    for i in range(n):
        X=input()
        Y=input()
        LCS(X,Y)

Submission status: Wrong Answer

Solution code:
#coding:UTF-8
def LCS(X,Y):
    count=0
    xlist=list(X)
    ylist=list(Y)
    anslist=[]
    ynum=0
    xnum=0
    yflag=False
    for i in range(len(ylist)):
        for j in range(i,len(xlist)):
            anslist.append([j,i])
    for i in range(len(anslist)):
        if xlist[anslist[i][0]]==ylist[anslist[i][1]] and ynum==anslist[i][1] and anslist[i][0]>=xnum:
            count+=1
            yflag=True
            ynum+=1
            xnum=anslist[i][0]
        if anslist[i][0]==len(xlist)-1:
            if yflag==True:
                yflag=False
            else:
                ynum+=1
    print(count)
if __name__=="__main__": 
    n=int(input())
    for i in range(n):
        X=input()
        Y=input()
        LCS(X,Y)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys


def lcs(A, B):
    m, n = len(A), len(B)
    count_list = tuple([[0] * (n + 1) for _ in range(m + 1)])

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

    return count_list[m][n]


def lcs_recursive(A, B, m, n):
    if m == 0 or n == 0:
        return 0
    elif A[m - 1] == B[n - 1]:
        return 1 + lcs_recursive(A, B, m - 1, n - 1)
    else:
        return max(lcs_recursive(A, B, m, n - 1), lcs_recursive(A, B, m - 1, n))


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num
    # for k in range(0, len(word_list), 2):
    #     print(lcs(word_list[k].strip(), word_list[k + 1].strip()))

    for pair in zip(word_list[::2], word_list[1::2]):
        w1, w2 = map(lambda x: x.strip(), pair)
        l1, l2 = len(w1), len(w2)
        print(w1, w2, l1, l2)
        print(lcs_recursive(w1, w2, l1, l2))

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(3 * 1000)

@lru_cache(maxsize=None)
def lcs_rec(i, j):
    if i == 0 or j == 0:
        return 0

    if X[i - 1] == Y[j - 1]:
        return lcs_rec(i - 1, j - 1) + 1
    else:
        return max(lcs_rec(i - 1, j), lcs_rec(i, j - 1))

q = int(input())

for i in range(q):
    X = input()
    Y = input()

    ans = lcs_rec(len(X), len(Y))

    print(ans)

Submission status: Wrong Answer

Solution code:
q = int(input())

for i in range(q):
    x = list(input())
    y = list(input())
    max_count = 0
    for j in range(len(x)):
        for k in range(len(y)):
            count = 0
            if x[j] == y[k]:
                count += 1 
                ret = j
                ret_2 = k
                while j < len(x) -1 and k < len(y) -1:
                    j += 1
                    k += 1
                    if x[j] == y[k]:
                        count += 1
                    else:
                        break
                j = ret
                k = ret_2
                max_count = max(count,max_count)
    print(max_count)

Submission status: Wrong Answer

Solution code:
q = int(input())

for k in range(q):
    x = input()
    y = input()
    lcs = [0 for i in range(len(x)+1)] 
    for i in range(1,len(y) + 1):
        lcs_2 = [i for i in lcs]
        for j in range(1,len(x) + 1):
            if x[j-1] == y[i-1]:
                lcs[j] = lcs_2[j-1] + 1  
    print(lcs[len(x)])