Go: package main

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

func main() {
	for q := ReadInt(); q > 0; q-- {
		x, y := ReadString(), ReadString()
		fmt.Println(LCS(x, y))
	}
}

func LCS(x, y string) int {
	dp := make([][]int, len(x)+1)
	for i := 0; i < len(x)+1; i++ {
		dp[i] = make([]int, len(y)+1)
	}
	for i := 0; i < len(x); i++ {
		for j := 0; j < len(y); j++ {
			dp[i+1][j+1] = Max(dp[i+1][j], dp[i][j+1])
			if x[i] == y[j] {
				dp[i+1][j+1] = Max(dp[i+1][j+1], dp[i][j]+1)
			}
		}
	}
	return dp[len(x)][len(y)]
}

func Max(xs ...int) int {
	max := xs[0]
	for _, x := range xs[1:] {
		if max < x {
			max = x
		}
	}
	return max
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}

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

import random
import sys
import os
import pprint


def LCS(s0, s1):
    # print(s0)
    # print(s1)
    m = len(s0)
    n = len(s1)

    # memo[i][j]
    memo = [[0] * n for i in range(m)]
    # pprint.pprint(memo)

    # fill at index 0
    index = s0.find(s1[0])
    if index != -1:
        for i in range(index, m):
            memo[i][0] = 1

    index = s1.find(s0[0])
    if index != -1:
        for j in range(index, n):
            memo[0][j] = 1

    """
    for i in range(m):
        if s1[0] in s0[0:i+1]:
            memo[i][0] = 1
    for j in range(n):
        if s0[0] in s1[0:j+1]:
            memo[0][j] = 1
    """

    # fill memo
    for i in range(1, m):
        for j in range(1, n):
            # same last
            if s0[i] == s1[j]:
                memo[i][j] = memo[i-1][j-1] + 1
            else:
                memo[i][j] = max(memo[i-1][j], memo[i][j-1])
    return memo[m-1][n-1]


"""
def LCS_better(s0, s1):
    dp = [0] * len(s1) # cost use till j
    for c in s0:
        tmp = dp[:]
        for j in range(len(s1)):
            if c == s1[j]:
                dp[j + 1] = tmp[j] + 1
            elif dp[j + 1] < dp[j]:
                dp[j + 1] = dp[j]
    return dp[-1]
"""

#fd = os.open('ALDS1_10_C.txt', os.O_RDONLY)
#os.dup2(fd, sys.stdin.fileno())

n = int(input())
for _ in range(n):
    s0 = input()
    s1 = input()
    l = LCS(s0, s1)
    #l2 = LCS_better(s0, s1)
    print(l)

Python: def lcs(x, y):
    L = []
    for y_k in y:
        si = 0
        for i, cri in enumerate(L):
            chi = x.find(y_k, si) + 1
            if not chi:
                break
            L[i] = min(cri, chi)
            si = cri
        else:
            chi = x.find(y_k, si) + 1
            if chi:
                L.append(chi)
    return len(L)


if __name__ == "__main__":
    N = int(input())
    ans = []
    for _ in range(N):
        X = input()
        Y = input()
        print(lcs(X, Y))

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

Python: import sys

def lcm(c,i, j):
    if c[i][j]>0: return c[i][j]        
    if i==0 or j==0:
        return 0
    elif x[i]==y[j]:
        c[i][j] = lcm(c,i-1,j-1)+1
        return c[i][j]
    else:
        c[i][j] = max(lcm(c,i,j-1), lcm(c,i-1,j))
        return c[i][j]

for _ in range(int(sys.stdin.readline())):
    x = sys.stdin.readline()
    y = sys.stdin.readline()
    c = [[0 for _ in range(len(x)+2)] for _ in range(len(y)+2)] 
    print(lcm(c,len(x)-1,len(y)-1))

Python: q = int(input())
ans = []
for _ in range(q):
    x = input()
    y = input()
    m = len(x)
    n = len(y)
    c = [0] * (n + 1)
    for i in range(m):
        tmp = x[i]
        c_ = c[:]
        for j in range(n):
            if tmp == y[j]:
                c[j + 1] = c_[j] + 1
            elif c[j + 1] < c[j]:
                c[j + 1] = c[j]
    ans.append(c[-1])

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