Go: package main

import "fmt"

func initialize_grid(width int,height int)[][]int{
	var grid [][]int
	for i:=0;i<height+1;i++{
		var grid_row  []int
		for j:=0;j<width+1;j++{
			grid_row = append(grid_row,0)
		}
		grid = append(grid,grid_row[:])
	}
	return grid
}

func ma(x int,y int)int{
	if x >= y{
		return x
	}else{
		return y
	}
}

func main()  {
	//Take input
	var num int
	var st1,st2 string
	var string_pairs [][]string
	fmt.Scan(&num)
	for i:=0;i<num;i++{
		var string_pair []string
		fmt.Scan(&st1)
		fmt.Scan(&st2)
		string_pair = append(string_pair,st1,st2)
		string_pairs = append(string_pairs,string_pair)
	}
	//DP
	//initialize grid
	for i:=0;i<num;i++{
		string_1 := string_pairs[i][0]
		string_2 := string_pairs[i][1]

		dp := initialize_grid(len(string_2),len(string_1))

		for j:=1;j<len(string_1)+1;j++{
			for k:=1;k<len(string_2)+1;k++{
				if string_1[j-1] == string_2[k-1]{
					dp[j][k] = dp[j-1][k-1] + 1
				}else{
					dp[j][k] = ma(dp[j-1][k],dp[j][k-1])
				}
			}
		}
		fmt.Println(dp[len(string_1)][len(string_2)])
	}
}

Python: def Ics(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)

    for i in range(a):
        d = x[i]
        c2 = c1[:]
        for j in range(n):
            if d == y[j]:
                c1[j + 1] = c2[j] + 1
            elif c1[j + 1] < c1[j]:
                c1[j + 1] = c1[j]
    return (c1[-1])

q = int(input().rstrip())
r = []
for k in range(q):
    s1 = input().rstrip()
    s2 = input().rstrip()
    r.append(Ics(s1, s2))

print(*r, sep = "\n")

Python: def calc_lcs(X, Y):
    from array import array
    max_lcs = 0
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y
    c = array('I', [0] * (1001 * 1001))
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i] == Y[j]:
                c[i*1001 + j] = c[(i-1)*1001 + j - 1] + 1
            elif c[(i-1)*1001 + j] >= c[i*1001 + j - 1]:
                c[i*1001 + j] = c[(i-1)*1001 + j]
            else:
                c[i*1001 + j] = c[i*1001 + j - 1]
            max_lcs = max(max_lcs, c[i*1001 + j])
    return max_lcs


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    # f = open('input.txt')
    # num = int(f.readline())

    for _ in range(num):
        X = input()
        Y = input()
        # X = f.readline().strip()
        # Y = f.readline().strip()

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

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

Python: from collections import defaultdict
from bisect import bisect_left, bisect, insort_left, insort
INF = 10000
def lcs(s1, s2):
    c = defaultdict(list)
    for i, s in enumerate(s1):
        c[s].append(i)
    for s in set(s2):
        c[s].append(INF)
    def g(li, a):
        for i in li:
            if i >= a:
                return i
        return -1
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = c[s2_k][bisect_left(c[s2_k], bgn_idx)]
            if chr_idx == INF:
                break
            dp[i] = min(cur_idx, chr_idx + 1)
            bgn_idx = cur_idx
        else:
            chr_idx = c[s2_k][bisect_left(c[s2_k], bgn_idx)]
            if chr_idx != INF:
                dp.append(chr_idx + 1)
    return len(dp)
def solve():
    N = int(input())
    for _ in range(N):
        x = input()
        y = input()
        print(lcs(x, y))
solve()

Python: def lcs(X,Y):
    res = [0 for i in range(len(X)+1)]
    for y in Y:
        previous = res[:]
        for i,x in enumerate(X):
            if x == y:
                res[i+1] = previous[i] + 1
            elif res[i] > previous[i+1]:
                res[i+1] = res[i]
    return res[-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 for i in range(nb+1)] for j in range(na+1)]
    for i in range(1,na+1):
        for j in range(1,nb+1):
            c = 0
            if a[i-1] == b[j-1]:
                c = 1
            array[i][j] = max(
                array[i-1][j],
                array[i][j-1],
                array[i-1][j-1]+c)
    print(array[na][nb])

Python: # -*- coding: utf-8 -*-
def lcs(x, y):
    n = len(x)
    m = len(y)
    dp = [0 for j in range(m + 1)]

    for i in range(1, n + 1):
        dp_prev = dp[:]
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                dp[j] = dp_prev[j - 1] + 1
            elif dp_prev[j] < dp[j - 1]:
                dp[j] = dp[j - 1]
            else:
                dp[j] = dp_prev[j]

    return dp[m]


if __name__ == '__main__':
    import sys
    q = int(sys.stdin.readline().strip())
    for i in range(q):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print(lcs(x, y))

Python: 
def resolve():
    def lcs(s1, s2):
        """
        文字列S, Tのlongest common subsequenceの長さを返す
        なお、longest common substringではない
        （要素同士がとなりあっていなくてもいい）ことに注意！
        """

        dp = []
        for s2_k in s2:
            bgn_idx = 0
            for i, cur_idx in enumerate(dp):
                # bgn_idx以降でs2_kを探す
                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(input())
    for i in range(q):
        S = str(input())
        T = str(input())
        print(lcs(S, T))


resolve()

Python: # -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: print('Yes' if b else 'No')
YESNO=lambda b: print('YES' if b else 'NO')

def main():
    Q=int(input())
    for _ in range(Q):
        S=tuple(input())
        T=tuple(input())
        dp=[0]*(len(T)+1)
        for s in S:
            pre=dp[:]
            for i,t in enumerate(T):
                if s==t:
                    dp[i+1]=max(dp[i+1],pre[i]+1)
                elif dp[i+1]<dp[i]:
                    dp[i+1]=dp[i]
        print(dp[-1])

if __name__ == '__main__':
    main()

Python: from collections import defaultdict
q = int(input())
for _ in range(q):
    x = input()
    y = input()
    len_x = len(x)
    len_y = len(y)
    if len_x < len_y:
        len_x, len_y = len_y, len_x
        x, y = y, x
    c = defaultdict(list)
    for i, s in enumerate(x):
        c[s].append(i)
    ans = 0
    def g(li, a):
        for i in li:
            if i >= a:
                return i
        return -1
    def f(x_i, y_i, cnt):
        if x_i >= len_x or y_i >= len_y:
            global ans
            if ans < cnt:
                ans = cnt
            return
        f(x_i, y_i + 1, cnt)
        s = g(c[y[y_i]], x_i)
        if s != -1:
            f(s + 1, y_i + 1, cnt + 1)
    f(0, 0, 0)
    print(ans)

Python: # -*- coding: utf-8 -*-
from itertools import product

N = int(input())

def calc_LCS(n, m):
    if n == 0 or m == 0:
        return 0
    elif X[n] == Y[m]:
        LCS[n][m] = LCS[n-1][m-1] + 1
        return LCS[n][m]
    else:
        LCS[n][m] = max(LCS[n-1][m], LCS[n][m-1])
        return LCS[n][m]
        

for _ in range(N):
    X = input()
    Y = input()
    LCS = [[0 for _ in range(len(Y) + 1)] for _ in range(len(X) + 1)]
    max_ = 0
    for n, m in product(range(1, len(X)+1), range(1, len(Y)+1)):        
        if X[n-1] == Y[m-1]:
            LCS[n][m] = LCS[n-1][m-1] + 1  
        else:
            LCS[n][m] = max(LCS[n-1][m], LCS[n][m-1])

    print(LCS[-1][-1])