Go: package main

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

//Util
func nextStr() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func maxInt(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func minInt(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

func absInt(a int) int {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

func absFloat64(a float64) float64 {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

func minFloat64(a, b float64) float64 {
	if a > b {
		return b
	} else {
		return a
	}
}

func str2Int(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}

//Main
var sc = bufio.NewScanner(os.Stdin)
var q int
var X, Y string

func lcs(X, Y string) int {
	lenX := len(X)
	lenY := len(Y)
	dp := make([][]int, lenX+1)
	for i := 0; i < lenX+1; i++ {
		dp[i] = make([]int, lenY+1)
	}

	res := 0
	for i := 1; i < lenX+1; i++ {
		for j := 1; j < lenY+1; j++ {
			if X[i-1] == Y[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = maxInt(dp[i-1][j], dp[i][j-1])
			}
			//fmt.Println(dp)
			res = maxInt(res, dp[i][j])
		}

	}
	return res
}

func main() {
	sc.Split(bufio.ScanWords)
	q = nextInt()

	for i := 0; i < q; i++ {
		X = nextStr()
		Y = nextStr()

		fmt.Println(lcs(X, Y))
	}
}

Python: def prep_array(X, Y):
    c = [[0]*1001 for _ in range(1000+1)]
    return c


def calc_lcs(X, Y, c):
    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 check_max(array):
    max_lcs = 0
    for row in array:
        temp_max = max(row)
        if temp_max > max_lcs:
            max_lcs = temp_max
    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, prep_array(X, Y))

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

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: def make_lcs(lhs , rhs):
    c = [[0 for _ in range(len(rhs) + 1)] for _ in range(len(lhs) + 1)]
    for l_i in range(len(lhs)):
        for r_i in range(len(rhs)):
            if lhs[l_i] == rhs[r_i]:
                c[l_i + 1][r_i + 1] = c[l_i][r_i] + 1
            else:
                c[l_i + 1][r_i + 1] = max(c[l_i][r_i + 1], c[l_i + 1][r_i])
    print(c[-1][-1])


if __name__ == '__main__':
    n = int(input())
    for _ in range(n):
        lhs = [i for i in input().rstrip()]
        rhs = [i for i in input().rstrip()]
        make_lcs(lhs, rhs)

Python: #Longest Common Subsequence
#?????????

def lastindex(a,x):
    #????????????a??????????????????????????????x??????????????????????????????????????????1???????????????????????????x????????¨???????????¨??????-1????????????
    try:
        return len(a)-a[::-1].index(x)-2
    except:
        return(-1)

'''
X={x1,x2,...xm}
Y={y1,y2,...yn}????????????

Xi={x1,x2,...xi}(1<=i<=m)
Yj={y1,y2,...yj}(1<=j<=n)
Z(i,j)=Xi??¨Yj???????????±?????¨???????????????
??¨?????????????????¨???

Zi,j=max{
	Z(lastindex(Xi,yj),j-1)+1
	Z(i-1,lastindex(Yj,xi))+1
	Z(i-1,j)
	Z(i,j-1)
}
??¨?????????
??¢??°lastindex??§???(Zi,j????¨????????????¨????????§?????????)??????1??????????????????????????????????????????lastindex(a,x)???0?????¨??????lastindex(a,i)-1=-1??¨?????£???????????????Z[lastindex(a,x)-1][...]?????¨?????\?????????????????£?????????????????????
a?????????x????????¨???????????????????????????-1??¨???????????¨??§?????????????????°???????????§?????¨??????-1?????????????????????
'''

#????????????????????°????????§?????£???????????????AOJ????????????????????¨??????????????????X??¨Y????\???????????????¨??????TLE??¨?????£???????????£??????

q=int(input())


for repeat in range(q):
    X=input()
    Y=input()
    lenX=len(X)
    lenY=len(Y)
    Z=[[0 for i in range(lenY)] for i in range(lenX)]

    if X[0]==Y[0]:
        Z[0][0]=1
    
    for i in range(1,lenY):
        if Z[0][i-1]==1:
            Z[0][i]=1
        else:
            if Y[i]==X[0]:
                Z[0][i]=1

    for j in range(lenX):
        if Z[j-1][0]==1:
            Z[j][0]=1
        else:
            if X[j]==Y[0]:
                Z[j][0]=1


    for i in range(1,lenX):
        for j in range(1,lenY):
            x=lastindex(X[:i+1:],Y[j])
            y=lastindex(Y[:j+1:],X[i])

            if x!=-1 and y!=-1:
                Z[i][j]=max(Z[x][j-1],Z[i-1][y])+1
            elif x!=-1:
                Z[i][j]=Z[x][j-1]+1
            elif y!=-1:
                Z[i][j]=Z[i-1][y]+1

            Z[i][j]=max(Z[i][j],Z[i-1][j],Z[i][j-1])

    print(Z[-1][-1])

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


def lcs(x, y):
    n = len(x)
    m = len(y)
    return rec(x, y, n, m)


@functools.lru_cache(maxsize=None)
def rec(x, y, i, j):
    if i == 0 or j == 0:
        return 0
    elif x[i - 1] == y[j - 1]:
        return rec(x, y, i - 1, j - 1) + 1
    else:
        return max(rec(x, y, i, j - 1), rec(x, y, i - 1, j))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10**7)
    q = int(sys.stdin.readline().strip())
    for i in range(q):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print(lcs(x, y))

Python: import sys
def lcs(X, Y):
    indices = [0]
    for c in Y:
        for i in range(len(indices) - 1, -1, -1):
            tmp = X.find(c, indices[i])
            if tmp + 1:
                if i + 1 < len(indices):
                    indices[i + 1] = min(indices[i + 1], tmp + 1)
                else:
                    indices.append(tmp + 1)
    return len(indices) - 1

q = int(input())
for i in range(q):
    X = sys.stdin.readline().rstrip('\r\n')
    Y = sys.stdin.readline().rstrip('\r\n')
    print(lcs(X, Y))

Python: import sys
from functools import lru_cache

sys.setrecursionlimit(3 * 1000)

@lru_cache(maxsize=None)
def lcs_rec(i, j):
    if i == 0 or j == 0:
        return 0

    if X[i - 1] == Y[j - 1]:
        return lcs_rec(i - 1, j - 1) + 1
    else:
        return max(lcs_rec(i - 1, j), lcs_rec(i, j - 1))

q = int(input())

for i in range(q):
    X = input()
    Y = input()

    ans = lcs_rec(len(X), len(Y))

    print(ans)

Python: # -*- coding: utf-8 -*-
def lcs_sol(x, y):
    n = len(x)
    m = len(y)
    dp = [0 for j in range(m + 1)]

    for i in range(1, n + 1):
        dp_prev = dp[:]
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                dp[j] = dp_prev[j - 1] + 1
            elif dp_prev[j] < dp[j - 1]:
                dp[j] = dp[j - 1]

    return dp[m]


# if __name__ == '__main__':
import sys
q = int(sys.stdin.readline().strip())
for i in range(q):
    x = sys.stdin.readline().strip()
    y = sys.stdin.readline().strip()
    print(lcs_sol(x, y))

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
            elif dp[i-1][j] >= dp[i][j-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]

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