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: import sys

for _ in range(int(sys.stdin.readline())):
    x = sys.stdin.readline()
    y = sys.stdin.readline()
    c = [[0 for _ in range(len(y))] for _ in range(len(x))]
    

    for i in range(1,len(x)):
        for j in range(1,len(y)):
            if i>0 and j>0 and x[i-1]==y[j-1]:
                c[i][j] = c[i-1][j-1]+1
            else:
                c[i][j] = max(c[i][j-1], c[i-1][j])
            
    print(c[len(x)-1][len(y)-1])

Python: def calc(x,y):
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == 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())
ans = []
for i in range(q):
    x = input()
    y = input()
    print(calc(x,y))

Python: from itertools import chain
from collections import deque
from sys import stdin
def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0] * 1001 for i in range(1002)]
    x = " " + x
    y = " " + y
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i] == y[j]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
    return max(chain.from_iterable(c))


n = int(input().rstrip())
strs = deque(stdin.readlines())
ret = []
for i in range(n):
    s1 = strs.popleft().rstrip()
    s2 = strs.popleft().rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")

Python: n=int(input())

for i in range(n):
    a=list(input())
    b=list(input())
    x=len(a)+1
    y=len(b)+1

    r=[[0 for j in range(y)]for i in range(x)]

    for j in range(1,x):
        for k in range(1,y):
            if r[j-1][k]>r[j][k-1]:
                c=r[j-1][k]
            else:
                c=r[j][k-1]
            if a[j-1]==b[k-1]:
                if r[j-1][k-1]+1>c:
                    c=r[j-1][k-1]+1
            
            r[j][k]=c    
    print(r[x-1][y-1])

Python: import sys
from functools import lru_cache

sys.setrecursionlimit(3 * 1000)

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: def calc_lcs(X, Y):
    max_lcs = 0
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y
    c = [[0 for _ in range(1000+1)] for i in range(1000+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i] == Y[j]:
                c[i][j] = c[i - 1][j - 1] + 1
            elif c[i - 1][j] >= c[i][j - 1]:
                c[i][j] = c[i - 1][j]
            else:
                c[i][j] = c[i][j - 1]
            max_lcs = max(max_lcs, c[i][j])
    return max_lcs


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    # X = 'abcbdab'
    # Y = 'bdcaba'

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

        # ???????????????
        result = calc_lcs(X, Y)

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

Python: import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            if c1 == c2:
                match = 1
            else:
                match = 0
            pr2 = results[j]
            mval = max(sec1, pr2, pr1 + match)
            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]



n = int(input())
s = []
for line in sys.stdin:
    s.append(line.strip())
for i in range(0, 2*n, 2):
    print(len_lcs(s[i], s[i+1]))

Python: import sys
def lcs(X, Y):
    m = len(X)
    n = len(Y)
    c = [[0 for i 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]:
                c[i][j] = c[i-1][j-1] + 1
            elif c[i -1][j] >= c[i][j - 1]:
                c[i][j] = c[i-1][j]
            else:
                c[i][j] = c[i][j-1]
    return str(c[m][n])

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: q = int(input())
X = ""
Y = ""
memo = [[]]

def LCS(x, y):
    if (x < 0) or (y < 0):
        return 0
    elif memo[x][y] != -1:
        return memo[x][y]
    else:
        memo[x][y] = max(LCS(x-1,y), LCS(x,y-1), LCS(x-1, y-1)+int(X[x] == Y[y]))
        return memo[x][y]

for c in range(q):
    X = input()
    Y = input()
    memo = [[-1 for j in range(len(Y))] for i in range(len(X))]
    print(LCS(len(X)-1, len(Y)-1))

Python: q = int(input())
for _ in range(q):
    X = input()
    Y = input()

    dp = [[0 for _ in range(len(Y) + 1)] for _ in range(len(X) + 1)]
    for i in range(len(X)):
        for j in range(len(Y)):
            if X[i] == Y[j]:
                dp[i + 1][j + 1] = max(dp[i][j] + 1, dp[i + 1][j], dp[i][j + 1])
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
    print(dp[len(X)][len(Y)])