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:
import sys

LEN_MAX = 1000
sys.setrecursionlimit(LEN_MAX + 3)

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

def solve(str_a, str_b):
    dp = dp_init(len(str_a)+1, len(str_b)+1)
    #print(dp)
    return rec(len(str_a), len(str_b), str_a, str_b, dp, 0)

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

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

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

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

Submission status: Runtime Error

Solution code:
import std.array, std.stdio, std.conv, std.string, std.math, std.random, std.range,std.functional, std.typecons;
import std.algorithm.searching, std.algorithm.sorting, std.algorithm.iteration, std.algorithm.comparison;

 
int[][char] memo;
int[][] memo2;
 
void main()
{
    int Q = readln().strip.to!int;
    foreach(i;0..Q)
    {
        int[][char] m;
        memo = m;
        memo2 = [];
        auto aList = readln().strip;
        auto bList = readln().strip;
        memoWrite(aList, bList);
        writeln(func(aList, bList, 0));
    }
}

int func(string aList, string bList, int lastIndex)
{
    if(aList.length == 0 || bList.length <= lastIndex)
    {
        return 0;
    }
    if(memo2[aList.length-1][lastIndex] != 0)
    {
        return memo2[aList.length-1][lastIndex];
    }
    int maxLen;
    foreach(i, a; enumerate(aList))
    {
        int li = memo[cast(char)a][lastIndex];
        if(li == -1)
            continue;
        maxLen = max(maxLen, func(aList[i+1..$], bList, li+1)+1);
    }
    memo2[aList.length-1][lastIndex] = maxLen;
    return maxLen;
}

void memoWrite(string aList, string bList)
{
    memo2.length = aList.length;
    memo2.each!((ref a)=>a.length = bList.length);
    foreach(a; aList)
    {
        if(a in memo)
        {
            continue;
        }

        int[] m;
        m.length = bList.length;

        int index = -1;
        for(long i = bList.length-1;i >= 0;i--)
        {
            char b = bList[i];
            if(a==b)
            {
                index = cast(int)i;
            }
            m[i] = index;
        }
        memo[a] = m;
    }
}

Submission status: Runtime Error

Solution code:
import numpy as np
q = int(input())

for _ in range(q):
    X = np.array([ord(i) for i in input()])
    Y = np.array([ord(i) for i in input()])
    NX = len(X)
    NY = len(Y)
    dp = np.zeros((NX+1,NY+1), dtype=np.int64)
    for x in range(NX):
        yes = Y == X[x]
        no = Y != X[x]
        dp[x+1][1:][yes] = dp[x][:-1][yes] + 1
        dp[x+1][1:][no] = np.maximum(dp[x][1:][no], dp[x][:-1][no])
    print(dp[NX][NY])

Submission status: Runtime Error

Solution code:
from sys import stdin

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


def getLCS() :
	xlen = len(X[l])
	ylen = len(Y[l])
	Z = [[0 for i in range(xlen+2)]for i in range(ylen+2)]

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

	return Z[xlen][ylen]

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

Submission status: Runtime Error

Solution code:
from sys import stdin

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


def getLCS() :
	xlen = len(X[l])
	ylen = len(Y[l])
	Z = [[0 for i in range(xlen+2)]for i in range(ylen+2)]


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

	return Z[xlen][ylen]

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

Submission status: Runtime Error

Solution code:
from sys import stdin

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

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

	for i in range(1,xlen+1) :
		for j in range(1,ylen+1) :
			a = 1 if X[l][i-1] == Y[l][j-1] else 0
			Z[i][j] = max(Z[i-1][j-1] + a, Z[i-1][j], Z[i][j-1])

	return Z[xlen][ylen]

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

Submission status: Runtime Error

Solution code:
from sys import stdin

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

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

	for i in range(1,xlen+1) :
		for j in range(1,ylen+1) :
			a = 1 if X[l][i-1] == Y[l][j-1] else 0
			Z[i][j] = max(Z[i-1][j-1] + a, Z[i-1][j], Z[i][j-1])

	return Z[xlen][ylen]

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

Submission status: Runtime Error

Solution code:
q = int(raw_input())

lcs = {}
for i in range(1000):
    lcs[i] = {}
    for j in range(1000):
        lcs[i][j] = 0

for i in range(q):
    X = raw_input()
    Y = raw_input()
    for i in range(len(X)):
        for j in range(len(Y)):
            if X[i] == Y[j]:
                lcs[i+1][j+1] = lcs[i][j] + 1
            else:
                lcs[i+1][j+1] = max(lcs[i][j+1],lcs[i+1][j])
    print lcs[len(X)][len(Y)]

Submission status: Runtime Error

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

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

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

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

    return dp[m][n]

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

Submission status: Runtime Error

Solution code:
def lcs_size():
  X = input()
  Y = input()
  
  a = len(X)
  b = len(Y)
  
  for i in range(a):
    for j in range(b):
      c[i][j] = 0
      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])
      maxl = max(maxl, c[i][j])
  
  return maxl

q = input()

for i in range(q):
  print lcs_siz()

Submission status: Runtime Error

Solution code:
def lcs_size():
  X = input()
  Y = input()
  
  a = len(X)
  b = len(Y)
  
  c[1][1] = 0
  for i in range(a):
    for j in range(b):
      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])
      maxl = max(maxl, c[i][j])
  
  return maxl

q = input()

for i in range(q):
  print lcs_siz()

Submission status: Runtime Error

Solution code:
def lcs_size():
  X = input()
  Y = input()
  
  a = len(X)
  b = len(Y)
  
  c[0][0] = 0
  for i in range(a):
    for j in range(b):
      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])
      maxl = max(maxl, c[i][j])
  
  return maxl

q = input()

for i in range(q):
  print lcs_siz()

Submission status: Runtime Error

Solution code:
def lcs_size():
  X = input()
  Y = input()
  
  a = len(X)
  b = len(Y)
  
  c[0][0] = 0
  for i in range(a):
    for j in range(b):
      if X[i] == Y[j]:
        c[i+1][j+1] = c[i][j] + 1
      else:
        c[i+1][j+1] = max(c[i][j+1], c[i+1][j])
      maxl = max(maxl, c[i+1][j+1])
  
  return maxl

q = input()

for i in range(q):
  print lcs_siz()

Submission status: Runtime Error

Solution code:
def lcs_size():
  X = input()
  Y = input()
  
  a = len(X)
  b = len(Y)
  
  c = [[0 for i in range(a)] for j in range(b)]
  for i in range(a):
    for j in range(b):
      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])
      maxl = max(maxl, c[i][j])
  
  return maxl

q = input()

for i in range(q):
  print lcs_siz()

Submission status: Runtime Error

Solution code:
def lcs_size():
  X = input()
  Y = input()
  
  a = len(X)
  b = len(Y)
  
  c = [[0 for i in range(a+1)] for j in range(b+1)]
  for i in range(a):
    for j in range(b):
      if X[i] == Y[j]:
        c[i+1][j+1] = c[i][j] + 1
      else:
        c[i+1][j+1] = max(c[i][j+1], c[i+1][j])
      maxl = max(maxl, c[i+1][j+1])
  
  return maxl

q = input()

for i in range(q):
  print lcs_siz()

Submission status: Runtime Error

Solution code:
def lcs_size():
  X = input()
  Y = input()
  
  a = len(X)
  b = len(Y)
  
  c = [[0 for i in range(a+1)] for j in range(b+1)]
  maxl = 0
  for i in range(a):
    for j in range(b):
      if X[i] == Y[j]:
        c[i+1][j+1] = c[i][j] + 1
      else:
        c[i+1][j+1] = max(c[i][j+1], c[i+1][j])
      maxl = max(maxl, c[i+1][j+1])
  
  return maxl

q = input()

for i in range(q):
  print lcs_siz()

Submission status: Runtime Error

Solution code:
def lcs_size():
  X = input()
  Y = input()
  
  a = len(X)
  b = len(Y)
  
  c = [[0 for i in range(a+1)] for j in range(b+1)]
  maxl = 0
  for i in range(a):
    for j in range(b):
      if X[i] == Y[j]:
        c[i+1][j+1] = c[i][j] + 1
      elif c[i+1][j+1] < c[i][j+1]:
        c[i+1][j+1] = c[i][j+1]
      maxl = max(maxl, c[i+1][j+1])
  
  return maxl

q = input()

for i in range(q):
  print lcs_siz()

Submission status: Runtime Error

Solution code:
def lcs_size():
  X = input()
  Y = input()
  
  a = len(X)
  b = len(Y)
  
  c = [[0 for i in range(a+1)] for j in range(b+1)]
  maxl = 0
  for i in range(a):
    for j in range(b):
      if X[i] == Y[j]:
        c[i][j+1] = c[i][j] + 1
      elif c[i+1][j+1] < c[i][j+1]:
        c[i][j+1] = c[i][j+1]
      maxl = max(maxl, c[i][j+1])
  
  return maxl

q = input()

for i in range(q):
  print lcs_siz()

Submission status: Runtime Error

Solution code:
def lcs_size():
  X = input()
  Y = input()
  
  a = len(X)
  b = len(Y)
  
  c = [[0 for i in range(a+1)] for j in range(b+1)]
  maxl = 0
  for i in range(a):
    for j in range(b):
      if X[i] == Y[j]:
        c[i][j+1] = c[i][j] + 1
      elif c[i][j+1] < c[i][j+1]:
        c[i][j+1] = c[i][j+1]
      maxl = max(maxl, c[i][j+1])
  
  return maxl

q = input()

for i in range(q):
  print lcs_siz()

Submission status: Runtime Error

Solution code:
def lcs_size():
  X = input()
  Y = input()
  
  a = len(X)
  b = len(Y)
  
  z2 = [0 for in range(b+1)]
  maxl = 0
  for i in range(a):
    z1 = z2 + []
    for j in range(b):
      if X[i] == Y[j]:
        z2[j+1] = z1[j] + 1
      else:
        z2[j+1] = z1[j]
      maxl = max(maxl, z2[j+1])
  
  return maxl

q = input()

for i in range(q):
  print lcs_siz()

Submission status: Runtime Error

Solution code:
def lcs_size():
  X = input()
  Y = input()
  
  a = len(X)
  b = len(Y)
  
  z2 = [0 for in range(b+1)]
  maxl = 0
  for i in range(a):
    z1 = z2 + []
    for j in range(b):
      if X[i] == Y[j]:
        z2[j+1] = z1[j] + 1
      else:
        z2[j+1] = z2[j]
      maxl = max(maxl, z2[j+1])
  
  return maxl

q = input()

for i in range(q):
  print lcs_siz()

Submission status: Runtime Error

Solution code:
def LCS(Xs, Ys):
  Xs = raw_input()
  Ys = raw_input()
  dp = {}
  count = 0
  a = 1

  for i in range(len(Ys) + 1):
    dp[0][i + 1] = Ys[i] 
  for j in range(len(Xs) + 1):
    dp[j + 1][0] = Xs[j]

  for i in range(a, len(Ys) + 1):
    for j in range(a, len(Xs) + 1):
      if dp[j][0] == dp[i][1]:
         count = count + 1
         a = j
         break
    if dp[j][0] == dp[i][1]:
      break

   print count

Submission status: Runtime Error

Solution code:
def lcs_size():
  X = input()
  Y = input()
  
  a = len(X)
  b = len(Y)
  
  z2 = [0 for in range(b+1)]
  for i in range(a):
    z1 = z2 + []
    for j in range(b):
      if X[i] == Y[j]:
        z2[j+1] = z1[j] + 1
      else:
        z2[j+1] = z2[j]
  
  return z2[-1]

q = input()

for i in range(q):
  print lcs_siz()

Submission status: Runtime Error

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

q = input()

for i in range(q):
  print lcs_siz()

Submission status: Runtime Error

Solution code:
  Xs = raw_input()
  Ys = raw_input()
  dp = {}
  count = 0
  a = 1

  for i in range(len(Ys) + 1):
    dp[0][i + 1] = Ys[i] 
  for j in range(len(Xs) + 1):
    dp[j + 1][0] = Xs[j]

  for i in range(1, len(Ys) + 1):
    for j in range(a + 1, len(Xs) + 1):
      if dp[j][0] == dp[i][1]:
         count = count + 1
         a = j
         break
    if dp[j][0] == dp[i][1]:
      break

   print count

Submission status: Runtime Error

Solution code:
  Xs = raw_input()
  Ys = raw_input()
  count = 0
  a = 1

  for i in range(len(Ys) + 1):
    dp[0][i + 1] = Ys[i] 
  for j in range(len(Xs) + 1):
    dp[j + 1][0] = Xs[j]

  for i in range(1, len(Ys) + 1):
    for j in range(a + 1, len(Xs) + 1):
      if dp[j][0] == dp[i][1]:
         count = count + 1
         a = j
         break
    if dp[j][0] == dp[i][1]:
      break

   print count

Submission status: Runtime Error

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

q = input()

for i in range(q):
  print lcs_siz()

Submission status: Runtime Error

Solution code:
  Xs = raw_input()
  Ys = raw_input()
  count = 0
  a = 0

  for j in range(len(Ys) + 1):
    dp[0][j + 1] = Ys[i] 
  for i in range(len(Xs) + 1):
    dp[i + 1][0] = Xs[j]

  for j in range(1, len(Ys) + 1):
    for i in range(a + 1, len(Xs) + 1):
      if dp[i][0] == dp[j][1]:
         count = count + 1
         a = j
         break
    if dp[j][0] == dp[i][1]:
      break

   print count

Submission status: Runtime Error

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

q = input()

for i in range(q):
  print lcs_siz()

Submission status: Runtime Error

Solution code:
  Xs = raw_input()
  Ys = raw_input()
  count = 0
  a = 0

  for j in range(len(Ys) + 1):
    dp[1][j] = Ys[j] 
  for i in range(len(Xs) + 1):
    dp[i][1] = Xs[i]

  for j in range(1, len(Ys) + 1):
    for i in range(a + 1, len(Xs) + 1):
      if dp[i][0] == dp[j][1]:
         count = count + 1
         a = j
         break
    if dp[j][0] == dp[i][1]:
      break

   print count

Submission status: Runtime Error

Solution code:
def solve():
 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 i2 in range(n):
 print solve()

Submission status: Runtime Error

Solution code:
  Xs = raw_input()
  Ys = raw_input()
  count = 0
  a = 0

  for j in range(len(Ys) + 1):
    dp[0][j + 1] = Ys[j] 
  for i in range(len(Xs) + 1):
    dp[i + 1][0] = Xs[i]

  for j in range(1, len(Ys) + 1):
    for i in range(a + 1, len(Xs) + 1):
      if dp[i][0] == dp[0][j]:
         count = count + 1
         a = i 
         break
   
  print count

Submission status: Runtime Error

Solution code:
n = input()
for i in range(n)
  Xs = raw_input()
  Ys = raw_input()
  count = 0
  a = 0

  for j in range(len(Ys) + 1):
    dp[0][j + 1] = Ys[j] 
  for i in range(len(Xs) + 1):
    dp[i + 1][0] = Xs[i]

  for j in range(1, len(Ys) + 1):
    for i in range(a + 1, len(Xs) + 1):
      if dp[i][0] == dp[0][j]:
         count = count + 1
         a = i 
         break
   
  print count

Submission status: Runtime Error

Solution code:
n = input()
for i in range(n)
  Xs = raw_input()
  Ys = raw_input()
  count = 0
  a = 0
  dp = {}

  for j in range(len(Ys) + 1):
    dp[0][j + 1] = Ys[j] 
  for i in range(len(Xs) + 1):
    dp[i + 1][0] = Xs[i]

  for j in range(1, len(Ys) + 1):
    for i in range(a + 1, len(Xs) + 1):
      if dp[i][0] == dp[0][j]:
         count = count + 1
         a = i 
         break
   
  print count

Submission status: Runtime Error

Solution code:
def lcs(X, Y):
    X = " " + X
    Y = " " + Y
    c = []
    for i in X:
        for j in Y:
            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])
            maxl = max(maxl, c[i][j])
n = int(raw_input())

for i in range(n):
    s1 = raw_input()
    s2 = raw_input()
    print lcs(s1, s2)

Submission status: Runtime Error

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

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

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

  return dp[slen][tlen]

n = int(raw_input())

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

Submission status: Runtime Error

Solution code:
n = int(input())
dataset = []
for i in range(n):
    tmp = []
    tmp.append(input())
    tmp.append(input())
    dataset.append(tmp)

for data in dataset:
    m = len(data[0])
    n = len(data[1])
    dp = []
    for x in range(n+1):
        dp.append([0] *(m+1))

    for j in range(n):
        for i in range(m):
            if data[0][i] == data[1][j]:
                dp[j+1][i+1] = dp[j][i] + 1
            else:
                #dp[j+1][i+1] = max(dp[j+1][i], dp[j][i+1])
                dp[J+1][i+1] = dp[j+1][i] if dp[j+1][i]>dp[j][i+1] else dp[j][i+1]
    print(dp[n][m])

Submission status: Runtime Error

Solution code:
n = int(input())
dataset = []
for i in range(n):
    tmp = []
    tmp.append(input())
    tmp.append(input())
    dataset.append(tmp)

for data in dataset:
    m = len(data[0])
    n = len(data[1])
    dp = []
    for x in range(n+1):
        dp.append([0] *(m+1))

    for j in range(n):
        for i in range(m):
            if data[0][i] == data[1][j]:
                dp[j+1][i+1] = dp[j][i] + 1
            elif dp[j+1][i]>dp[j][i+1]:
                dp[J+1][i+1] = dp[j+1][i] 
            else:
                dp[j+1][i+1] = dp[j][i+1]

    print(dp[n][m])

Submission status: Runtime Error

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

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

  return z2[-1]

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

Submission status: Runtime Error

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

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

  return z2[-1]

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

Submission status: Runtime Error

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

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

  return z2[-1]

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

Submission status: Runtime Error

Solution code:

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

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

Submission status: Runtime Error

Solution code:

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

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

Submission status: Runtime Error

Solution code:

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

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

Submission status: Runtime Error

Solution code:

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def edit_distance():
 s = raw_input()
 t = raw_input()
 a = len(X)
 b = len(Y)
 x = [0 for i in range(b+1)]
 for i in range(a):
   q = s[i]
   x2 = x1+[]
   for j in range(b):
    if (q ==t[j]):
     x[j+1] =x2[j]+1
    elif (x[j+1]<x2[j]+1):
      x[j+1] =x2[j]
 return x1[-1]
n = input()
for i2 in range(n):
 print edit_distance()

Submission status: Runtime Error

Solution code:
def edit_distance():
 s = raw_input()
 t = raw_input()
 a = len(s)
 b = len(t)
 x = [0 for i in range(b+1)]
 for i in range(a):
   q = s[i]
   x2 = x1+[]
   for j in range(b):
    if (q ==t[j]):
     x[j+1] =x2[j]+1
    elif (x[j+1]<x2[j]+1):
      x[j+1] =x2[j]
 return x1[-1]
n = input()
for i2 in range(n):
 print edit_distance()

Submission status: Runtime Error

Solution code:
def edit_distance():
 s = raw_input()
 t = raw_input()
 a = len(s)
 b = len(t)
 x = [0 for i in range(b+1)]
 for i in range(a):
   q = s[i]
   x2 = x1+[]
   for j in range(b):
    if (q ==t[j]):
     x[j+1] =x2[j]+1
    elif (x[j+1]<x[j]):
     x[j+1] =x2[j]
 return x1[-1]
n = input()
for i2 in range(n):
 print edit_distance()

Submission status: Runtime Error

Solution code:
def edit_distance():
 s = raw_input()
 t = raw_input()
 a = len(s)
 b = len(t)
 x = [0 for i in range(b+1)]
 for i in range(a):
   q = s[i]
   x2 = x1+[]
   for j in range(b):
    if (q ==t[j]):
     x[j+1] =x2[j]+1
    elif (x[j+1]<x[j]):
     x[j+1] =x2[j]
 return x[-1]
n = input()
for i2 in range(n):
 print edit_distance()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def lcs(x,y):
    x = " " + x
    y = " " + y    
    c = [[0]*(len(x)+1)]*(len(y)+1)
#    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: Runtime Error

Solution code:
def lcs(x,y):
    x = " " + x
    y = " " + y    
    c = [[0]*(len(x)+1)]*(len(y)+1)
    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: Runtime Error

Solution code:
def lcs(x,y):
    x = " " + x
    y = " " + y    
    c = [[0]*(len(x)+1)]*(len(y)+1)
#    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: Runtime Error

Solution code:
def lcs(x,y):
    x = " " + x
    y = " " + y    
    c = [[0]*(len(x)+1)]*(len(y)+1)
    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)