Go: package main

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

var (
	nstr   func() string
	stdout *bufio.Writer
)

func init() {
	nstr = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func main() {
	defer stdout.Flush()

	n := nint()
	xList := make([]string, n)
	yList := make([]string, n)

	for i:=0;i<n ;i++  {
		xList[i] = nstr()
		yList[i] = nstr()
	}

	for i := 0; i<n	; i++  {
		fmt.Println(lcs(xList[i], yList[i]))
	}

}

func lcs(x string, y string) int{
	var m = len(x)
	var n = len(y)

	c := make([][]int, m+1)
	for i:= range c{
		c[i] = make([]int, n+1)
	}
	for i:=	1;i<=m ;i++  {
		for j:=1;j<=n ;j++  {
			if x[i-1] == y[j-1]{
				c[i][j] = c[i-1][j-1] + 1
			}else{
				c[i][j] = int(math.Max(float64(c[i-1][j]), float64(c[i][j-1])))
			}


		}
	}
	return c[m][n]

}


func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func nint64() int64 {
	i, err := strconv.ParseInt(nstr(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func nint() int {
	return int(nint64())
}

func getIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = nint()
	}
	return b
}

func getStringSlice(n int) []string {
	b := make([]string, n)
	for i := 0; i < n; i++ {
		b[i] = nstr()
	}
	return b
}

func gcd(x, y int) int {
	if y == 0 {
		return x
	}
	return gcd(y, x%y)
}

func lcm(x, y int) int {
	return x * y / gcd(x, y)
}

func contains(s []int, e int) bool {
	for _, a := range s {
		if a == e {
			return true
		}
	}
	return false
}

func bin(i int, prefix bool) string {
	i64 := int64(i)

	if prefix {
		return "0b" + strconv.FormatInt(i64, 2)
	} else {
		return strconv.FormatInt(i64, 2)
	}
}

func strReverse(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}

	return string(runes)
}

Python: import sys
sys.setrecursionlimit(10000)

def calc(x,y):
    i = len(x)
    j = len(y)
    if not d[i][j] == None:
        return d[i][j]
    else:
        if x[-1] == y[-1]:
            tmp = calc(x[:-1],y[:-1])+1
            d[i][j] = tmp
            return tmp
        else:
            tmp = max(calc(x[:-1],y),calc(x,y[:-1]))
            d[i][j] = tmp
            return tmp
        
q = int(input())
for i in range(q):
    x = input()
    y = input()
    d = [[0 if i == 0 or j == 0 else None for i in range(len(y)+1)] for j in range(len(x)+1)]
    print(calc(x,y))

Python: def lcs(str1, str2):
    lcslist = []
    for s in str2:
        m = n = 0
        for index in lcslist:
            t = str1.find(s, m) + 1
            if t <= 0:
                break
            elif t < index:
                lcslist[n] = t
            m = index
            n += 1
        else:
            t = str1.find(s, m) + 1
            if t > 0:
                lcslist.append(t)
    return len(lcslist)

if __name__ == '__main__':
    n = int(input())
    for i in range(n):
        str1 = input()
        str2 = input()
        print(lcs(str1, str2))

Python: q = int(input())

for k in range(q):
    x = list(input())
    y = list(input())
    lcs = [[0 for i in range(len(x)+1)] for j in range(len(y)+1)]
    for i in range(1,len(y) + 1):
        for j in range(1,len(x) + 1):
            if x[j-1] != y[i-1]:
                lcs[i][j] = max(lcs[i][j-1],lcs[i-1][j])
            else:
                lcs[i][j] = lcs[i-1][j-1] + 1
    print(lcs[len(y)][len(x)])

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

Python: def calc(x,y):
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        dp2 = dp1[:]
        for j in range(m):
            if x[i] == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    return dp1[-1]

q = int(input())
for i in range(q):
    x = input()
    y = input()
    print(calc(x,y))

Python: import sys


n = int(input())

primary = [0] * 1000
secondary = [0] * 1000


for i in range(n):
    s1 = sys.stdin.readline().strip()
    s2 = sys.stdin.readline().strip()

    len1 = len(s1)
    len2 = len(s2)

    for i in range(len1):
        primary[i] = 0
        secondary[i] = 0

    for i in range(len2):
        for j in range(len1):
            if s1[j] == s2[i]:
                matched = 1
            else:
                matched = 0

            if j == 0:
                secondary[j] = matched
            else:
                sc0 = secondary[j-1]
                pr0 = primary[j-1] + matched
                pr1 = primary[j]
                if sc0 > pr0:
                    if pr0 > pr1:
                        secondary[j] = sc0
                    elif sc0 > pr1:
                        secondary[j] = sc0
                    else:
                        secondary[j] = pr1
                else:
                    if sc0 > pr1:
                        secondary[j] = pr0
                    elif pr0 > pr1:
                        secondary[j] = pr0
                    else:
                        secondary[j] = pr1

        primary, secondary = secondary, primary

    print(primary[len1-1])

Python: m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    A = [0 for j in range(len(str2)+1)]
    for char1 in str1:
        A_copy = A[:]
        for char2 in str2:
            if(char1==char2):
                A[k+1] = A_copy[k]+1
            elif(A[k] > A[k+1]):
                A[k+1] = A[k]
    print(A[-1])

Python: def solve():
    n = int(input())
    dp = [[0] * 1005 for _ in range(1005)]
    for _ in range(n):
        x = input()
        y = input()
        len_x = len(x)
        len_y = len(y)
        for i in range(len_x):
            for j in range(len_y):
                if x[i] == y[j]:
                    dp[i + 1][j + 1] = dp[i][j] + 1
                else:
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
        print(dp[len_x][len_y])
solve()

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

Python: def num_substr(s, t):
    sl = len(s)
    tl = len(t)
    dp = {}
    for i in range(sl + 1):
        dp[i] = {0: 0}
    for j in range(sl + 1):
        dp[0][j] = 0
     
    for i in range(1,sl+1):
        si_1 = s[i-1]
        dpi = dp[i]
        dpi_1 = dp[i-1]
        for j in range(1,tl+1):
            d=1 if si_1 == t[j-1] and dpi_1[j-1] == dpi[j-1] else 0
            dp[i][j] = max(dpi_1[j] ,
                           dpi[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: def lcs(X,Y):
    p=len(X)
    q=len(Y)
    Z=[[0 for i in range(q+1)]for j in range(p+1)]
    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]
    return Z[p][q]

n=int(input())
a=[0 for i in range(n)]
for i in range(n):
    X=input()
    Y=input()
    a[i]=lcs(X,Y)
for i in range(n):
       print(a[i])