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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys


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

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

    return count_list[m][n]


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


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

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

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

Submission status: Runtime Error

Solution code:
from typing import List


def make_lcs(lhs, rhs):
    pass


class stub():
    def __init__(self):
        self.fin = open('task.txt')

    def stub_input(self):
        return self.fin.readline()


# _stub = stub()
# input = _stub.stub_input


def make_lcs(lhs: List[str], rhs: List[str]):
    c = [[0 for _ in range(len(rhs) + 1)] for _ in range(len(lhs) + 1)]
    for l_i in range(len(lhs)):
        for r_i in range(len(rhs)):
            if lhs[l_i] == rhs[r_i]:
                c[l_i + 1][r_i + 1] = c[l_i][r_i] + 1
            else:
                c[l_i + 1][r_i + 1] = max(c[l_i][r_i + 1], c[l_i + 1][r_i])
    print(c[-1][-1])


if __name__ == '__main__':
    n = int(input())
    for _ in range(n):
        lhs = [i for i in input().rstrip()]
        rhs = [i for i in input().rstrip()]
        make_lcs(lhs, rhs)

Submission status: Runtime Error

Solution code:
import itertools
import time

c = [[0 for _ in range(1001)] for _ in range(1001)]

def make_lcs(lhs, rhs):
    llen = len(lhs)
    rlen = len(rhs)
    for l_i, r_i in itertools.product(range(llen), range(rlen)):
            c[l_i + 1][r_i + 1] = max(c[l_i][r_i + 1], c[l_i + 1][r_i]) if lhs[l_i] != rhs[r_i] else c[l_i][r_i] + 1
    print(c[llen][rlen])


if __name__ == '__main__':
    # start = time.time()
    n = int(input())
    for _ in range(n):
        lhs = [i for i in input().rstrip()]
        rhs = [i for i in input().rstrip()]
        make_lcs(lhs, rhs)
    end = time.time() - start
    # print('elapsed time: {}'.format(end))

Submission status: Runtime Error

Solution code:
import itertools
import numpy
import time

c = [[0]*1001 for _ in range(1001)]

def make_lcs(lhs, rhs):
    llen = len(lhs)
    rlen = len(rhs)
    for l_i, r_i in itertools.product(range(llen), range(rlen)):
            c[l_i + 1][r_i + 1] = max(c[l_i][r_i + 1], c[l_i + 1][r_i]) if lhs[l_i] != rhs[r_i] else c[l_i][r_i] + 1
    print(c[llen][rlen])


if __name__ == '__main__':
    start = time.time()
    n = int(input())
    for _ in range(n):
        lhs = [i for i in input().rstrip()]
        rhs = [i for i in input().rstrip()]
        make_lcs(lhs, rhs)
    end = time.time() - start
    print('elapsed time: {}'.format(end))

Submission status: Runtime Error

Solution code:
def lcs_rec(i, j):
    if i == 0 or j == 0:
        return 0

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

q = int(input())

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

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

    print(ans)

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(3 * 1000)

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

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

q = int(input())

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

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

    print(ans)

Submission status: Runtime Error

Solution code:
q = int(input().rstrip())
data_set = [[[i for i in input().rstrip()],
             [i for i in input().rstrip()]] for i in range(q)]

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


def lcs(X: list, Y: list):
    global common_list
    m, n = len(X), len(Y)
    for i in range(1, m + 1):
        for k in range(1, n + 1):
            if X[i - 1] == Y[k - 1]:
                common_list[i][k] = common_list[i - 1][k - 1] + 1
            elif common_list[i - 1][k] >= common_list[i][k - 1]:
                common_list[i][k] = common_list[i - 1][k]
            else:
                common_list[i][k] = common_list[i][k - 1]
    return common_list[m][n]


for l, r in data_set:
    print(lcs(l, r))

Submission status: Runtime Error

Solution code:
q = int(input())

def lcss(x,y):
    
    lcs = [0]*(len(x)+1)
    for i in range(len(y)):
        w1 = y[i]
        lcs_2 = lcs[:]
        for j in range(len(x)):
            if x[j] == w1:
                lcs[j+1] = lcs_2[j] + 1  
            elif lcs[j+1] < lcs[j]:
                lcs[j+1] = lcs[j]
    return lcs[-1]

ret = []
for i in range(q):
    x = input()
    y = input()
    ret.append(lcss())
print(*ret,sep= "\n")

Submission status: Runtime Error

Solution code:
def get_longest_count(X, Y):
  count = 0
  while len(X) > 0 and len(Y) > 0:
    if X[-1] != Y[-1]:
      return count + max(get_longest_count(X[:-1], Y), get_longest_count(X, Y[:-1]))
    else:
      X = X[:-1]
      Y = Y[:-1]
      count += 1
  return count

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

Submission status: Runtime Error

Solution code:
def lcs_len(x, y):
    indices = [0]
    for y_i in y:
        t_index = 0
        for i, index in enumerate(indices, 1):
            c_index = x.find(y_i, t_index) + 1
            if c_index:
                if i < len(indices):
                    t_index = indices[i]
                    indices[i] = min(c_index, t_index)
                else:
                    indices.append(c_index)
                    break
    print(len(indices) - 1)


def answer(X, Y):
    m, n = len(X), len(Y)
    C = [[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]:
                C[i][j] = C[i-1][j-1] + 1
            else:
                C[i][j] = max(C[i][j -1], C[i -1][j])
    return C[m][n]


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

Submission status: Runtime Error

Solution code:
def lcs_len(x, y):
    indices = [0]
    for y_i in y:
        t_index = 0
        for i, index in enumerate(indices, 1):
            c_index = x.find(y_i, t_index) + 1
            if c_index:
                if i < len(indices):
                    t_index = indices[i]
                    indices[i] = min(c_index, t_index)
                else:
                    indices.append(c_index)
                    break
    print(len(indices) - 1)


def answer(X, Y):
    m, n = len(X), len(Y)
    C = [[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]:
                C[i][j] = C[i-1][j-1] + 1
            else:
                C[i][j] = max(C[i][j -1], C[i -1][j])
    return C[m][n]


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

Submission status: Runtime Error

Solution code:
def lcs_better(X, Y):
    costs = [0]
    for c in Y:
        for i in range(len(costs) - 1, -1, -1):
            tmp = X.find(c, costs[i])
            if tmp + 1:
                if i + 1 < len(costs):
                    costs[i + 1] = min(costs[i + 1], tmp + 1)
                else:
                    costs.append(tmp + 1)
    return len(costs) - 1


def answer(X, Y):
    m, n = len(X), len(Y)
    C = [[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]:
                C[i][j] = C[i-1][j-1] + 1
            else:
                C[i][j] = max(C[i][j -1], C[i -1][j])
    return C[m][n]


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

Submission status: Runtime Error

Solution code:
dp = [[0] * (1001) for i in xrange(1001)]

def main():
????????n = input()
????????for i in xrange(n):
????????????????X = raw_input()
????????????????Y = raw_input()
????????????????print lcs(X,Y)
??
def lcs(X,Y):
????????m = len(X)
????????n = len(Y)
????????for i in xrange(m):
????????????????for j in xrange(n):
????????????????????????if X[i] == Y[j]:
????????????????????????????????dp[i+1][j+1] = dp[i][j] + 1
????????????????????????else:
????????????????????????????????if dp[i][j+1] >= dp[i+1][j]:
????????????????????????????????????????dp[i+1][j+1] = dp[i][j+1]
????????????????????????????????else:
????????????????????????????????????????dp[i+1][j+1] = dp[i+1][j]
????????return dp[m][n]
??????????
if __name__ == "__main__":
????????main()

Submission status: Runtime Error

Solution code:
dp = [[0] * 1001 for i in xrange(1001)]

def main():
????????n = input()
????????for i in xrange(n):
????????????????X = raw_input()
????????????????Y = raw_input()
????????????????print lcs(X,Y)
??
def lcs(X,Y):
????????m = len(X)
????????n = len(Y)
????????for i in xrange(m):
????????????????for j in xrange(n):
????????????????????????if X[i] == Y[j]:
????????????????????????????????dp[i+1][j+1] = dp[i][j] + 1
????????????????????????else:
????????????????????????????????if dp[i][j+1] >= dp[i+1][j]:
????????????????????????????????????????dp[i+1][j+1] = dp[i][j+1]
????????????????????????????????else:
????????????????????????????????????????dp[i+1][j+1] = dp[i+1][j]
????????return dp[m][n]
??????????
if __name__ == "__main__":
????????main()

Submission status: Runtime Error

Solution code:
def calc_lcs(X, Y):
    from array import array
    max_lcs = 0
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y
    c = array('b', [0] * (1001 * 1001))
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i] == Y[j]:
                c[i*1001 + j] = c[(i-1)*1001 + j - 1] + 1
            elif c[(i-1)*1001 + j] >= c[i*1001 + j - 1]:
                c[i*1001 + j] = c[(i-1)*1001 + j]
            else:
                c[i*1001 + j] = c[i*1001 + j - 1]
            max_lcs = max(max_lcs, c[i*1001 + j])
    return max_lcs


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    # num = 1

    for _ in range(num):
        X = input()
        Y = input()
        # X = 'abcbdab'
        # Y = 'bdcaba'


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

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

Submission status: Runtime Error

Solution code:
def calc_lcs(X, Y):
    from array import array
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y
    c = array('I', [0] * (1001 * 1001))
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i] == Y[j]:
                c[i*1001 + j] = c[(i-1)*1001 + j - 1] + 1
            elif c[(i-1)*1001 + j] >= c[i*1001 + j - 1]:
                c[i*1001 + j] = c[(i-1)*1001 + j]
            else:
                c[i*1001 + j] = c[i*1001 + j - 1]
    return max(c)


if __name__ == '__main__':
    # ??????????????\???
    # num = int(input())
    f = open('input.txt')
    num = int(f.readline())

    for _ in range(num):
        # X = input()
        # Y = input()
        X = f.readline().strip()
        Y = f.readline().strip()

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

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

Submission status: Runtime Error

Solution code:
def calc_lcs2(X, Y):
    max_lcs = 0
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y
    c = [[0]*(m+1) for i in range(n+1)]
    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
            elif c[i - 1][j] >= c[i][j - 1]:
                c[i][j] = c[i - 1][j]
            else:
                c[i][j] = c[i][j - 1]
    for row in c:
        max_lcs = max(row)
    return max_lcs



if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    # f = open('input.txt')
    # num = int(f.readline())

    for _ in range(num):
        X = input()
        Y = input()
        # X = f.readline().strip()
        # Y = f.readline().strip()

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

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

Submission status: Runtime Error

Solution code:
def prep_array(X, Y):
    """ ??????0???2?¬???????????????¨??????????????????????????\????????????????????§??????????????????????¨?(1000+1) """
    c = [[0]*1001 for _ in range(1000+1)]
    return c


def check_max(array):
    """ 2?¬????????????????????????§??????????????? """
    max_lcs = 0
    for row in array:
        temp_max = max(row)
        if temp_max > max_lcs:
            max_lcs = temp_max
    return max_lcs


def calc_lcs4(X, Y, c):
    """
    X[i]???for j?????????????????????????????°????????????????????§???
    4/5 ?????????????????????????????¨????????????????????????????????°??§6.5?§?
    """
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)
    max_lcs = 0

    pre_row = c[0]
    for i in range(1, m):
        row = c[i]
        XX = X[i]
        for j, YY in enumerate(Y):
            if XX == YY:
                row[j] = pre_row[j - 1] + 1
                if row[j] > max_lcs:
                    max_lcs = row[j]
            elif pre_row[j] >= row[j - 1]:
                row[j]= pre_row[j]
            else:
                row[j] = row[j - 1]
        pre_row = row
    return max_lcs



def calc_lcs3(X, Y, c):
    """
    X[i]???for j?????????????????????????????°????????????????????§???
    4/5 ?????????????????????????????¨????????????????????????????????°??§7.1?§?
    """
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y

    pre_row = c[0]
    for i in range(1, m+1):
        row = c[i]
        XX = X[i]
        for j in range(1, n+1):
            if XX == Y[j]:
                row[j] = pre_row[j - 1] + 1
            elif pre_row[j] >= row[j - 1]:
                row[j] = pre_row[j]
            else:
                row[j] = row[j - 1]
        pre_row = row
    return check_max(c)



def calc_lcs2(X, Y, c):
    """
    c[i][j]????????¢????????????????????????????????§?????????????????¨?????????????????°??????????????????????????£??????????????§???
    4/5 ?????????????????????????????¨????????????????????????????????°??§8.2?§?
    """
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y

    pre_row = c[0]
    for i in range(1, m+1):
        row = c[i]
        for j in range(1, n+1):
            if X[i] == Y[j]:
                row[j] = pre_row[j - 1] + 1
            elif pre_row[j] >= row[j - 1]:
                row[j] = pre_row[j]
            else:
                row[j] = row[j - 1]
        pre_row = row
    return check_max(c)



def calc_lcs(X, Y, c):
    """
    ??????????????¢?????´????????????????????????????£?????????????
    4/5 ?????????????????????????????¨????????????????????????????????°??§12.5?§?
    """
    m = len(X)
    n = len(Y)
    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
            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 check_max(c)


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    # f = open('input.txt')
    # num = int(f.readline())

    for _ in range(num):
        X = input()
        Y = input()
        # X = f.readline().strip()
        ??????# Y = f.readline().strip()

        # ???????????????
        result = calc_lcs4(X, Y, prep_array(X, Y))

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

Submission status: Runtime Error

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: Runtime Error

Solution code:

def lcs():
    A = input()
    B = 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: Runtime Error

Solution code:
def main():
    num = int(input())
    for i in range(num):
        X = " " + input()
        Y = " " + input()
        lx = len(X)
        ly = len(Y)
        max = 0
        XY = [[0] * ly for i in range(lx)]
        for j in range(1,lx):
            for k in range(1,ly):
                if X[j] == Y[k]:
                    XY[j][k] = XY[j-1][k-1] + 1
                elif XY[j-1][k] > XY[j][k-1]:
                    XY[j][k] = XY[j-1][k]
                else:
                    XY[j][k] = XY[j][k-1]
                if max < XY[j][k]:
                    max = XY[j][k]
        print(max)
 f __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

????????±?????¨??????
"""
# 4/5??§Time Limit Exceeded 5.20s ????????????5s??\???????????????????????????

c = []
def prep_array(X, Y):
    global c
    """ ??????0???2?¬???????????????¨??????????????????????????\????????????????????§??????????????????????¨?(1000+1)??\???????????? """
    # from array import array
    # c = [array('I', [0] * (len(X)+1)) for _ in range(len(Y)+1)]  #  array??§??¨???
    c = [[0]*(len(X)+2) for _ in range(len(Y)+2)] #  ???????????§??¨???
    return c


def check_max(array):
    """ 2?¬????????????????????????§??????????????? """
    max_lcs = 0
    for row in array:
        temp_max = max(row)
        if temp_max > max_lcs:
            max_lcs = temp_max
    return max_lcs


def calc_lcs4(X, Y, c):
    """
    Y[j]?????¢???????????????????????´
    ?????????????????????????????°?????????????????????????????´
    ????????±?????¨???????????¢??°?????§?¨????????????????????????´
    4/5 ?????????????????????????????¨?????????????????????????????°????????¨??????????????? 5.6?§?
    """
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)
    max_lcs = 0

    pre_row = c[0]
    for i in range(1, m):
        row = c[i]
        XX = X[i]
        for j, YY in enumerate(Y):
            if XX == YY:
                pr_j1 = pre_row[j - 1]
                row[j] = pr_j1 + 1
                if pr_j1+1 > max_lcs:
                   max_lcs = pr_j1 + 1
            else:
                pr_j = pre_row[j]
                r_j1 = row[j-1]
                if pr_j >= r_j1:
                    row[j] = pr_j
                else:
                    row[j] = r_j1
        pre_row = row
    return max_lcs


def calc_lcs3(X, Y, c):
    """
    X[i]???for j?????????????????????????????°(XX)????????????????????§???
    4/5 ?????????????????????????????¨?????????????????????????????°????????¨??????????????? 6.5?§?
    """
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y

    pre_row = c[0]
    for i in range(1, m+1):
        row = c[i]
        XX = X[i]
        for j in range(1, n+1):
            if XX == Y[j]:
                row[j] = pre_row[j - 1] + 1
            elif pre_row[j] >= row[j - 1]:
                row[j] = pre_row[j]
            else:
                row[j] = row[j - 1]
        pre_row = row
    return check_max(c)



def calc_lcs2(X, Y, c):
    """
    c[i][j]????????¢????????????????????????????????§???????????????(row)??¨?????????(pre_row)????????°??????????????????????????£??????????????§???
    4/5 ?????????????????????????????¨?????????????????????????????°????????¨??????????????? 7.5?§?
    """
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y

    pre_row = c[0]
    for i in range(1, m+1):
        row = c[i]
        for j in range(1, n+1):
            if X[i] == Y[j]:
                row[j] = pre_row[j - 1] + 1
            elif pre_row[j] >= row[j - 1]:
                row[j] = pre_row[j]
            else:
                row[j] = row[j - 1]
        pre_row = row
    return check_max(c)


def calc_lcs1(X, Y):
    """
    ?????????????????????array?????????????????¨???byte???????????¨????????¨????§??????????????????????????????????????????§?????¨???????????£?????????int???????????¨???
    4/5 ?????????????????????????????¨?????????????????????????????°????????¨??????????????? 18.5?§?
    """
    from array import array
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y
    c = array('i', [0] * (1024 * 1024))
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i] == Y[j]:
                c[i*1024 + j] = c[(i-1)*1024 + j - 1] + 1
            elif c[(i-1)*1024 + j] >= c[i*1024 + j - 1]:
                c[i*1024 + j] = c[(i-1)*1024 + j]
            else:
                c[i*1024 + j] = c[i*1024 + j - 1]
    return max(c)


def calc_lcs1_1(X, Y):
    """
    4/5 ?????????????????????????????¨?????????????????????????????°????????¨??????????????? 7.1?§?
    """
    from array import array
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)
    max_lcs = 0
    C = [array('I', [0] * n) for _ in range(m)]

    pre_row = C[0]
    for i in range(1, m):
        row = C[i]
        XX = X[i]
        for j, YY in enumerate(Y[1:]):
            if XX == YY:
                pr_j1 = pre_row[j-1]
                row[j] = pr_j1 + 1
                if row[j] > max_lcs:
                    max_lcs = pr_j1 + 1
            else:
                pr_j = pre_row[j]
                r_j1 = row[j-1]
                if pr_j >= r_j1:
                    row[j] = pr_j
                else:
                    row[j]= r_j1
        pre_row = row
    return max_lcs


def calc_lcs(X, Y, c):
    """
    ??????????????¢?????´????????????(??????)????????????????£?????????????
    4/5 ?????????????????????????????¨?????????????????????????????°????????¨??????????????? 11.3?§?
    ????????????????????¨????????????????????¢??°??§?¶?????????????????????§?????¢??°???????????????????????????????????????
    """
    m = len(X)
    n = len(Y)
    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
            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 check_max(c)


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    #f = open('input.txt')
    #num = int(f.readline())

    for _ in range(num):
        X = input().strip()
        Y = input().strip()
        #X = f.readline().strip()
        #Y = f.readline().strip()

        # ???????????????
        result = calc_lcs4(X, Y, prep_array(X, Y))

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def lcs(x, y):
    dp = [defaultdict(int) for _ in range(len(x) + 1)]
    dp[0] = [0]*(len(y) + 1)
    for i in range(len(x)):
        for j in range(len(y)):
            if x[i] == y[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])
    return dp[len(x)][len(y)]


N = int(input())
for i in range(N):
    x = input()
    y = input()
    print(lcs(x, y))

Submission status: Runtime Error

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

q = int(input())
t = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    t.append(lcs(s1, s2))
print(*t, sep="\n")

Submission status: Runtime Error

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

q = int(input().rstrip())
t = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    t.append(lcs(s1, s2))
print(*t, sep="\n")

Submission status: Runtime Error

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

q = int(input().rstrip())
t = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    t.append(lcs(s1, s2))
print(*t, sep="\n")

Submission status: Runtime Error

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

q = int(input().rstrip())
t = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    t.append(Ics(s1, s2))
print(*t, sep="\n")

Submission status: Runtime Error

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

q = int(input().rstrip())
t = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    t.append(Ics(s1, s2))
print(*t, sep="\n")

Submission status: Runtime Error

Solution code:
def Ics(X, Y):
    m = len(X)
    n = len(Y)
    c1, c2 = [0] * (n + 1)
    for i in range(m):
        d = X[i]
    for j in range(n):
        if d == Y[j]:
            c1[j+1] = c2[j] + 1
        elif c1[j+1] < c1[j]:
            c1[j+1] = c1[j]
    return c1[-1]

q = int(input().rstrip())
t = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    t.append(Ics(s1, s2))
print(*t, sep="\n")

Submission status: Runtime Error

Solution code:
def Ics(X, Y):
    m = len(X)
    n = len(Y)
    c1 = [0] * (n + 1)
    c2 = [0] * (n + 1)
    for i in range(m):
        d = X[i]
    for j in range(n):
        if (d == Y[j]):
            c1[j + 1] = c2[j] + 1
        elif (c1[j + 1] < c1[j]):
            c1[j + 1] = c1[j]
    return (c1[-1])

q = int(input().rstrip())
t = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    t.append(Ics(s1, s2))
print(*t, sep="\n")

Submission status: Runtime Error

Solution code:
def Ics(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)

    for i in range(a):
        d = x[i]
        c2 = c1[:]
        for j in range(n):
            if d == y[j]:
                c1[j + 1] = c2[j] + 1
            elif c1[j + 1] < c1[j]:
                c1[j + 1] = c1[j]
    return c1[-1]

q = int(input())
for k in range(q):
    x = input()
    y = input()
    print(Ics(x, y))

Submission status: Runtime Error

Solution code:
def Ics(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)

    for i in range(a):
        d = x[i]
        c2 = c1[:]
        for j in range(n):
            if d == y[j]:
                c1[j + 1] = c2[j] + 1
            elif c1[j + 1] < c1[j]:
                c1[j + 1] = c1[j]
    return (c1[-1])

q = int(input().rstrip())
r = []
for k in range(q):
    s1 = input().rstrip()
    s2 = input().rstrip()
    r.append(Ics(s1, s2))

print(*r, sep = "\n")