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:
def lcs(X, Y):
    X = " " + X
    Y = " " + Y
    c = [[0 for j in range(len(Y))] for i in range(len(X))]
    maxl = 0
    
    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
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
            maxl = max(maxl, c[i][j])
    return maxl
n = int(raw_input())
 
for i in range(n):
    s1 = raw_input()
    s2 = raw_input()
    print lcs(s1, s2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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
    X = ' ' + X
    Y = ' ' + Y
    
    for i in range(1, m+1):
        for j in range(1, n+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])
            maxl = max(maxl, c[i][j])
    return maxl

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

Submission status: Time Limit Exceeded

Solution code:
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
    X = ' ' + X
    Y = ' ' + Y
    
    for i in range(1, m+1):
        for j in range(1, n+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])
            maxl = max(maxl, c[i][j])
    return maxl

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

Submission status: Time Limit Exceeded

Solution code:
def LCS(X, Y):
    c = [[0 for i in range(0, len(Y)+1)] for j in range(0, len(X)+1)]
    m = len(X)
    n = len(Y)
    maxl = 0
    X = ' ' + X
    Y = ' ' + Y
     
    for i in range(1, m+1):
        for j in range(1, n+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])
            maxl = max(maxl, c[i][j])
    return maxl
 
q = int(raw_input())
for i in range(0, q):
    X = str(raw_input())
    Y = str(raw_input())
    print LCS(X, Y)

Submission status: Time Limit Exceeded

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

  return maxl



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

Submission status: Time Limit Exceeded

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

  return maxl



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

Submission status: Time Limit Exceeded

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)]
for k in range(q):
  maxl = 0
  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: Time Limit Exceeded

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

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

    return count_map[i][j]

p = input()

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

Submission status: Time Limit Exceeded

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

    for i in xrange(len(str1)):
        count_map[i][0] = 0
    for j in xrange(len(str2)):
        count_map[0][j] = 0


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

    return count_map[i][j]

p = input()

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

Submission status: Time Limit Exceeded

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

    for i in xrange(len(str1)):
        count_map[i][0] = 0
    for j in xrange(len(str2)):
        count_map[0][j] = 0


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

    return count_map[i][j]

p = input()

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

Submission status: Time Limit Exceeded

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

    for i in xrange(len(str1)):
        count_map[i][0] = 0
    for j in xrange(len(str2)):
        count_map[0][j] = 0


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

    return cnt

p = input()

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

Submission status: Time Limit Exceeded

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

    for i in xrange(len(str1)):
        count_map[i][0] = 0
    for j in xrange(len(str2)):
        count_map[0][j] = 0


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

    print count_map[i][j]

p = input()

for i in xrange(p):
    X = raw_input()
    Y = raw_input()
    count(X, Y)

Submission status: Time Limit Exceeded

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

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

    print count_map[i][j]

p = input()

for i in xrange(p):
    X = raw_input()
    Y = raw_input()
    count(X, Y)

Submission status: Time Limit Exceeded

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

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

    print count_map[i][j]

p = input()

for i in xrange(p):
    X = raw_input()
    Y = raw_input()
    count(X, Y)

Submission status: Time Limit Exceeded

Solution code:
DP_MAX = 1000
dp = [0] * (DP_MAX + 1)

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

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

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

  return dp[slen][tlen]

n = int(raw_input())

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

Submission status: Time Limit Exceeded

Solution code:
DP_MAX = 1000
dp = [0] * (DP_MAX + 1)

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

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

  for i in range(1, slen + 1):
    dp_i   = dp[i]
    dp_i_1 = dp[i-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:
DP_MAX = 1000
dp = [0] * (DP_MAX + 1)

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

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

  dp_i = dp[0]
  for i in range(1, slen + 1):
    dp_i_1 = dp_i
    dp_i   = dp[i]
    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 = [0] * (slen + 1)
  dp[0] = [0] * (tlen + 1)

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

  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 = [0] * (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:
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):
        si_1 = s[i-1]
        dpi = dp[i]
        dpi_1 = dp[i-1]
        Flag=False
        for j in range(1,len(t)+1):
            d=1 if s[i-1] == t[j-1] and dpi_1[j-1] == dp[i][j-1] else 0
            dpi[j] = max(dpi_1[j] ,
                           dpi[j-1] +d)
    return dp[len(s)][len(t)]
 
n = int(input())
for i in range(n):
    s = input()
    t = input()
    print(num_substr(s,t))

Submission status: 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):
        si_1 = s[i-1]
        dpi = dp[i]
        dpi_1 = dp[i-1]
        for j in range(1,len(t)+1):
            d=1 if si_1 == t[j-1] and dpi_1[j-1] == dpi[j-1] else 0
            dpi[j] = max(dpi_1[j] ,
                           dpi[j-1] +d)
    return dp[len(s)][len(t)]
 
n = int(input())
for i in range(n):
    s = input()
    t = input()
    print(num_substr(s,t))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)

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

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

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

    return main(lx - 1, ly - 1)


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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)


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

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

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

    return main(lx - 1, ly - 1)


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

Submission status: Time Limit Exceeded

Solution code:
def lcs(X, Y):
    m = len(X) + 1
    n = len(Y) + 1
    c = [[0] * n for _ in xrange(m)]
    X = ' ' + X
    Y = ' ' + Y
    for i in xrange(1,m):
        for j in xrange(1,n):
            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]
    print c[m-1][n-1]
    return 0

def main():
    q = int(raw_input())
    for i in xrange(q):
        X = raw_input()
        Y = raw_input()
        lcs(X,Y)
    return 0

main()

Submission status: Time Limit Exceeded

Solution code:
def lcs(X, Y):
    m = len(X) + 1
    n = len(Y) + 1
    c = [[0] * n for _ in xrange(m)]
    X = ' ' + X
    Y = ' ' + Y
    maxl = 0
    for i in xrange(1,m):
        for j in xrange(1,n):
            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] = max(c[i][j-1],c[i-1][j])
        maxl = max(maxl, c[i][j])
    print maxl
    return 0

def main():
    q = int(raw_input())
    for i in xrange(q):
        X = raw_input()
        Y = raw_input()
        lcs(X,Y)
    return 0

main()

Submission status: Time Limit Exceeded

Solution code:
def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0] * 1001 for i in range(1002)]
    x = " " + x
    y = " " + y
    maxl = 0
    for i in range(1, m + 1):
        for j in range(1, n + 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])
            maxl = max(maxl, c[i][j])
    return maxl

if __name__ == '__main__':
    n = int(input().rstrip())
    for i in range(n):
        s1 = input().rstrip()
        s2 = input().rstrip()
        print(lcs(s1, s2))

Submission status: Time Limit Exceeded

Solution code:
def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0] * 1001 for i in range(1002)]
    x = " " + x
    y = " " + y
    for i in range(1, m + 1):
        for j in range(1, n + 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])
    return max([e for l1 in c for e in l1])

if __name__ == '__main__':
    n = int(input().rstrip())
    for i in range(n):
        s1 = input().rstrip()
        s2 = input().rstrip()
        print(lcs(s1, s2))

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain
from collections import deque
from sys import stdin
def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0] * 1001 for i in range(1002)]
    x = " " + x
    y = " " + y
    for i in range(1, m + 1):
        for j in range(1, n + 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])
    return max(chain.from_iterable(c))


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

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain
from sys import stdin
def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0] * 1001 for i in range(1002)]
    # x = " " + x
    # y = " " + y
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i-1] == y[j-1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
    return max(chain.from_iterable(c))


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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from __future__ import print_function
from sys import stdin
def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0]*(n + 1) for a in range(m + 2)]
    for i in xrange(1, m + 1):
        for j in xrange(1, n + 1):
            if x[i-1] == y[j-1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
    return max(max(c))
 
n = int(raw_input().rstrip())
strs = stdin.readlines()
ret = []
for i in xrange(n):
    s1 = strs[i*2].rstrip()
    s2 = strs[i*2+1].rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
def lcs(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (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 = int(input().rstrip())
ret = [0] * n
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    ret[i] = lcs(s1, s2)
for i in range(n):
    print(ret[i])

Submission status: Time Limit Exceeded

Solution code:
def lcs(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (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 = int(input().rstrip())
ret = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
def lcs(X, Y):
    m, n = len(X), len(Y)
    cost = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            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[m][n]

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

Submission status: Time Limit Exceeded

Solution code:
pcsl = [[0 for i in range(1001)] for j in range(1001)]

def lcs(x, y):
    lx = len(x)
    ly = len(y)
    for i in range(lx):
        for j in range(ly):
            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: Time Limit Exceeded

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

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


q = int(input())

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

Submission status: Time Limit Exceeded

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


q = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
def lcs_len(x, y):
    ly = len(y)
    tcsl = [0 for i in range(ly + 1)]
    for x_i in x:
        pre_tcsl = list(tcsl)
        for j in range(ly):
            if x_i == y[j]:
                tcsl[j] = pre_tcsl[j - 1] + 1
            else:
                tcsl[j] = max(pre_tcsl[j], tcsl[j - 1])
    print(tcsl[j])


q = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
def lcs_len(x, y):
    ly = len(y)
    tcsl = [0 for i in range(ly + 1)]
    for x_i in x:
        pre_tcsl = list(tcsl)
        for j in range(ly):
            if x_i == y[j]:
                tcsl[j] = pre_tcsl[j - 1] + 1
            else:
                tcsl[j] = max(pre_tcsl[j], tcsl[j - 1])
    return tcsl[j]


q = int(input())

ans = []

for i in range(q):
    ax = input()
    ay = input()
    ans.append(lcs_len(ax, ay))

print(*ans, sep = '\n')

Submission status: Time Limit Exceeded

Solution code:
def lcs_len(x, y):
    ly = len(y)
    tcsl = [0 for i in range(ly + 1)]
    for x_i in x:
        pre_tcsl = list(tcsl)
        for j in range(ly):
            if x_i == y[j]:
                tcsl[j] = pre_tcsl[j - 1] + 1
            else:
                tcsl[j] = max(pre_tcsl[j], tcsl[j - 1])
    print(tcsl[j])


import sys

q = int(sys.stdin.readline())

for i in range(q):
    ax = sys.stdin.readline()[:-1]
    ay = sys.stdin.readline()[:-1]
    lcs_len(ax, ay)

Submission status: Time Limit Exceeded

Solution code:
def lcs_len(x, y):
    ly = len(y)
    tcsl = [0] * (ly + 1)
    for x_i in x:
        pre_tcsl = list(tcsl)
        for j in range(ly):
            if x_i == y[j]:
                tcsl[j] = pre_tcsl[j - 1] + 1
            else:
                tcsl[j] = max(pre_tcsl[j], tcsl[j - 1])
    print(tcsl[j])


q = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
import sys

def findLCS(X, Y):
    subx = list(set(X))
    suby = list(set(Y))
    extractSubsequence(X, subx[:], subx)
    extractSubsequence(Y, suby[:], suby)

    sublen = 0
    for sx in subx:
        for sy in suby:
            if sx == sy:
                sublen = len(sx)
    return sublen

def extractSubsequence(A, C, S):
    alen = len(A)
    flag = True
    while flag:
        for s in S:
            for c in C:
                sub = s + c
                if len(sub) > alen:
                    flag = False
                elif judgeSubInList(A, sub):
                    S.append(sub)

def judgeSubInList(A, sub):
    idx = 0
    slen = len(sub)
    for a in A:
        if a == sub[idx]:
            idx += 1
            if idx == slen:
                return True
    return False

lines = sys.stdin.readlines()
N = int(lines[0])

for i in range(N):
    X = lines[2 * i + 1].strip()
    Y = lines[2 * i + 2].strip()
    print findLCS(X, Y)

Submission status: Time Limit Exceeded

Solution code:
import sys

def findLCS(X, Y):
    C = [[0 for i in range(1001)] for j in range(1001)]
    X, Y = " " + X, " " + Y
    m, n, maxl = len(X), len(Y), 0

    for i in range(1, m):
        for j in range(1, n):
            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

lines = sys.stdin.readlines()
N = int(lines[0])

for i in range(N):
    X = lines[2 * i + 1].strip()
    Y = lines[2 * i + 2].strip()
    print findLCS(X, Y)

Submission status: Time Limit Exceeded

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()
        l = longest_common_seq(x,y)
        print(l)

Submission status: Time Limit Exceeded

Solution code:
def len_LCS(X,Y):
    Z = X
    if len(X) > len(Y): Z,Y = Y,X
    D = {}
    def len_LCS_core(Z,Y):
        if Z in D: return D[Z]
        if Z in Y:
            D[Z] = len(Z)
            return D[Z]
        D[Z] = 0
        if len(Z) < 2: return 0
        for i in range(len(Z)):
            D[Z] = max(D[Z], len_LCS_core(Z[:i]+Z[i+1:],Y))
        return D[Z]
    return len_LCS_core(Z,Y)
        
if __name__=='__main__':
    n = int(input())
    for _ in range(n):
        X = input()
        Y = input()
        print(len_LCS(X,Y))

Submission status: Time Limit Exceeded

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

if __name__=='__main__':
    q = int(input())
    for _ in range(q):
        X = input()
        Y = input()
        print(len_LCS(X,Y))

Submission status: Time Limit Exceeded

Solution code:
def len_LCS(X,Y):
    x_l = len(X)
    y_l = len(Y)
    lcs = [[0 for _ in range(x_l+1)] for _ in range(y_l+1)]
    for j in range(y_l):
        for i in range(x_l):
            if Y[j] == X[i]:
                lcs[j+1][i+1] = lcs[j][i] + 1
            else:
                lcs[j+1][i+1] = lcs[j+1][i] if lcs[j+1][i] > lcs[j][i+1] else lcs[j][i+1]
    return lcs[-1][-1]

if __name__=='__main__':
    q = int(input())
    for _ in range(q):
        X = input()
        Y = input()
        print(len_LCS(X,Y))