Go: package main

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

// define
var (
	sc = bufio.NewScanner(os.Stdin)
)

func bordersInt(in_map [][]int, invalid int) [][]int{
	H, W := len(in_map), len(in_map[0])
	out_map := make([][]int, H+2)
	for h:=0; h<H+2; h++ {
		out_map[h] = make([]int, W+2)
		for w:=0; w<W+2; w++ {
			out_map[h][w] = invalid
		}
	}
	for h:=0; h<H; h++{
		for w:=0; w<W; w++{
			out_map[h+1][w+1] = in_map[h][w] 
		}
	}
	return out_map
}

func bordersString(in_map [][]string, invalid string) [][]string{
	H, W := len(in_map), len(in_map[0])
	out_map := make([][]string, H+2)
	for h:=0; h<H+2; h++ {
		out_map[h] = make([]string, W+2)
		for w:=0; w<W+2; w++ {
			out_map[h][w] = invalid
		}
	}
	for h:=0; h<H; h++{
		for w:=0; w<W; w++{
			out_map[h+1][w+1] = in_map[h][w] 
		}
	}
	return out_map
}

func scanIntLine(len int) []int{
	arr := make([]int, len)
	for i:=0; i<len; i++{
		sc.Scan()
		tmp, err := strconv.Atoi(sc.Text())
		if err == nil{
			arr[i] = tmp
		}
	}
	return arr
}

func scanStringLine(len int) []string{
	arr := make([]string, len)
	for i:=0; i<len; i++{
		sc.Scan()
		arr[i] = sc.Text()
	}
	return arr
}

func scanIntSplit(len int) []int{
	arr := make([]int, len)
	sc.Scan()
	for i, v := range strings.Split(sc.Text(), " "){
		tmp, err := strconv.Atoi(v)
		if err == nil{
			arr[i] = tmp
		}
	}
	return arr
}

func maxInt(args... int) int{
	sort.Ints(args)
	return args[len(args)-1]
}

func main(){
	buf := make([]byte, 0)
    sc.Buffer(buf, 1000000009)
	var n int 
	fmt.Scan(&n)
	dp := make([][]int, 1003)
	for i:=0; i<1003; i++ {
		dp[i] = make([]int, 1003)
	}
	input_lines := scanStringLine(2*n)
	for i:=0; i<n; i++ {
		S, T := input_lines[2*i], input_lines[2*i+1]
		lenS, lenT := len(S), len(T)
		for i:=1; i<lenS+1; i++ {
			for j:=1; j<lenT+1; j++ {
				if S[i-1] == T[j-1] {
					dp[i][j] = dp[i-1][j-1]+1
				} else if S[i-1] != T[j-1] && dp[i-1][j] > dp[i][j-1] {
					dp[i][j] = dp[i-1][j]
				} else {
					dp[i][j] = dp[i][j-1]
				}
				// if S[i-1] == T[j-1] {
				// 	dp[i][j] = maxInt(dp[i-1][j-1]+1, dp[i-1][j], dp[i][j-1])
				// } else {
				// 	dp[i][j] = maxInt(dp[i-1][j], dp[i][j-1])
				// }
			}
		}
		fmt.Println(dp[lenS][lenT])
	}
}

Python: def edit_distance(s, t):
 s = raw_input()
 t = raw_input()
 dp = {}
 for i in range(len(s) + 1):
  dp[i] = {0: i}
 for j in range(len(t) + 1):
  dp[0][j] = j
 for i in range(1, len(s) + 1):
  for j in range(1, len(t) + 1):
   if (s[i-1] == t[j-1]): 
    d = 0
   else:
    dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + d)
 return dp[len(s)][len(t)]
n = input()

Python: for _ in[0]*int(input()):
 X,Y,z=input(),input(),[]
 for y in Y:
  s=0
  for i,k in enumerate(z):
   t=X.find(y,s)+1
   if t<1:break
   if t<k:z[i]=t
   s=k
  else:
   t=X.find(y,s)+1
   if t:z+=[t]
 print(len(z))

Python: # dpテーブル生成
def gen_dp(row, col):
  print('row: {}'.format(row))
  print('col: {}'.format(col))
  print('----------')
  return [[0]*col for i in range(row)]
#dpテーブル表示
def show_dp(table):
  for line in range(len(table)):
    print(table[line])
  print('----------')

def solver(str_1 ,str_2):
  # テーブル生成
  dp = gen_dp(len(str_2) + 1, len(str_1) + 1)
  for r in range(len(str_2)):
    for c in range(len(str_1)):
      print('[str_2]:{}, [str_1]:{}'.format(r + 1, c + 1))
      # 末尾の文字が一致していれば
      if str_2[r] == str_1[c]:
        dp[r + 1][c + 1] = dp[r][c] + 1
      # 末尾の文字が違えば
      else:
        dp[r + 1][c + 1] = max(dp[r + 1][c], dp[r][c + 1])
      show_dp(dp)
  return dp[len(str_2)][len(str_1)]

# 実行
n = int(input())
for _ in range(n):
  str_1 = input()
  str_2 = input()
  print(solver(str_1, str_2))

Python: i=input
for _ in[0]*int(i()):
 X,z=i(),[]
 for y in i():
  s=i=0
  for k in z:
   t=X.find(y,s)+1
   if t<1:break
   if t<k:z[i]=t
   s=k;i+=1
  else:
   t=X.find(y,s)+1
   if t:z+=[t]
 print(len(z))

Python: def gen_dp(row, col):
  return [[0]*col for i in range(row)]

def solver(str_1 ,str_2):
  dp = gen_dp(len(str_2) + 1, len(str_1) + 1)
  for r in range(len(str_2)):
    for c in range(len(str_1)):
      if str_2[r] == str_1[c]:
        dp[r + 1][c + 1] = dp[r][c] + 1
      else:
        dp[r + 1][c + 1] = max(dp[r + 1][c], dp[r][c + 1])
  return dp[len(str_2)][len(str_1)]

n = int(input())
for _ in range(n):
  str_1 = input()
  str_2 = input()
  print(solver(str_1, str_2))

Python: q = int(input())
 
def lcss(x,y):
     
    lcs = [0]*(len(x)+1)
    for i in range(len(y)):
        w1 = y[i]
        lcs_2 = lcs[:]
        for j in range(len(x)):
            if x[j] == w1:
                lcs[j+1] = lcs_2[j] + 1  
            elif lcs[j+1] < lcs[j]:
                lcs[j+1] = lcs[j]
    return lcs[-1]
 
for i in range(q):
    x = input()
    y = input()
    print(lcss(x,y))

Python: def main():
    n=int(input())
    result=[]
    for i in range(n):
        a=input()
        b=input()
        array=[[1 for i in range(len(a))] for j in range(len(b))]
        for i in range(1,len(a)):
            for j in range(1,len(b)):
                c=0
                if a[j] == b[i]:
                    c=1
                array[i][j]=max(array[i-1][j],array[i][j-1],array[i-1][j-1]+c)
        result.append(array[len(a)-1][len(b)-1])
    for i in result:
        print(i)
if __name__ == "__main__":
    main()

Python: pcsl = [[0] * 1001] * 1001

def lcs(x, y):
    m = len(x)
    n = len(y)
    for i in range(m):
        for j in range(n):
            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)

Python: def num_substr(s, t):
    dp = {}
    for i in range(len(s) + 1):
        dp[i] = {0: 0}
    for j in range(len(t) + 1):
        dp[0][j] = 0
    
    for i in range(1,len(s)+1):
        Flag=False
        for j in range(1,len(t)+1):
            d=1 if s[i-1] == t[j-1] and dp[i-1][j-1] == dp[i][j-1] else 0
            dp[i][j] = max(dp[i-1][j] ,
                           dp[i][j-1] +d)
    return dp[len(s)][len(t)]

n = int(input())
for i in range(n):
    s = input()
    t = input()
    print(num_substr(s,t))

Python: # Longest Common Subsequence problem: LCS
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/10/ALDS1_10_C

import sys
input = sys.stdin.readline
ascii_letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'


def get_LCS(x: str, y: str):
    lx = len(x)
    ly = len(y)
    dp = [[0] * (lx + 1) for _ in range(ly + 1)]  # 1-indexed

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

    return dp[-1][-1]


def llcs(x, y):
    """solution author: bs5lNkJ"""
    pm = dict((zip(ascii_letters, [0] * 52)))
    for c in pm:
        for i, xc in enumerate(x):
            if c == xc:
                pm[c] |= (1 << i)

    V = (1 << len(x)) - 1

    for yc in y:
        V = ((V + (V & pm[yc])) | (V & ~pm[yc]))

    ans = bin(V)[-len(x):].count('0')

    return ans


n = int(input())

for _ in range(n):
    X = input().strip()
    Y = input().strip()
    print(llcs(X, Y))

Python: for _ in[0]*int(input()):
 X,Y,z=input(),input(),[]
 for y in Y:
  s=i=0
  for k in z:
   t=X.find(y,s)+1
   if t<1:break
   if t<k:z[i]=t
   s=k;i+=1
  else:
   t=X.find(y,s)+1
   if t:z+=[t]
 print(len(z))