Go: package main

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

func max(x, y int) int {
	if x < y {
		return y
	} else {
		return x
	}
}

/*********************************************************************
長さmの列X_(m)と長さnの列Y_(n)の最長共通部分列LCSは、
	(1)X[m] == Y[n]ならば、X_(m-1)とY_(n-1)のLCSにX[m]を繋げたもの
	(2)X[m] != Y[n]ならば、X_(m-1)とY_(n)のLCSもしくはX_(m)とY_(n-1)のLCS
	のいずれかのうち長い方

c[m+1][n+1]：c[i][j]にX_(i)とY_(j)のLCSの長さを格納する二次元配列
*********************************************************************/

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	n, _ := strconv.Atoi(scanner.Text())
	for i := 0; i < n; i++ {
		scanner.Scan()
		s1 := scanner.Text()
		scanner.Scan()
		s2 := scanner.Text()
		s1, s2 = " " + s1 , " " + s2
		c := make([][]int, len(s1))
		for i := range c {
			c[i] = make([]int, len(s2))
		}

		LCS := 0

		for i := 1; i < len(s1); i++ {
			for j := 1; j < len(s2); j++ {
				if s1[i] == s2[j] {
					c[i][j] = c[i-1][j-1] + 1
				} else {
					c[i][j] = max(c[i-1][j], c[i][j-1])
				}
				LCS = max(LCS, c[i][j])
			}
		}
		fmt.Println(LCS)
	}
}

Python: import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7


def lcs(s1, s2):##
	dp = []
	for s2_k in s2:
		bgn_idx = 0
		for i, cur_idx in enumerate(dp):
			chr_idx = s1.find(s2_k, bgn_idx) + 1
			if not chr_idx:
				break
			dp[i] = min(cur_idx, chr_idx)
			bgn_idx = cur_idx
		else:
			chr_idx = s1.find(s2_k, bgn_idx) + 1
			if chr_idx:
				dp.append(chr_idx)
	return len(dp)

q = INT()

for _ in range(q):
	S = input()
	T = input()
	print(lcs(S, T))

Python: import sys

c = [[0 for _ in range(1001)] for _ in range(1001)]
for _ in range(int(sys.stdin.readline())):
    x = sys.stdin.readline().rstrip()
    y = sys.stdin.readline().rstrip()
    c[0][0]=0
    for i,xi in enumerate(x):
        for j,yj in enumerate(y):
            if xi==yj:
                c[i+1][j+1] = c[i][j]+1
            elif c[i][j+1] > c[i+1][j]:
                c[i+1][j+1] = c[i][j+1]
            else:
                c[i+1][j+1] = c[i+1][j]
            
    print(c[len(x)][len(y)])

Python: # ライブラリのインポート
#import re #正規表現
import sys
#import heapq
#import collections
#import math

def main():
    q = int(input())
    STR = [str.strip("\n") for str in sys.stdin]
    for i in range(q):
        x = STR[2*i]
        y = STR[2*i+1]
        print(lcs(x,y))


def lcs(x, y):
    dp = []
    for y_k in y:
        ps = 0
        for i, pdp in enumerate(dp):
            p = x.find(y_k, ps) + 1 #.find method returns -1 if there is no element
            if not p: break
            dp[i] = min(p,pdp)
            ps = pdp
        else: #else block is executed when for block has done completedly
            p = x.find(y_k, ps) + 1
            if p: dp.append(p)
    return len(dp)


if __name__ == '__main__':
    main()

Python: n = int(input())
for i in range(n):
    a = input()
    b = input()
    L = [[0 for j  in range(len(a) + 1)] for k in range(len(b) + 1)]
    for  m in range(1, len(a) + 1):
        for n in range(1, len(b) + 1):
            if a[m-1] == b[n-1]:
                L[n][m] = L[n-1][m-1] + 1
            else:
                L[n][m] = max(L[n-1][m], L[n][m-1])
    print(L[-1][-1])

Python: from typing import List


def compute_lcs(x_str: str, y_str: str) -> int:
    if len(x_str) <= len(y_str):
        shorter_str, longer_str = x_str, y_str
    else:
        shorter_str, longer_str = y_str, x_str

    lcs_idx: List[int] = []
    for s_ch in shorter_str:
        l_bgn_idx = 0
        for i, l_cur_idx in enumerate(lcs_idx):
            l_idx = longer_str.find(s_ch, l_bgn_idx)
            if -1 == l_idx:
                break
            lcs_idx[i] = min(l_cur_idx, l_idx)
            l_bgn_idx = l_cur_idx + 1  # Move to the next ch.
        l_idx = longer_str.find(s_ch, l_bgn_idx)
        if -1 != l_idx:
            lcs_idx.append(l_idx)
    return len(lcs_idx)


if __name__ == "__main__":
    num_pairs = int(input())

    for _ in range(num_pairs):
        x_str = input()
        y_str = input()
        lcs = compute_lcs(x_str, y_str)
        print(f"{lcs}")

Python: 
n=int(input())
cnt=[]
for k in range(n):
    a=input()
    b=input()
    lc=[[0 for j in range(len(b)+1)]for i in range(len(a)+1)]
    for i in range(len(a)):
        for j in range(len(b)):
            if a[i]==b[j]:
                lc[i+1][j+1]=lc[i][j]+1
            else:
                if lc[i][j+1]>lc[i+1][j]:
                    lc[i+1][j+1]=lc[i][j+1]
                else:
                    lc[i+1][j+1]=lc[i+1][j]
    cnt.append(lc[-1][-1])
for i in range(len(cnt)):
    print(cnt[i])