Go: package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)
	for i := 0; i < n; i++ {
		x := getNextString(scanner)
		y := getNextString(scanner)

		fmt.Fprintln(writer, lcs(x, y))
	}

	writer.Flush()
}

func lcs(x, y string) int {
	lx := len(x)
	ly := len(y)
	dp := make([][]int, lx+1)
	for i := 0; i <= lx; i++ {
		dp[i] = make([]int, ly+1)
	}
	for i := 0; i < lx; i++ {
		for ii := 0; ii < ly; ii++ {
			if x[i] == y[ii] {
				dp[i+1][ii+1] = dp[i][ii] + 1
				continue
			}
			dp[i+1][ii+1] = dp[i][ii+1]
			if dp[i+1][ii] > dp[i+1][ii+1] {
				dp[i+1][ii+1] = dp[i+1][ii]
			}
		}
	}
	return dp[lx][ly]
}

Python: n=int(input())
al=[]
bl=[]
for i in range(n):
	al.append(list(input()))
	bl.append(list(input()))

for i in range(n):
	a=al.pop(0)
	b=bl.pop(0)
	dp=[[0 for i in range(len(b))] for j in range(len(a))]

	if a[0]==b[0]:
		dp[0][0]=1
	for i in range(1,len(a)):
		if a[i]==b[0]:
			dp[i][0]=1
		else:
			dp[i][0]=dp[i-1][0]
	for i in range(1,len(b)):
		if a[0]==b[i]:
			dp[0][i]=1
		else:
			dp[0][i]=dp[0][i-1]
	for i in range(1, len(a)):
		for j in range(1, len(b)):
			if a[i]!=b[j]:
				dp[i][j]=max(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])
			else:
				dp[i][j]=dp[i-1][j-1]+1

	print(dp[len(a)-1][len(b)-1])

Python: from collections import defaultdict


def lcs(x, y):
    dp = [defaultdict(int) for _ in range(len(x) + 1)]
    dp[0] = [0]*(len(y) + 1)
    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])
    return dp[len(x)][len(y)]


N = int(input())
for i in range(N):
    x = input()
    y = input()
    print(lcs(x, y))

Python: def lcs(l1,l2):
    dp=[[0 for x in range(len(l2)+1)] for y in range(len(l1)+1)]

    for i in range(1,len(l1)+1):
        for j in range(1,len(l2)+1):
            if l1[i-1]==l2[j-1]:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
                
    return dp[len(l1)][len(l2)]


a=[]
n=int(input())
for i in range(n):
    l1=list(input())
    l2=list(input())
    a+=[lcs(l1,l2)]

for i in range(n):
    print(a[i])

Python: def longest_common_subseq(S, T):
    if not S and not T: return 0
    len_S, len_T = len(S), len(T)
    dp = [0] * (len_T + 1)
    prev = [0] * (len_T + 1)
    for s in S:
        for j in range(len_T):
            if s == T[j]: dp[j+1] = prev[j] + 1
            elif dp[j] > dp[j+1]: dp[j+1] = dp[j]
        prev = dp[:]
    return dp[len_T]

Q = int(input())
ans = []
for _ in range(Q):
    X = input()
    Y = input()
    ans.append(longest_common_subseq(X, Y))
print(*ans, sep='\n')

Python: q = int(input().rstrip())
data_set = [[[i for i in input().rstrip()],
             [i for i in input().rstrip()]] for i in range(q)]

common_list = [[0] * 2000 for i in range(2000)]


def lcs(X: list, Y: list):
    global common_list
    m, n = len(X), len(Y)
    for i in range(1, m + 1):
        for k in range(1, n + 1):
            if X[i - 1] == Y[k - 1]:
                common_list[i][k] = common_list[i - 1][k - 1] + 1
            elif common_list[i - 1][k] >= common_list[i][k - 1]:
                common_list[i][k] = common_list[i - 1][k]
            else:
                common_list[i][k] = common_list[i][k - 1]
    return common_list[m][n]


for l, r in data_set:
    print(lcs(l, r))

Python: # ALDS_10_C - 最長共通部分列

import sys


# def main():
#     q = int(input())
#
#     for _ in range(q):
#         X = list(str(sys.stdin.readline().strip()))
#         Y = list(str(sys.stdin.readline().strip()))
#
#         dp = [[0] * (len(X) + 1) for _ in range(len(Y) + 1)]
#
#         for y in range(len(Y)):
#             for x in range(len(X)):
#                 dp[y + 1][x + 1] = max(dp[y][x + 1], dp[y + 1][x])
#                 if X[x] == Y[y]:
#                     dp[y + 1][x + 1] = dp[y][x] + 1
#
#         print(dp[-1][-1])


def main():
    q = int(input())

    for _ in range(q):
        X = list(str(sys.stdin.readline().strip()))
        Y = list(str(sys.stdin.readline().strip()))

        dp = [0] * (len(X) + 1)

        for y in range(len(Y)):
            dp2 = dp[:]
            # print(dp2)
            for x in range(len(X)):
                if X[x] == Y[y]:
                    dp[x + 1] = dp2[x] + 1
                elif dp[x + 1] < dp[x]:
                    dp[x + 1] = dp[x]

        print(dp[-1])


if __name__ == '__main__':
    main()

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

    for i in range(1, x):
        for j in range(1, y):
            if X[i - 1] == Y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
    return c[x - 1][y - 1]

n = int(input())

for i in range(n):
    X = input()
    Y = input()
    print(lcs(X, Y))

Python: #dj 16D8101012J ito jun
n = int(input())
for _ in range(n):
    a = input()
    b = input()
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]+1:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    print(array[-1][-1])

Python: import sys

def dp_init(m, n):
    return [[0] * n] * m

def solve(str_a, str_b):
    dp = dp_init(len(str_a), len(str_b))
    return rec(len(str_a), len(str_b), str_a, str_b, dp)

def rec(i, j, str_a, str_b, dp):
    if i == 0 or j == 0:
        return 0
    if dp[i][j] > 0:
        return dp[i][j]
    if str_a[i-1] == str_b[j-1]:
        dp[i][j] = rec(i-1, j-1, str_a, str_b, dp) + 1
        return dp[i][j]
    dp[i][j] = max(rec(i, j-1, str_a, str_b, dp), rec(i-1, j, str_a, str_b, dp))
    return dp[i][j]

nb_pairs = int(input())
pairs = []
for i in range(0, nb_pairs):
    pairs.append((input(), input()))

for i in range(0, nb_pairs):
    str_a, str_b = pairs[i]
    print(solve(str_a, str_b))

Python: def search(x, y):
    x_length = len(x)
    y_length = len(y)
    memo = [[0] * (y_length + 1) for i in range(x_length + 1)]
    for i, ch_x in enumerate(x, 1):
        row = memo[i]
        pre_row = memo[i-1]
        for j, ch_y in enumerate(y, 1):
            if ch_x == ch_y:
                row[j] = pre_row[j-1] + 1
            elif pre_row[j] < row[j-1]:
                row[j] = row[j-1]
            else:
                row[j] = pre_row[j]
    return memo[-1][-1]

N = int(input())
for i in range(N):
    X = input()
    Y = input()
    print(search(X, Y))

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