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: Accepted

Solution code:
import bisect


def LCS(S, T):
    N = len(S)
    M = len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]

    for i, s in enumerate(S, start=1):
        for j, t in enumerate(T, start=1):
            if s == t:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[N][M]


def LCS_HTKB(S, T):
    T = T[::-1]
    memo = []

    for s in S:
        i = T.find(s) + 1
        while i:
            j = bisect.bisect_left(memo, -i)
            if j >= len(memo):
                memo.append(-i)
            else:
                memo[j] = -i
            i = T.find(s, i) + 1
    return len(memo)


if __name__ == "__main__":
    Q = int(input())
    ans = []
    for _ in range(Q):
        ans.append(LCS_HTKB(input(), input()))
    print(*ans, sep="\n")

Submission status: Accepted

Solution code:
n = int(input())
import sys

def input():
    return sys.stdin.readline().rstrip()
ans = []
def calc(s1,s2):
    lens1 = len(s1)
    lens2 = len(s2)
    # print(len(s1),s1[-1])
    dp = [0]*(lens2+1)
    for i in range(lens1):
        dp2 = dp[:]
        e = s1[i]
        for j in range(lens2):
            if e == s2[j]:
                dp[j+1] = dp2[j] + 1
            elif dp[j]>dp[j+1]:
                dp[j+1] = dp[j]
    # print(dp)
    ans.append(dp[-1])


for i in range(n):
    s1 = input()
    s2 = input()
    calc(s1,s2)
for i in ans:
    print(i)

# def lcs(x, y):
#     a = len(x)
#     b = len(y)
#     c1 = [0] * (b + 1)
#     for i in range(a):
#         e1 = x[i]
#         c2 = c1[:]
#         for j in range(b):
#             if e1 == 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: Accepted

Solution code:
def LCS(x,y):
    n,m=len(x),len(y)
    DP=[0 for _ in range(m+1)]
    for i in range(n):
        tmp=DP[:]
        num=x[i]
        for j in range(m):
            if num==y[j]:DP[j+1]=tmp[j]+1
            elif DP[j+1]<DP[j]:DP[j+1]=DP[j]
    return DP[-1]


n=int(input())
for _ in range(n):
    print(LCS(input(),input()))

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline

q = int(stdin.readline())

def solve():
    xs = input()
    ys = input()
    len_x = len(xs)-1
    len_y = len(ys)-1
    # [i,j]までで一番長い数値とする
    dp = [0] * (len_x+1)
    memo = [0] * (len_x+1)

    for j in range(len_y):
        yj = ys[j]
        # 参照コピーにならない
        memo = dp[:]
        for i in range(len_x):
            if xs[i] == yj:
                dp[i+1] = memo[i] + 1
            elif dp[i+1] < dp[i]:
                dp[i+1] = dp[i]
    return dp[len_x]


ret = [ solve() for i in range(q)]
print(*ret, sep="\n")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: print('Yes' if b else 'No')
YESNO=lambda b: print('YES' if b else 'NO')

def main():
    Q=int(input())
    for _ in range(Q):
        S=tuple(input())
        T=tuple(input())
        dp=[0]*(len(T)+1)
        for s in S:
            pre=dp[:]
            for i,t in enumerate(T):
                if s==t:
                    dp[i+1]=max(dp[i+1],pre[i]+1)
                elif dp[i+1]<dp[i]:
                    dp[i+1]=dp[i]
        print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def lcs(X,Y):
  L = []
  for yk in Y:
    prev_idx = -1
    for l_idx, l in enumerate(L):
      x_idx = X.find(yk, prev_idx + 1)
      if x_idx < 0:
        break
      L[l_idx] = min(l, x_idx) 
      prev_idx = l
    else:
      x_idx = X.find(yk, prev_idx + 1)
      if x_idx >= 0:
        L.append(x_idx)

  return len(L)

def main():
  q = int(input())
  for _ in range(q):
    X = input()
    Y = input()
    print(lcs(X,Y))

if __name__ == "__main__":
  import sys, io
  main()

Submission status: Accepted

Solution code:
import sys


n = int(input())

def calc(data1, data2):
    term = len(data1)+1
    table = [0]*term

    for i, d2 in enumerate(data2):
        tmp_table = table[:]
        for j, d1 in enumerate(data1):
            if d1 == d2:
                table[j + 1] = tmp_table[j] + 1
            elif table[j+1] < table[j]:
                table[j + 1] = table[j]

    print(table[term-1])
    return 

for _ in range(n):
    data1 = sys.stdin.readline().rstrip()
    data2 = sys.stdin.readline().rstrip()
    calc(data1, data2)

Submission status: Accepted

Solution code:
def longest_common_subseq(S, T):
    if not S and not T: return 0
    len_S, len_T = len(S), len(T)
    dp = [0] * (len_T + 1)
    prev = [0] * (len_T + 1)
    for s in S:
        for j in range(len_T):
            if s == T[j]: dp[j+1] = prev[j] + 1
            elif dp[j] > dp[j+1]: dp[j+1] = dp[j]
        prev = dp[:]
    return dp[len_T]

Q = int(input())
ans = []
for _ in range(Q):
    X = input()
    Y = input()
    ans.append(longest_common_subseq(X, Y))
print(*ans, sep='\n')

Submission status: Accepted

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]


if __name__ == "__main__":
    N = int(input())
    for _ in range(N):
        x = input()
        y = input()
        print(lcs(x, y))

Submission status: Accepted

Solution code:
def lcs_len(X,Y):
    m,n=len(X),len(Y)
    LCS=[0 for _ in range(m+1)]
    for y in Y:
        previous=LCS[:]
        for i,x in enumerate(X):
            if x==y:
                LCS[i+1]=previous[i]+1
            elif LCS[i]>previous[i+1]:
                LCS[i+1]=LCS[i]
    return LCS[-1]

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

Submission status: Accepted

Solution code:
# Longest Common Subsequence

# 関数に入れる
def main():
    # input ← stdin.readline
    import sys
    input = sys.stdin.readline
    for _ in [0]*int(input()):
        # \n削除
        X = '_' + input()[:-1]
        Y = '_' + input()[:-1]

        lx = len(X)
        ly = len(Y)

        dp = [[0]*ly for _ in [0]*lx]

        # 変数に入れておく
        j_y = tuple(enumerate(Y))
        for i, x in enumerate(X):
            if i == 0:
                continue

            # 変数に入れておく
            dp_i = dp[i]
            dp_i1 = dp[i-1]
    
            for j, y in j_y:
                if x == y:
                    dp_i[j] = dp_i1[j-1] + 1
                else:
                    # max(a, b)を書き下す
                    a = dp_i1[j]
                    b = dp_i[j-1]
                    dp_i[j] = a if a > b else b

        print(dp[-1][-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

def longest_common_subsequence(X, Y):
    len_X = len(X)
    len_Y = len(Y)
    c = [0] * len_Y

    for i in range(1, len_X):
        c_ = c[:]

        for j in range(1, len_Y):

            if X[i] == Y[j]:
                c[j] = c_[j - 1] + 1
            elif c_[j] < c[j - 1]:
                c[j] = c[j - 1]
    
    return c[-1]

def Main():
    Q = int(input())

    for q in range(Q):
        X = " " + input()
        Y = " " + input()
        print(longest_common_subsequence(X, Y))

Main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(15000)
n = int(sys.stdin.readline())

def lcs(X,Y):
  n_y = len(Y)
  n_x = len(X)
  #dp = [[0]*(n_x+1) for _ in range(n_y+1)]
  dp = [0]*(n_x+1)
  for i_y in range(n_y):
    ndp = dp.copy()
    for i_x in range(n_x):
      if X[i_x] == Y[i_y]:
        #dp[i_y+1][i_x+1] = dp[i_y][i_x] + 1
        ndp[i_x+1] = dp[i_x] + 1
      elif dp[i_x+1] < ndp[i_x]:
        #dp[i_y+1][i_x+1] = max(dp[i_y+1][i_x],dp[i_y][i_x+1])
        ndp[i_x+1] = ndp[i_x]
    dp = ndp
    #print(dp)
    #return(dp[-1][-1])
  return(dp[-1])

ret = []
inp = sys.stdin.readlines()
for i in range(n):
  X = inp[2*i].rstrip()#[:-1]#input()
  Y = inp[2*i+1].rstrip()#[:-1]#input()
  ret.append(lcs(X,Y))
  #print

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

Submission status: Accepted

Solution code:

def resolve():
    def lcs(s1, s2):
        """
        文字列S, Tのlongest common subsequenceの長さを返す
        なお、longest common substringではない
        （要素同士がとなりあっていなくてもいい）ことに注意！
        """

        dp = []
        for s2_k in s2:
            bgn_idx = 0
            for i, cur_idx in enumerate(dp):
                # bgn_idx以降でs2_kを探す
                chr_idx = s1.find(s2_k, bgn_idx) + 1
                if not chr_idx:
                    break
                dp[i] = min(cur_idx, chr_idx)
                bgn_idx = cur_idx
            else:
                chr_idx = s1.find(s2_k, bgn_idx) + 1
                if chr_idx:
                    dp.append(chr_idx)
        return len(dp)

    q = int(input())
    for i in range(q):
        S = str(input())
        T = str(input())
        print(lcs(S, T))


resolve()

Submission status: Accepted

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


q = int(input())
for _ in range(q):
    s = input()
    t = input()

    info = deque(deque() for _ in range(100))
    check = []
    for i in range(len(s)):
        info[ord(s[i]) - 97].appendleft(i)
    ans = [INF] * (max(len(s), len(t)) + 10)
    link = [0] * (max(len(s), len(t)) + 10)
    for i in t:
        for l in info[ord(i) - 97]:
            ans[bisect_left(ans, l)] = l
    print(bisect_left(ans, INF))

Submission status: Accepted

Solution code:
def lcs(s1, s2):
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if not chr_idx:
                break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if chr_idx:
                dp.append(chr_idx)
    return len(dp)


n = int(input())
for _ in range(n):
    x = input()
    y = input()
    print(lcs(x, y))

Submission status: Accepted

Solution code:
def longest_common(m, n):
	N = len(n)
	dp = [0]*(N+1)
	for x in m:
		dp_kari = dp[:]
		for j, y in enumerate(n):
			if x == y:
				dp[j+1] = dp_kari[j]+1
			elif dp[j+1] < dp[j]:
				dp[j+1] = dp[j]
	return dp[N]


for _ in range(int(input())):
    x = input()
    y = input()
    print(longest_common(x, y))

Submission status: Accepted

Solution code:
def lcs(X, Y):
    a = len(X)
    b = len(Y)
    c1 = [0] * (b + 1)
    for i in range(a):
        e1 = X[i]
        c2 = c1[:]
        for j in range(b):
            if e1 == 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()
    s2 = input()
    ret.append(lcs(s1, s2))
print(*ret, sep = '\n')

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    from sys import stdin
    input = stdin.readline

    N = 1000

    def lcs(X, Y):
        c = [[0]*(N+1) for _ in range(N+1)]
        maxl = 0
        X = ' ' + X # 1オリジンにする
        Y = ' ' + Y
        pre_row = c[0]
        for i, x in enumerate(X):
            if i == 0:
                continue
            row = c[i]
            for j, y in enumerate(Y):
                if j == 0:
                    continue
                if x == y:
                    value = pre_row[j-1] + 1
                    row[j] = value
                    if maxl < value: # maxlの更新はこの時しか起こらない
                        maxl = value
                else:
                    pre_row_j = pre_row[j]
                    row_j_1 = row[j-1]
                    value = row_j_1
                    if pre_row_j > row_j_1:
                        value = pre_row_j # max関数だと、とても遅い
                    row[j] = value
            pre_row = row # 今の列が次の列にとって一つ前の列になる

        return maxl

    n = int(input())
    for _ in range(n):
        s1 = input()[:-1]
        s2 = input()[:-1]
        print(lcs(s1, s2))

Submission status: Accepted

Solution code:
def lcs(s1_raw, s2_raw):
    dp = []
    for s2 in s2_raw:
        start = 0
        for i, cnt in enumerate(dp):
            index = s1_raw.find(s2, start) + 1
            if not index:
                break
            else:
                dp[i]  = min(cnt , index)
                start = cnt
        index = s1_raw.find(s2, start) + 1
        if index:
            dp.append(index)
    return len(dp)


if __name__ == "__main__":
    q = int(input())
    for _ in range(q):
        x = input()
        y = input()
        print(lcs(x, y))

Submission status: Accepted

Solution code:

def main():
    Q = int(input())
    XY = []
    for i in range(Q):
        X = input()
        Y = input()
        XY.append((X,Y))
    for X,Y in XY:
        
        LX,LY = len(X), len(Y)
        dp = [0 for _ in range(LY+1)]

        for i in range(LX):
            ex = dp[:]
            for j in range(LY):
                if X[i] == Y[j]:
                    dp[j+1] = ex[j] + 1
                elif dp[j+1] < dp[j]:
                    dp[j+1] = dp[j]
        print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def lcs(x, y):
    ans = [[0]*(len(y)+1) for _ in range(len(x)+1)]
    for i, cx in enumerate(x, 1):
        ao = ans[i-1]
        old = ans[i][0]
        for j, cy in enumerate(y, 1):
            if cx == cy:
                old = ao[j-1] + 1
            else:
                a1, a2 = old, ao[j]
                old = a1 if a1 > a2 else a2
            ans[i][j] = old
    return ans[-1][-1]

def main():
    n = int(input())
    a = []
    for _ in range(n):
        X = input()
        Y = input()
        a.append(lcs(X, Y))
    print('\n'.join(list(map(str, a))))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def lcs(s1, s2):
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if not chr_idx:
                break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if chr_idx:
                dp.append(chr_idx)
    return len(dp)

q = INT()

for _ in range(q):
	S = input()
	T = input()
	print(lcs(S, T))

Submission status: Accepted

Solution code:
def lcs(s1, s2):
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if not chr_idx:
                break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if chr_idx:
                dp.append(chr_idx)
    return len(dp)

n = int(input())
ans = []
for _ in range(n):
    x = input()
    y = input()
    ans.append(lcs(x, y))

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
"""
ALDS1_10_C
最長共通部分列を二次元配列を用いた動的計画法で求める
だた，普通に二次元配列を構成するとTLEになるので工夫しなければならない
IKAPPERさんのコードを参考にしました
"""

def lcs(X, Y):
    m = len(X)
    n = len(Y)
    #xが縦，yが横
    lcs_r = [0 for _ in range(m+1)]
    for y in Y:
        previous = lcs_r[:] #copy.copy 使わなくて済むかも
        for i, x in enumerate(X):
            if x == y:
                lcs_r[i+1] = previous[i]+1
            elif lcs_r[i] > previous[i]:
                lcs_r[i+1] = lcs_r[i]
            else: #ここは省略できる（そのままpreviousがlcs_rに上がってくる）
                lcs_r[i] = previous[i] 
    
    print(lcs_r[-1])



roop = int(input())
for _ in range(roop):
    x = input()
    y = input()
    lcs(x, y)

Submission status: Accepted

Solution code:
# ライブラリのインポート
#import re #正規表現
import sys
#import heapq
#import collections
#import math

def main():
    q = int(input())
    STR = [str.strip("\n") for str in sys.stdin]
    for i in range(q):
        x = STR[2*i]
        y = STR[2*i+1]
        print(lcs(x,y))


def lcs(x, y):
    dp = []
    for y_k in y:
        ps = 0
        for i, pdp in enumerate(dp):
            p = x.find(y_k, ps) + 1 #.find method returns -1 if there is no element
            if not p: break
            dp[i] = min(p,pdp)
            ps = pdp
        else: #else block is executed when for block has done completedly
            p = x.find(y_k, ps) + 1
            if p: dp.append(p)
    return len(dp)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def length_of_lcs(x, y):
    n = len(y)
    #pre_row = [0] * (n + 1)
    cur_row = [0] * (n + 1)
    for x_c in x:
        prev_row = cur_row[:]
        for j, y_c in enumerate(y):
            if x_c == y_c:
                cur_row[j+1] = prev_row[j] + 1
            elif cur_row[j] > cur_row[j+1]:
                cur_row[j+1] = cur_row[j]

    return cur_row[n]


if __name__ == '__main__':
    N = int(input())
    for _ in range(N):
        x = input()
        y = input()
        print(length_of_lcs(x, y))

Submission status: Accepted

Solution code:
def lcs(s1, s2):

    dp = []

    for s2_k in s2:

        bgn_idx = 0

        for i, cur_idx in enumerate(dp):

            chr_idx = s1.find(s2_k, bgn_idx) + 1

            if not chr_idx:

                break

            dp[i] = min(cur_idx, chr_idx)

            bgn_idx = cur_idx

        else:

            chr_idx = s1.find(s2_k, bgn_idx) + 1

            if chr_idx:

                dp.append(chr_idx)

    return len(dp)



def solve():

    N = int(input())

    for _ in range(N):

        x = input()

        y = input()

        print(lcs(x, y))



if __name__ == '__main__':

    solve()

Submission status: Accepted

Solution code:
for i in range(int(input())):
    x = input()
    y = input()
    a=[0]
    for i in x:
        for j in range(len(a) - 1, -1, -1):
            b = y.find(i, a[j]) + 1
            if b:
                if j + 1 < len(a):
                    a[j + 1] = min(a[j + 1], b)
                else:
                    a.append(b)
    print(len(a)-1)

Submission status: Accepted

Solution code:
q = int(input())
for i in range(q):
    x = input()
    y = input()
    co = []

    for j, s in enumerate(x):
        co.append([])
        co[j].append(-1)
        if j == 0:
            end = y.find(s)
            if end != -1:
                co[j].append(end)
        else:
            for k, t in enumerate(co[j-1][:-1]):
                end = y.find(s, t+1)
                if end != -1:
                    co[j].append(min(end, co[j-1][k+1]))
                else:
                    co[j].append(co[j-1][k+1])
            end = y.find(s, co[j-1][-1]+1)

            if end != -1:
                co[j].append(end)

    print(len(co[-1])-1)

Submission status: Accepted

Solution code:
def common(x, y):
    n = len(x)
    m = len(y)
    c1 = [0 for i in range(m + 1)]
    for i in range(n):
        e1 = x[i]
        c2 = c1[:]
        for j in range(m):
            if (e1 == 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())
for i in range(n):
    x = str(input())
    y = str(input())
    print(common(x, y))

Submission status: Accepted

Solution code:
def lcs(x, y):

    l1, l2 = len(x), len(y)

    dp = [0] * (l2+1)
    #dp = [[0]*(l2+1) for i in range(l1+1)]

    for i in range(l1):
        prev = dp[:]
        for j in range(l2):
            if x[i] == y[j]:
                dp[j+1] = prev[j] + 1
                #dp[i+1][j+1] = dp[i][j] + 1   
            elif dp[j+1] < dp[j]:
                dp[j+1] = dp[j]
    
    return dp[l2]

N = int(input())
ans = []
for i in range(N):
    x = input()
    y = input()
    ans.append(lcs(x,y))
for i in range(N):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys

def LCS():
    str1=input()
    str2=input()

    l=len(str1)
    m=len(str2)
    x1=[0 for i in range(m+1)]
    for i in range(l):
        e1=str1[i]
        x2=x1+[]
        for j in range(m):
            if e1 == str2[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1]<x1[j]:
                x1[j+1] = x1[j]
    return x1[-1]

n = int(input())
for i in range(n):
    
    print(LCS())

Submission status: Accepted

Solution code:
def lcs(X,Y):
    res = [0 for i in range(len(X)+1)]
    for y in Y:
        previous = res[:]
        for i,x in enumerate(X):
            if x == y:
                res[i+1] = previous[i] + 1
            elif res[i] > previous[i+1]:
                res[i+1] = res[i]
    return res[-1]

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

Submission status: Accepted

Solution code:
def main(X, Y):
    M = len(Y)
    dp = [0]*(M+1)
    for i, x in enumerate(X):
        dp_pre = dp[:]
        for j, y in enumerate(Y):
            if x == y:
                dp[j+1] = dp_pre[j] + 1
            elif dp[j+1] < dp[j]:
                dp[j+1] = dp[j]
    return print(dp[M])


for _ in range(int(input())):
    X = input()
    Y = input()
    main(X, Y)

Submission status: Accepted

Solution code:
def lcs(m,n):
	N=len(n)
	dp=[0]*(N+1)
	for x in m:
		dp_kari=dp[:]
		for j, y in enumerate(n):
			if x==y:
				dp[j+1]=dp_kari[j]+1
			elif dp[j+1]<dp[j]:
				dp[j+1]=dp[j]
	return dp[N]
import sys
for _ in range(int(input())):
	m=sys.stdin.readline().rstrip()
	n=sys.stdin.readline().rstrip()
	print(lcs(m,n))

Submission status: Accepted

Solution code:
def lcs_fast(x, y):
    len_x = len(x)
    len_y = len(y)

    c = [0] * (len_y + 1)
    for i in range(len_x):
        c_prev = c[:]
        for j in range(len_y):
            if x[i] == y[j]:
                c[j+1] = c_prev[j] + 1
            elif c[j+1] < c[j]:
                c[j+1] = c[j]
    return c[-1]


if __name__ == "__main__":
    n = int(input())
    for i in range(n):
        x = input()
        y = input()
        # print(lcs(x, y))
        print(lcs_fast(x, y))

Submission status: Accepted

Solution code:
def lcs(str1, str2):
    lcslist = []
    for s in str2:
        m = n = 0
        for index in lcslist:
            t = str1.find(s, m) + 1
            if t <= 0:
                break
            elif t < index:
                lcslist[n] = t
            m = index
            n += 1
        else:
            t = str1.find(s, m) + 1
            if t > 0:
                lcslist.append(t)
    return len(lcslist)

if __name__ == '__main__':
    n = int(input())
    for i in range(n):
        str1 = input()
        str2 = input()
        print(lcs(str1, str2))

Submission status: Accepted

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

最長共通部分列
"""


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(Y)+2) for _ in range(len(X)+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


if __name__ == '__main__':
    # データの入力
    num = int(input())
    #f = open('input.txt')
    #num = int(f.readline())

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

        # 処理の実行
        result = calc_lcs4(X, Y, prep_array(X, Y))

        # 結果の表示
        print(result)

Submission status: Accepted

Solution code:
def lcs(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)
    for i in range(a):
        e1 = x[i]
        c2 = c1[:]
        for j in range(b):
            if e1 == 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: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    Q=I()
    for _ in range(Q):
        S=ST()
        T=ST()[::-1]
        lis = []
        find, append = T.find, lis.append

        for c in S:
            i = find(c)+1
            while i:
                j = bisect_left(lis, -i)
                if j >= len(lis):
                    append(-i)
                else:
                    lis[j] = -i
                i = find(c, i)+1
        print(len(lis))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def lcs(X, Y):
	m = len(X)
	n = len(Y)
	c = [0 for i in range(n+1)]
	for i in range(m):
		pre_c = c[:]
		XX = X[i]
		for j in range(n):
			if XX == Y[j]:
				c[j+1] = pre_c[j] + 1
			elif c[j + 1] < c[j]:
				c[j+1] = c[j]
	return c[-1]

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

Submission status: Accepted

Solution code:
for i in range(int(input())):
    s=input()
    t=input()
    a=[0]
    for i in s:
        for j in range(len(a)-1,-1,-1):
            b=t.find(i,a[j])+1
            if b:
                if j+1<len(a):
                    a[j+1]=min(a[j+1],b)
                else:
                    a.append(b)
    print(len(a)-1)

Submission status: Accepted

Solution code:
def lcs(X, Y):
    dp = []
    for y in Y:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = X.find(y, bgn_idx) + 1
            
            if not chr_idx:
                break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = X.find(y, bgn_idx) + 1
            if chr_idx:
                dp.append(chr_idx)
    return len(dp)

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

Submission status: Accepted

Solution code:
from typing import List


def compute_lcs(x_str: str, y_str: str) -> int:
    if len(x_str) <= len(y_str):
        shorter_str, longer_str = x_str, y_str
    else:
        shorter_str, longer_str = y_str, x_str

    lcs_idx: List[int] = []
    for s_ch in shorter_str:
        l_bgn_idx = 0
        for i, l_cur_idx in enumerate(lcs_idx):
            l_idx = longer_str.find(s_ch, l_bgn_idx)
            if -1 == l_idx:
                break
            lcs_idx[i] = min(l_cur_idx, l_idx)
            l_bgn_idx = l_cur_idx + 1  # Move to the next ch.
        l_idx = longer_str.find(s_ch, l_bgn_idx)
        if -1 != l_idx:
            lcs_idx.append(l_idx)
    return len(lcs_idx)


if __name__ == "__main__":
    num_pairs = int(input())

    for _ in range(num_pairs):
        x_str = input()
        y_str = input()
        lcs = compute_lcs(x_str, y_str)
        print(f"{lcs}")