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: 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) if len(x) > len(y) else lcs(y, x))
solve()

Python: 
def LCS(x, y):
    len_x = len(x)
    len_y = len(y)
    
    dp = {}
    for i in range(len_x + 1):
        dp[i] = {0: 0}
    for j in range(len_y + 1):
        dp[0][j] = 0
    
    for i in range(1, len_x + 1):
        for j in range(1, len_y + 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])
    
    return dp[len_x][len_y]

q = int(raw_input())
for i in range(q):
    X = raw_input()
    Y = raw_input()
    print(LCS(X, Y))

Python: from itertools import product

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, k in product(range(1, m + 1), range(1, n + 1)):
            common_list[i][k] = common_list[i - 1][k - 1] + 1 if X[i - 1] == Y[k - 1] else max(common_list[i - 1][k], common_list[i][k - 1])
    return common_list[m][n]

[print(lcs(l, r)) for l, r in data_set]

Python: import sys
readline = sys.stdin.readline
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)
    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 = readline().strip()
        y = readline().strip()
        print(lcs(x, y) if len(x) > len(y) else lcs(y, x))
solve()

Python: q = int(input().rstrip())
for i in range(q):
    x = input().rstrip()
    y = input().rstrip()
    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]
    print(dp1[-1])

Python: q = int(input())


for __ in range (q):

    S1 = input()
    S2 = input()
    dp = [[0 for i in range(len(S2)+1)] for j in range(len(S1)+1)]


    for i in range (len(S1)):
        for j in range (len(S2)):
            if S1[i] != S2[j]:
                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])
            else:
                dp[i+1][j+1] = (dp[i][j]+1)

    print(dp[len(S1)][len(S2)])

Python: n = int(input())

for i in range(n):
    s = list(input())
    t = list(input())
    dp = [[0 for j in range(len(s)+1)] for k in range(len(t)+1)]

    for j in range(len(s)):
        for k in range(len(t)):
            if s[j]==t[k]:
                dp[k+1][j+1] = max(dp[k][j]+1,dp[k+1][j+1])
            else:
                dp[k+1][j+1] = max(dp[k+1][j+1],dp[k+1][j])
                dp[k+1][j+1] = max(dp[k+1][j+1],dp[k][j+1])
    print(dp[len(t)][len(s)])

Python: # -*- coding: utf-8 -*-
def lcs(x, y):
    dp = {(0, 0): 0}
    for i in range(1, len(x) + 1):
        dp[(i, 0)] = 0
    for j in range(1, len(y) + 1):
        dp[(0, j)] = 0
    for i in range(1, len(x) + 1):
        for j in range(1, len(y) + 1):
            if x[i - 1] == y[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(x), len(y))]


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 solver(str_1 ,str_2):
  dp = [[0] * (len(str_2) + 1) for i in range(len(str_1) + 1)]
  for r in range(len(str_2)):
    for c in range(len(str_1)):
      if str_2[r] == str_1[c]:
        dp[r + 1][c + 1] = dp[r][c] + 1
      else:
        dp[r + 1][c + 1] = max(dp[r + 1][c], dp[r][c + 1])
  return dp[len(str_2)][len(str_1)]

n = int(input())
for _ in range(n):
  str_1 = input()
  str_2 = input()
  print(solver(str_1, str_2))

Python: def Ics(X, Y):
    m = len(X)
    n = len(Y)
    c1 = [0] * (n + 1)
    c2 = [0] * (n + 1)
    for i in range(m):
        d = X[i]
        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())
t = []
for i in range(q):
    s1 = input().rstrip()
    s2 = input().rstrip()
    t.append(Ics(s1, s2))
print(*t, sep="\n")

Python: def f(i,j):
    if i == 0 or j == 0:
        if s1[i] == s2[j]:
            x[i][j] = 1
        else:
            if i == 0:
                x[i][j] = x[i][j-1]
            else:
                x[i][j] = x[i-1][j]
    elif s1[i] == s2[j]:
        x[i][j] = max(x[i-1][j-1]+1,x[i][j-1],x[i-1][j])
    else:
        x[i][j] = max(x[i-1][j-1],x[i][j-1],x[i-1][j])

n = int(input())
for i in range(n):
    s1 = input()
    s2 = input()
    x = [[0 for j in range(len(s2))]for k in range(len(s1))]
    for j in range(len(s1)):
        for k in range(len(s2)):
            f(j,k)
            
    print(x[len(s1)-1][len(s2)-1])