Go: package main

import (
	"bufio"
	"os"
	"strconv"
	"fmt"
)

func max(x, y int) int {
	if x < y {
		return y
	} else {
		return x
	}
}

/*********************************************************************
長さmの列X_(m)と長さnの列Y_(n)の最長共通部分列LCSは、
	(1)X[m] == Y[n]ならば、X_(m-1)とY_(n-1)のLCSにX[m]を繋げたもの
	(2)X[m] != Y[n]ならば、X_(m-1)とY_(n)のLCSもしくはX_(m)とY_(n-1)のLCS
	のいずれかのうち長い方

c[m+1][n+1]：c[i][j]にX_(i)とY_(j)のLCSの長さを格納する二次元配列
*********************************************************************/

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	n, _ := strconv.Atoi(scanner.Text())
	for i := 0; i < n; i++ {
		scanner.Scan()
		s1 := scanner.Text()
		scanner.Scan()
		s2 := scanner.Text()
		s1, s2 = s1 + " ", s2 + " "
		c := make([][]int, len(s1))
		for i := range c {
			c[i] = make([]int, len(s2))
		}

		LCS := 0

		for i := 1; i < len(s1); i++ {
			for j := 1; j < len(s2); j++ {
				if s1[i] == s2[j] {
					c[i][j] = c[i-1][j-1] + 1
				} else {
					c[i][j] = max(c[i-1][j], c[i][j-1])
				}
				LCS = max(LCS, c[i][j])
			}
		}
		fmt.Println(LCS)
	}
}

Python: ans=[]
n=int(input("n="))
for i in range(n):
    X=input("X=")
    Y=input("Y=")
    com=[0]
    for i in X:
        for j in range(len(com)-1,-1,-1):
            tmp=X.find(i,com[j])+1
            if tmp:
                if j+1<len(com):
                    com[j+1]=min(com[j+1],tmp)
                else:
                    com.append(tmp)     
    ans.append(len(com)-1)
for i in range(n):
    print(ans[i])

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

????????±?????¨??????
"""
# 3/5??§Time Limit Exceeded 14.27s ????????????5s??\???????????????????????????

def calc_lcs(X, Y):
    from array import array
    max_lcs = 0
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y
    c = array('l', [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())
    # 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)

Python: import sys
import functools as ft
sys.setrecursionlimit(10000)

q = int(input())
X = ""
Y = ""
memo = [[]]

def print_memo() :
    for x in range(len(X)):
        print(ft.reduce(lambda x,y: x + str(y) + "\t" ,memo[x], ""))

def LCS(x, y):
    if (x < 0) or (y < 0):
        return 0
    elif memo[x][y] != -1:
        return memo[x][y]
    elif X[x] == Y[y]:
        memo[x][y] =  LCS(x-1, y-1) + 1
        return memo[x][y]
    else:
        memo[x][y] = max(LCS(x-1,y), LCS(x,y-1))
        return memo[x][y]


for c in range(q):
    X = input()
    Y = input()
    memo = [[-1 for j in range(len(Y))] for i in range(len(X))]
    print(LCS(len(X)-1, len(Y)-1))
    #print_memo()

Python: def lcs(x, y):
    m, n = len(x), len(y)
    dp = [[0 for j in range(n+1)] for i 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]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])

    return dp[m][n]


def main():
    q = int(input())

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


if __name__ == '__main__':
    main()

Python: 
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())

Python: def len_LCS(X,Y):
    D = {}
    def main(X,Y):
        if len(X) == 0: return 0
        if (X,Y) in D: return D[(X,Y)]
        if len(X) == 1:
            D[(X,Y)] = 1 if X[0] in Y else 0
        elif X[0] in Y:
            if Y.index(X[0]) == len(Y)-1:
                D[(X,Y)] = max(1,main(X[1:],Y[:])) 
            else: 
                D[(X,Y)]=  max(main(X[1:],Y[Y.index(X[0])+1:]) + 1,\
                               main(X[1:],Y[:]))
        else:
             D[(X,Y)] = main(X[1:],Y[:]) 
        return D[(X,Y)]
    return main(X,Y)
        
if __name__=='__main__':
    n = int(input())
    for _ in range(n):
        X = input()
        Y = input()
        print(len_LCS(X,Y))

Python: 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)

if __name__ == '__main__':
    main()

Python: for _ in range(int(input())):
    X, Y = input(), input()
    X_len = len(X)
    Y_len = len(Y)
    dp = [[0] * (Y_len+1) for x in range(X_len+1)]
    for x in range(1, X_len + 1):
        pre = dp[x-1]
        tmp = dp[x]
        for y in range(1, Y_len + 1):
            if X[x-1] == Y[y-1]:
                tmp[y] = pre[y-1] + 1
            else:
                tmp[y] = max(tmp[y-1], pre[y])
    print(dp[-1][-1])

Python: n=int(input())

for i in range(n):
    a=list(input())
    b=list(input())

    r=[[0 for j in range(len(b)+1)]for i in range(len(a)+1)]

    for j in range(1,len(a)+1):
        for k in range(1,len(b)+1):
            c=max(r[j-1][k-1],r[j-1][k],r[j][k-1])
            if a[j-1]==b[k-1]:
                c=max(r[j-1][k-1]+1,r[j-1][k],r[j][k-1])
            
            r[j][k]=c
  
    
    print(r[len(a)][len(b)])

Python: # -*- coding: utf-8 -*-
import numpy as np

def lcs_sol(x, y):
    n = len(x)
    m = len(y)
    dp = np.zeros((n + 1) * (m + 1)).reshape(n + 1, m + 1)

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

    return dp[n][m]


if __name__ == '__main__':
    import sys
    q = int(sys.stdin.readline().strip())
    for i in range(q):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print(lcs_sol(x, y))

Python: 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))