Go: package main

import (
	. "fmt"
    "math"
)

// func init() { Println("----------------------------------------") }

func main() {
    const L_MAX = 1003

	var q int
	Scanf("%d", &q)
	X := make([]string, 0, 150)
	Y := make([]string, 0, 150)
	for i := 0; i < 2 * q; i++ {
	    var tmp string
	    Scanf("%s", &tmp)

	    if i % 2 == 0 {
	        X = append(X, tmp)
	    } else {
	        Y = append(Y, tmp)
	    }
	}

    for i := 0; i < q; i++ {
        dp := make([][]int, L_MAX)
        for k, _ := range dp {
            dp[k] = make([]int, L_MAX)
        }

        x, y := X[i], Y[i]

        // init
        isXFound := false
        for c := 0; c < len(x); c++ {
            if isXFound || y[0] == x[c] {
                dp[0][c] = 1
                isXFound = true
            }
        }
        isYFound := false
        for r := 0; r < len(y); r++ {
            if isYFound || x[0] == y[r] {
                dp[r][0] = 1
                isYFound = true
            }
        }

        for r := 1; r < len(y); r++ {
            for c := 1; c < len(x); c++ {
                // dp[r][c]
                if x[c] == y[r] {
                    dp[r][c] = int(math.Max(float64(dp[r - 1][c - 1] + 1), float64(dp[r][c])))
                }

                dp[r][c] = int(math.Max(float64(dp[r][c]), math.Max(float64(dp[r - 1][c]), float64(dp[r][c - 1]))))
            }
        }
        Println(dp[len(y) - 1][len(x) - 1])

        // LCSも求めておく
        // ans := ""
        // r, c := len(y) - 1, len(x) - 1
        // for r >= 0 && c >= 0 {
        //     if y[r] == x[c] {
        //         ans = string(x[c]) + ans
        //         r--
        //         c--
        //     } else {
        //         if dp[r - 1][c] > dp[r][c - 1] {
        //             r--
        //         } else {
        //             c--
        //         }
        //     }
        // }
        // Println(ans)
    }
}

Python: # -*- coding: utf-8 -*-


def lcs(X, Y):
    memo = dict()
    for i in range(len(X)+1):
        memo[(i, 0)] = 0
    for j in range(len(Y)+1):
        memo[(0, j)] = 0
    for i, x in enumerate(X):
        for j, y in enumerate(Y):
            if x == y:
                memo[(i+1,j+1)] = memo[i, j] + 1
            else:
                memo[(i+1,j+1)] = max(memo[i, j+1], memo[i+1, j])
    return memo[(len(X), len(Y))]


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

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