Go: package main

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

const max int = 1000 + 1
var A [][]int

func lcs(x, y string) int {
	x = " " + x
	y = " " + y
	for i:=0;i<len(x); i++ {
		for j:=0;j<len(y); j++ {
			A[i][j] = 0
		}
	}
	for i:=1; i<len(x); i++ {
		for j:=1; j<len(y); j++ {
			if x[i] == y[j] {
				A[i][j] = A[i-1][j-1] + 1
			} else if A[i-1][j] > A[i][j-1] {
				A[i][j] = A[i-1][j]
			} else {
				A[i][j] = A[i][j-1]
			}
		}
	}
	return A[len(x)-1][len(y)-1]
}

func nextInt(scanner *bufio.Scanner) int {
	scanner.Scan()
	num, _ := strconv.Atoi(scanner.Text())
	return num 
}

func nextStr(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}


func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	A = make([][]int, max)
	for i := range A {
		A[i] = make([]int, max)
	}
	n := nextInt(scanner)
	for i:=0; i<n; i++ {
		x := nextStr(scanner)
		y := nextStr(scanner)
		fmt.Printf("%d\n", lcs(x, y))
	}
}

Python: def lcs(X,Y,p,q,Z):
    for i in range(p):
        for j in range(q):
            if X[i]==Y[j]:
                Z[i+1][j+1]=Z[i][j]+1
            else:
                if Z[i][j+1]>Z[i+1][j]:
                    Z[i+1][j+1]=Z[i][j+1]
                else:
                    Z[i+1][j+1]=Z[i+1][j]
    print(Z[p][q])

n=int(input())
for i in range(n):
    X=input()
    Y=input()
    p=len(X)
    q=len(Y)
    Z=[[0 for i in range(q+1)]for j in range(p+1)]
    lcs(X,Y,p,q,Z)

Python: n=int(input())
al=[]
bl=[]
for i in range(n):
	al.append(list(input()))
	bl.append(list(input()))

for i in range(n):
	a=al.pop(0)
	b=bl.pop(0)
	dp=[[0 for i in range(len(b))] for j in range(len(a))]

	for i in range(len(a)):
		for j in range(len(b)):
			if i==0:
				if j==0:
					if a[i]==b[j]:
						dp[i][j]=1
					else:
						dp[i][j]=0
				elif a[i]==b[j]:
					dp[i][j]=1
				else:
					dp[i][j]=dp[i][j-1]
			elif j==0:
				if a[i]==b[j]:
					dp[i][j]=1
				else:
					dp[i][j]=dp[i-1][j]

			elif a[i]!=b[j]:
				dp[i][j]=max(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])
			else:
				dp[i][j]=dp[i-1][j-1]+1

	print(dp[len(a)-1][len(b)-1])

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

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

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

c = []
def prep_array(X, Y):
    """ ??????0???2?¬???????????????¨??????????????????????????\????????????????????§??????????????????????¨?(1000+1)??\???????????? """
    c = [[0]*1001 for _ in range(1001)]
    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 ?????????????????????????????¨????????????????????????????????°??§6.0?§?
    """
    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]
                cv = pr_j1 + 1
                row[j] = cv
                if cv > max_lcs:
                    max_lcs = cv
            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?????????????????????????????°????????????????????§???
    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_lcs1(X, Y):
    """
    array?????????????????¨???byte???????????¨????????¨????§??????????????????????????????????????????§?????¨???????????£?????????int???????????¨???
    4/5 ?????????????????????????????¨????????????????????????????????°??§19.3?§?
    """
    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_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))
        # result = calc_lcs5(X, Y)

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

Python: n=int(input())

for i in range(n):
    a=list(input())
    b=list(input())
    x=len(a)+1
    y=len(b)+1

    r=[[0 for j in range(y)]for i in range(x)]

    for j in range(1,x):
        for k in range(1,y):
            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[x-1][y-1])

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