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: Time Limit Exceeded

Solution code:
n = int(input())

# result = []

memo = {}


def search(s1, s2):

    if (s1, s2) in memo:
        return memo[(s1, s2)]

    total = [0]

    if s1:
        s1_head, s1_body = s1[0], s1[1:]
        for idx2, s2_tgt in enumerate(s2):
            if s1_head == s2_tgt:
                total.append(1+search(s1_body, s2[idx2+1:]))

    if s2:
        s2_head, s2_body = s2[0], s2[1:]
        for idx1, s1_tgt in enumerate(s1):
            if s2_head == s1_tgt:
                total.append(1+search(s1[idx1+1:], s2_body))

    if s1 and s2:
        total.append(search(s1[1:], s2[1:]))

    memo[(s1, s2)] = max(total)
    return max(total)
    # print(rs)


for _ in range(n):
    s1 = input()
    s2 = input()
    result = search(s1, s2)
    print(result)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())


def lcs(s1, s2):
    N, M = len(s1), len(s2)

    for _ in range(N+1):
        c.append([0]*(M+1))

    for i in range(1, N+1):
        for j in range(1, M+1):
            if s1[i-1] == s2[j-1]:
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i-1][j], c[i][j-1])


for _ in range(n):
    c = []
    s1 = input()
    s2 = input()
    lcs(s1, s2)
    print(c[len(s1)][len(s2)])
    # print(c[len(s1)], c[len(s2)])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

def LCS(A, B):
    N = len(A)
    M = len(B)
    dp = [[0] * (M+1) for i in range(N+1)]
    for i in range(N+1):
        for j in range(M+1):
            # 下に送る
            if i < N:
                dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            # 右に送る
            if j < M:
                dp[i][j+1] = max(dp[i][j+1], dp[i][j])
            # 今回増やす文字が一致するなら、LCSが1文字増える
            if i < N and j < M and A[i] == B[j]:
                # 右下に送る
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
    return dp[N][M]

Q=INT()

for _ in range(Q):
    a=input()
    b=input()
    print(LCS(a, b))

Submission status: Time Limit Exceeded

Solution code:
q = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
q = int(input())


for __ in range (q):

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


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

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

Submission status: Time Limit Exceeded

Solution code:
q = int(input())


for __ in range (q):

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


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

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

Submission status: Time Limit Exceeded

Solution code:
t=int(input())
for _ in range(t):
    s=str(input())
    t=str(input())
    dp = [[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i]==t[j]:
                dp[i+1][j+1]=dp[i][j]+1
            else:
                dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
    print(dp[len(s)][len(t)])

Submission status: Time Limit Exceeded

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
# Longest Common Subsequence
# Result:
import sys

def get_matrix_val(matrix, xlen, i, j):
    if i < 0 or j < 0: return 0
    return matrix[xlen * j + i]

def set_matrix_val(matrix, xlen, i, j, val):
    matrix[xlen * j + i] = val

def lcs(str1, str2):
    lstr1 = len(str1)
    lstr2 = len(str2)
    lcsmax = [0] * (lstr1 * lstr2)
    for i in range(0, lstr1):
        for j in range(0, lstr2):
            if str1[i] == str2[j]:
                v = get_matrix_val(lcsmax, lstr1, i - 1, j - 1)
                set_matrix_val(lcsmax, lstr1, i, j, v + 1)
            else:
                v1 = get_matrix_val(lcsmax, lstr1, i - 1, j)
                v2 = get_matrix_val(lcsmax, lstr1, i, j - 1)
                if v1 > v2:
                    set_matrix_val(lcsmax, lstr1, i, j, v1)
                else:
                    set_matrix_val(lcsmax, lstr1, i, j, v2)
    return lcsmax[-1]

ntest = int(sys.stdin.readline().strip())
for _ in range(0, ntest):
    l1 = sys.stdin.readline().strip()
    l2 = sys.stdin.readline().strip()
    print lcs(l1, l2)

Submission status: Time Limit Exceeded

Solution code:
import sys


def lcs(x, y):
    # Creating len(x + 1) * len(y + 1) table
    x = ' ' + x  # Add Space
    y = ' ' + y  # Add Space
    len_x = len(x)
    len_y = len(y)
    table = []
    for _ in range(len_y):
        table.append([0] * len_x)

    maxl = 0
    for i, x_ch in enumerate(x):
        if i == 0: continue
        for j, y_ch in enumerate(y):
            if j == 0: continue
            if x[i] == y[j]:
                table[j][i] = table[j - 1][i - 1] + 1
            else:
                table[j][i] = max(table[j - 1][i], table[j][i - 1])
            maxl = max(maxl, table[j][i])

    return maxl


if __name__ == "__main__":
    lines = [line.strip() for line in sys.stdin.readlines()[1:]]
    for sequence_pair in zip(lines[::2], lines[1::2]):
        print(lcs(*sequence_pair))

Submission status: Time Limit Exceeded

Solution code:
"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
"""

from __future__ import division
from sys import stdin, maxint

def lcs(s1, s2):
	dp = [[0 for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]

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

	return dp[len(s1)][len(s2)]

if __name__ == '__main__':
	tc = int(stdin.readline())
	for _ in range(tc):
		sa = stdin.readline().strip()
		sb = stdin.readline().strip()
		print(lcs(sa, sb))

Submission status: Time Limit Exceeded

Solution code:
"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
"""

from __future__ import division
from sys import stdin, maxint

def lcs(s1, s2):
	dp = [[0 for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]

	for i in xrange(1, len(s1) + 1):
		for j in xrange(1, len(s2) + 1):
			if s1[i - 1] == s2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

	return dp[len(s1)][len(s2)]

if __name__ == '__main__':
	tc = int(stdin.readline())
	for _ in range(tc):
		sa = stdin.readline().strip()
		sb = stdin.readline().strip()
		print(lcs(sa, sb))

Submission status: Time Limit Exceeded

Solution code:
"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
"""

from __future__ import division
from sys import stdin, maxint

def lcs(s1, s2):
	dp = [[0 for _ in xrange(len(s2) + 1)] for _ in xrange(2)]

	for i in xrange(1, len(s1) + 1):
		for j in xrange(1, len(s2) + 1):
			if s1[i - 1] == s2[j - 1]:
				dp[i & 1][j] = dp[1 - i & 1][j - 1] + 1
			else:
				dp[i & 1][j] = max(dp[1 - i & 1][j], dp[i & 1][j - 1])

	return dp[len(s1) & 1][len(s2)]

if __name__ == '__main__':
	tc = int(stdin.readline())
	for _ in range(tc):
		sa = stdin.readline().strip()
		sb = stdin.readline().strip()
		print(lcs(sa, sb))

Submission status: Time Limit Exceeded

Solution code:
"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
"""

from __future__ import division
from sys import stdin, maxint

def lcs(s1, s2):
	la, lb = len(s1), len(s2)
	dp1 = [0 for _ in range(lb + 1)]

	for i in xrange(1, la + 1):
		dp2 = dp1[0:]
		for j in xrange(1, lb + 1):
			if s1[i - 1] == s2[j - 1]:
				dp1[j] = dp2[j - 1] + 1
			else:
				dp1[j] = max(dp1[j - 1], dp2[j])

	return dp1[-1]

if __name__ == '__main__':
	tc = int(stdin.readline())
	for _ in range(tc):
		sa = stdin.readline().strip()
		sb = stdin.readline().strip()
		print(lcs(sa, sb))

Submission status: Time Limit Exceeded

Solution code:
"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
"""


def lcs():
	s1 = raw_input()
	s2 = raw_input()
	la, lb = len(s1), len(s2)
	dp1 = [0 for _ in range(lb + 1)]

	for i in range(la):
		dp2 = dp1 + []
		for j in range(lb):
			if s1[i] == s2[j]:
				dp1[j + 1] = dp2[j] + 1
			else:
				dp1[j + 1] = dp1[j] if dp1[j] > dp2[j + 1] else dp2[j + 1]

	return dp1[-1]

tc = int(raw_input())
for _ in range(tc):
	print(lcs())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

# main
q = int(input())
for a in range(q):
    X = input()
    Y = input()
    m = len(X)
    n = len(Y)
    c = [[0 for j in range(n + 1)] for i in range(m + 1)]
    for i in range(m + 1):
        c[i][0] = 0
    for j in range(n + 1):
        c[0][j] = 0
    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][j - 1], c[i - 1][j])
    print(c[m][n])

Submission status: Time Limit Exceeded

Solution code:
q = int(raw_input())

for i in range(q):
    X = raw_input()
    Y = raw_input()
    lcs = {}
    for i in range(len(X)+1):
        lcs[i] = {}
        for j in range(len(Y)+1):
            lcs[i][j] = 0
    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: Time Limit Exceeded

Solution code:
q = int(raw_input())

lcs = {}
for i in range(1010):
    lcs[i] = {}
    for j in range(1010):
        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: Time Limit Exceeded

Solution code:
q = int(raw_input())

lcs = [[0 for j in xrange(1010)] for i in xrange(1010)]

for i in xrange(q):
    X = raw_input()
    Y = raw_input()
    for i in xrange(len(X)):
        for j in xrange(len(Y)):
            if X[i] == Y[j]:
                lcs[i+1][j+1] = lcs[i][j] + 1
            elif lcs[i][j+1] > lcs[i+1][j]:
                lcs[i+1][j+1] = lcs[i][j+1]
            else:
                lcs[i+1][j+1] = lcs[i+1][j]
    print lcs[len(X)][len(Y)]

Submission status: Time Limit Exceeded

Solution code:
q = int(raw_input())

for i in xrange(q):
    X = raw_input()
    Y = raw_input()
    lcs1 = [0 for i in range(len(Y)+1)]
    for i in xrange(len(X)):
        lcs2 = lcs1+[]
        for j in xrange(len(Y)):
            if X[i] == Y[j]:
                lcs2[j+1] = lcs1[j] + 1
            elif lcs1[j+1] > lcs2[j]:
                lcs2[j+1] = lcs1[j+1]
            else:
                lcs2[j+1] = lcs2[j]
        lcs1 = lcs2
    print lcs2[-1]

Submission status: Time Limit Exceeded

Solution code:
q = int(raw_input())

for i in xrange(q):
    X = raw_input()
    Y = raw_input()
    lcs1 = [0 for i in range(len(Y)+1)]
    for i in xrange(len(X)):
        lcs2 = lcs1+[]
        for j in xrange(len(Y)):
            if X[i] == Y[j]:
                lcs1[j+1] = lcs2[j] + 1
            elif lcs2[j+1] > lcs1[j]:
                lcs1[j+1] = lcs2[j+1]
            else:
                lcs1[j+1] = lcs1[j]
    print lcs1[-1]

Submission status: Time Limit Exceeded

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

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

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

    maxl = 0

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

            maxl = max(maxl, dp[i][j])

    return maxl

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

Submission status: Time Limit Exceeded

Solution code:
def lcs(s, t):
  dp = {}

  for i in range(len(s) + 1):
    dp[i] = {0: 0}
  for j in range(len(t) + 1):
    dp[0][j] = 0

  for i in range(1, len(s) + 1):
    for j in range(1, len(t) + 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[len(s)][len(t)]

n = int(raw_input())

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

Submission status: Time Limit Exceeded

Solution code:
def lcs(s, t):
  dp = {}
  slen = len(s)
  tlen = len(t)

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

  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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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])
    i, j = 0, 0
    dp = []
    for x in range(n+1):
        dp.append([0] *(m+1))

    lcs = 0
    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])

            if dp[j+1][i+1] > lcs:
                lcs = dp[j+1][i+1]
        
    print(lcs)

Submission status: Time Limit Exceeded

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])
    i, j = 0, 0
    dp = []
    for x in range(n+1):
        dp.append([0] *(m+1))

    lcs = 0
    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])

            #if dp[j+1][i+1] > lcs:
            #   lcs = dp[j+1][i+1]
        
    #print(lcs)
    print(dp[n][m])

Submission status: Time Limit Exceeded

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])
    i, j = 0, 0
    dp = []
    #for x in range(n+1):
    #    dp.append([0] *(m+1))
    dp = [[0 for i in range(m+1)] for j in range(n+1)]
    lcs = 0
    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])

            #if dp[j+1][i+1] > lcs:
            #   lcs = dp[j+1][i+1]
        
    #print(lcs)
    print(dp[n][m])

Submission status: Time Limit Exceeded

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])

    print(dp[n][m])

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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

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: Time Limit Exceeded

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-1] == y[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[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: Time Limit Exceeded

Solution code:

def LCS(x, y):
    len_x = len(x)
    len_y = len(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-1] == y[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[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: Time Limit Exceeded

Solution code:
def num_substr(s, t):
    dp = {}
    for i in range(len(s) + 1):
        dp[i] = {0: 0}
    for j in range(len(t) + 1):
        dp[0][j] = 0
    
    for i in range(1,len(s)+1):
        Flag=False
        for j in range(1,len(t)+1):
            d=1 if s[i-1] == t[j-1] and dp[i-1][j-1] == dp[i][j-1] else 0
            dp[i][j] = max(dp[i-1][j] ,
                           dp[i][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: Time Limit Exceeded

Solution code:
def lcs(x,y):
    xs = len(x)
    ys = len(y)
    x = " " + x
    y = " " + y
    c = [[0 for i in xrange(len(x))] for j in xrange(len(y))] 
    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))

n = input()

for i in xrange (n):

    x = raw_input()
    y = raw_input()

    print lcs(x,y)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def lcs(x,y):
    xs = len(x)
    ys = len(y)
    x = " " + x
    y = " " + y
    c = [[0 for i in xrange(len(x))] for j in xrange(len(y))]
    for i in xrange (1,len(y)):
        for j in xrange (1,len(x)):
            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)
    return max(max(c))
n = input() 
for i in xrange (n): 
    x = raw_input()
    y = raw_input() 
    print lcs(x,y)

Submission status: Time Limit Exceeded

Solution code:
def lcs(x,y):
    x = " " + x
    y = " " + y
    c = [[0 for i in xrange(len(x))] for j in xrange(len(y))]
    for i in xrange (1,len(y)):
        for j in xrange (1,len(x)):
            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)
    return max(max(c))
n = input() 
for i in xrange (n): 
    x = raw_input()
    y = raw_input() 
    print lcs(x,y)

Submission status: Time Limit Exceeded

Solution code:
def lcs(x,y):
    x = " " + x
    y = " " + y
    c = [[0 for i in xrange(len(x))] for j in xrange(len(y))]
    for i in xrange (1,len(y)):
        for j in xrange (1,len(x)):
            if x[j] == y[i]:
                c[i][j] = c[i-1][j-1] + 1
            else:
                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: Time Limit Exceeded

Solution code:
def lcs(x,y):
    x = " " + x
    y = " " + y
    c = [[0 for i in xrange(len(x))] for j in xrange(len(y))]
    for i in xrange (1,len(y)):
        for j in xrange (1,len(x)):
            if x[j] == 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]
    return max(max(c))
n = input() 
for i in xrange (n): 
    x = raw_input()
    y = raw_input() 
    print lcs(x,y)

Submission status: Time Limit Exceeded

Solution code:
n = input() 
for i in xrange (n): 
    x = raw_input()
    y = raw_input() 
    
    x = " " + x
    y = " " + y
    c = [[0 for i in xrange(len(x))] for j in xrange(len(y))]
    for i in xrange (1,len(y)):
        for j in xrange (1,len(x)):
            if x[j] == 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 max(max(c))

Submission status: Time Limit Exceeded

Solution code:
def lcs():
    x = raw_input()
    y = raw_input() 
    x = " " + x
    y = " " + y
    c = [[0 for i in xrange(len(x))] for j in xrange(len(y))]
    for i in xrange (1,len(y)):
        for j in xrange (1,len(x)):
            if x[j] == 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]
    return max(max(c))
n = input() 
for i in xrange (n): 

    print lcs()

Submission status: Time Limit Exceeded

Solution code:
def LCS():
 x = raw_input()
 y = raw_input()
 i = len(x)
 j = len(y)

 dsp = [[0 for col in range(j+1)] for row in range(i+1)]
 for i in range(1,i+1):
  for j in range(1,j+1):
   if x[i-1] == y[j-1]:
    dsp[i][j] = dsp[i-1][j-1]+1
   else:
    dsp[i][j] = max(dsp[i-1][j],dsp[i][j-1])
 return dsp[i][j]

q = input()
for i in range(q):
 print LCS()

Submission status: Time Limit Exceeded

Solution code:
def LCS():
 x = raw_input()
 y = raw_input()
 i, j = len(x), len(y)

 dsp = [[0 for col in xrange(j+1)] for row in xrange(i+1)]
 for i in xrange(1,i+1):
  for j in xrange(1,j+1):
   if x[i-1] == y[j-1]:
    dsp[i][j] = dsp[i-1][j-1]+1
   else:
    dsp[i][j] = max(dsp[i-1][j],dsp[i][j-1])
 print dsp[i][j]

q = input()
for i in range(q):
 LCS()

Submission status: Time Limit Exceeded

Solution code:
def LCS():
 x = raw_input()
 y = raw_input()
 i, j = len(x), len(y)

 dsp = [[0 for col in xrange(j+1)] for row in xrange(i+1)]
 for i in xrange(1,i+1):
  for j in xrange(1,j+1):
   if x[i-1] == y[j-1]:
    dsp[i][j] = dsp[i-1][j-1]+1
   else:
    dsp[i][j] = max(dsp[i-1][j],dsp[i][j-1])
 print dsp[-1][-1]

q = input()
for i in xrange(q):
 LCS()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
ans = {}

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

Submission status: Time Limit Exceeded

Solution code:
ans = {}

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

Submission status: Time Limit Exceeded

Solution code:
roop = input()
for k in range(roop):
    str1 = raw_input()
    str2 = raw_input()
    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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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
            elif after[j - 1] > before[j]:
                after[j] = after[j - 1]
    print after[j]