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 f() {
	var S, T string
	fmt.Scan(&S)
	fmt.Scan(&T)
	lenS, lenT := len(S), len(T)
	dp := make([][]int, lenS+1)
	for i:=0; i<lenS+1; i++ {
		dp[i] = make([]int, lenT+1)
	}
	for i:=1; i<lenS+1; i++ {
		for j:=1; j<lenT+1; j++ {
			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])
}

func main(){
	var n int 
	fmt.Scan(&n)
	for i:=0; i<n; i++ {
		f()
	}
}

Python: import sys
def longest_common_subsequence(line1, line2):
    n_rows = len(line2) + 1
    array = [0] * n_rows

    ix_ = [x for x in range(n_rows)]
    ix = [x+1 for x in range(n_rows)]

    for l1_letter in line1:
        prev_array = array[:]
        for i_row_, i_row, l2_letter in zip(ix_, ix, line2):
            if l1_letter == l2_letter:
                array[i_row] = prev_array[i_row_] + 1
            else:
                up = prev_array[i_row]
                left = array[i_row_]
                array[i_row] = up if up > left else left
    return array[-1]

calc_time = False
if calc_time: import time; start = time.time()
def main():
    n = int(input())
    lines = sys.stdin.readlines()
    for i in range(0, 2*n, 2):
        ans = longest_common_subsequence(lines[i].rstrip(), lines[i+1].rstrip())
        print(ans)
    return

main()
if calc_time:print("elapsed:",time.time()-start)

Python: n = int(input())


def lcs(s1, s2):
    N, M = len(s1), len(s2)

    for _ in range(N+1):
        c.append([0]*(M+1))

    for i in range(1, N+1):
        for j in range(1, M+1):
            if s1[i-1] == s2[j-1]:
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i-1][j], c[i][j-1])


for _ in range(n):
    c = []
    s1 = input()
    s2 = input()
    lcs(s1, s2)
    print(c[len(s1)][len(s2)])
    # print(c[len(s1)], c[len(s2)])

Python: N = int(input())

for _ in range(N):
    x = input()
    y = input()
    m, n = len(x), len(y)
    dp = [[0 for i in range(n+1)] for j 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
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
                
    print(dp[m][n])

Python: q = int(input())

for i 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-1][j-1],lcs[i][j-1],lcs[i-1][j])
            else:
                lcs[i][j] = max(lcs[i-1][j-1] + 1,lcs[i][j-1],lcs[i-1][j])
    print(lcs[i][j])

Python: import bisect
import collections
import heapq
import itertools
import operator
import sys

def lcs(x, y):
    dp = [[0] * 1010 for _ in range(1010)]
    for i, c in enumerate(y):
        if c == x[0]:
            dp[0][i] = 1
    for i, c in enumerate(x):
        if c == y[0]:
            dp[i][0] = 1
    for i in range(len(x)):
        for j in range(len(y)):
            if x[i] == y[j]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
    return dp[len(x)-1][len(y)-1]

def main():
    n = int(sys.stdin.readline())
    for _ in range(n):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print(lcs(x, y))


if __name__ == '__main__':
    main()

Python: def num_substr(s, t):
    dp = {}
    for i in range(len(s) + 1):
        dp[i] = {0: 0}
    for j in range(len(t) + 1):
        dp[0][j] = 0
     
    for i in range(1,len(s)+1):
        si_1 = s[i-1]
        dpi = dp[i]
        dpi_1 = dp[i-1]
        for j in range(1,len(t)+1):
            d=1 if si_1 == t[j-1] and dpi_1[j-1] == dpi[j-1] else 0
            dpi[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: q = int(input())

for i in range(q):
    X = input()
    Y = input()
    x = len(X)
    y = len(Y)
    X = ' ' + X
    Y = ' ' + Y
    dp = [[None] * (y + 1)] * (x + 1)
    for i in range(1, x+1):
        dp[i][0] = 0
    for i in range(1, y+1):
        dp[0][i] = 0
    for j in range(1, x + 1):
        for k in range(1, y + 1):
            if X[j - 1] == Y[k - 1]:
                dp[j][k] = dp[j - 1][k - 1] + 1
            else:
                dp[j][k] = max(dp[j - 1][k],dp[j][k - 1])
    print(dp[x][y])

Python: #
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    Q=I()
    for _ in range(Q):
        S=ST()
        T=ST()[::-1]
        lis = []
        find, append = T.find, lis.append

        for c in S:
            i = find(c)+1
            while i:
                j = bisect_left(lis, -i)
                if j >= len(lis):
                    append(-i)
                else:
                    lis[j] = -i
                i = find(c, i)+1
        print(len(lis))
if __name__ == '__main__':
    main()