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: def lcs(list1,list2):
    f=[[0 for x in range(len(list1)+1)]for y in range(len(list2)+1)]#表の確保

    for j in range(len(list1)):
        if list1[j]==list2[0]:
            f[j][0]=1
    for j in range(len(list2)):
        if list1[0]==list2[j]:
            f[0][j]=1
            
    for j in range(1,len(list1)):
        for k in range(1,len(list2)):
            if list1[j]==list2[k]:
                f[j][k]=f[j-1][k-1]+1
            else:
                f[j][k]=max(f[j-1][k],f[j][k-1])

    print(f[len(list1)-1][len(list2)-1])



n=int(input())
l=[]

for i in range(n*2):
    str=input()
    l+=[list(str)]
l[0].pop()

i=0
while True:#(文字列の数/2)回繰り返す
    if i>2*n-2:
        break
    lcs(l[i],l[i+1])
    i+=2

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

????????±?????¨??????
"""
import sys
from sys import stdin
input = stdin.readline



def calc_lcs4(X, Y):
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)

    C = [[0]*(n) for _ in range(m)] #  ???????????§??¨???

    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

    print(max_lcs)


if __name__ == '__main__':
    num = int(input())

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

        result = calc_lcs4(X, Y)

Python: #!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys
sys.setrecursionlimit(int(1e5))


def lcs(A, B):
    m, n = len(A), len(B)
    count_list = tuple([[0] * (n + 1) for _ in range(m + 1)])

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                count_list[i][j] = count_list[i - 1][j - 1] + 1
            else:
                count_list[i][j] = max(count_list[i - 1][j], count_list[i][j - 1])

    return count_list[m][n]


def lcs_recursive(A, B, m, n):
    if m == 0 or n == 0:
        return 0
    elif A[m - 1] == B[n - 1]:
        return 1 + lcs_recursive(A, B, m - 1, n - 1)
    else:
        return max(lcs_recursive(A, B, m, n - 1), lcs_recursive(A, B, m - 1, n))


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num
    # for k in range(0, len(word_list), 2):
    #     print(lcs(word_list[k].strip(), word_list[k + 1].strip()))

    for pair in zip(word_list[::2], word_list[1::2]):
        w1, w2 = map(lambda x: x.strip(), pair)
        l1, l2 = len(w1), len(w2)
        print(lcs_recursive(w1, w2, l1, l2))

Python: import sys
def lcs(X, Y):
    c = [0 for _ in range(len(Y) + 1)]

    for i in X:
        tmp = c[:]
        for ji, yc in enumerate(Y):
            j = ji + 1
            if i == yc:
                c[j] = tmp[j - 1] + 1
            else:
                c[j] = max(tmp[j], c[j - 1])
    return c[-1]

n = int(input())

for i in range(n):
    X = sys.stdin.readline()[:-1]
    Y = sys.stdin.readline()[:-1]
    print(lcs(X, Y))