Go: package main

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

type Position struct {
	X int
	Y int
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}
	for i := 0; i < n; i++ {
		strX := nextText(sc)
		strY := nextText(sc)
		fmt.Println(calcLcs(strX, strY))
	}
}

func calcLcs(strX, strY string) int {
	return lcs(strX, strY, Position{0, 0}, make(map[Position]int))
}

func lcs(strX string, strY string, position Position, memo map[Position]int) int {
	if position.X >= len(strX) || position.Y >= len(strY) {
		return 0
	}
	if v, ok := memo[position]; ok {
		return v
	}
	if strX[position.X] == strY[position.Y] {
		result := lcs(strX, strY, Position{position.X + 1, position.Y + 1}, memo)
		memo[position] = result + 1
		return memo[position]
	} else {
		result1 := lcs(strX, strY, Position{position.X + 1, position.Y}, memo)
		result2 := lcs(strX, strY, Position{position.X, position.Y + 1}, memo)
		var result int
		if result1 > result2 {
			result = result1
		} else {
			result = result2
		}
		memo[position] = result
		return result
	}
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

func nextText(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

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(0, 0, str_a, str_b)

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

Python: #dj 16D8101012J ito jun
import sys
def search(a,b):
    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]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in sys.stdin.read().splitlines()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")

Python: def solveZ(X, Y, Z, x, y):
  if x < len(X) and y < len(Y):
    ans = [solveZ(X, Y, Z, x, y+1)]
    for j in range(x, len(X)):
      if Y[y] == X[j]:
        Z2 = Z + str(Y[y])
        ans.append(solveZ(X, Y, Z2, j+1, y+1))
        break
    return max(ans)
  else:
    print(Z)
    return len(Z)

q = int(input())
ans = [[] for i in range(q)]
for i in range(q):
  X = str(input())
  Y = str(input())
  ans[i] = solveZ(X, Y, "", 0, 0)

for i in range(q):
  print(ans[i])

Python: for _ in range(int(input())):
    X = input()
    Y = input()
    dp = [[0] * (len(Y)+1) for x in range(len(X)+1)]
    for x in range(1, len(X) + 1):
        pre = dp[x-1]
        tmp = dp[x]
        for y in range(1, len(Y) + 1):
            if X[x-1] == Y[y-1]:
                tmp[y] = pre[y-1] + 1
            else:
                tmp[y] = max(tmp[y-1], pre[y])
    print(dp[-1][-1])

Python: def findlcs(x, y):
    dp = [0]*(len(y)+1)

    for c in x:
        tmp = dp[:]
        for j in range(len(y)):
            if c == y[j]:
                dp[j+1] = tmp[j] + 1
            elif dp[j+1] < dp[j]:
                dp[j+1] = dp[j]

    return dp[-1]


q = int(input())
for k in range(q):
    X = input()
    Y = input()
    print(findlcs(X, Y))

Python: def LCS(X, Y):
    n = len(X)
    m = len(Y)
    T = [0]*(n+1)
    
    for j in range(m):
        T_old = T[:]
        c = Y[j]
        for i in range(n):
            if X[i] == c:
                T[i] = T_old[i-1] + 1
            elif T[i-1] > T[i]:
                T[i] = T[i-1]            
    return T[len(X)-1] 



q = int(input())
for cnt in range(q):
    X = input()
    Y = input()
    print(LCS(X, Y))

Python: def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0] * 1001 for i in range(1002)]
    x = " " + x
    y = " " + y
    maxl = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i] == y[j]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
            maxl = max(maxl, c[i][j])
    return maxl

if __name__ == '__main__':
    n = int(input().rstrip())
    for i in range(n):
        s1 = input().rstrip()
        s2 = input().rstrip()
        print(lcs(s1, s2))

Python: #JOI
def main():
    X=input()
    Y=input()
    dp=[[0 for y in range(1+len(Y))] for x in range(1+len(X))]
    for x in range(len(X)):
        for y in range(len(Y)):
            now=0
            dp[x][y]=max(dp[x-1][y],dp[x][y-1])
            for x1 in range(Y[:y+1].count(X[x])):
                idx=Y[now:y+1].index(X[x])
                now=idx+1
                dp[x][y]=max(dp[x-1][idx-1]+1,dp[x][y])
            now=0
            for y1 in range(X[:x+1].count(Y[y])):
                idx=X[now:x+1].index(Y[y])
                now=idx+1
                dp[x][y]=max(dp[idx-1][y-1]+1,dp[x][y])
    print(dp[len(X)-1][len(Y)-1])
for i in range(int(input())):
    main()

Python: def lcs(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)
    for i in range(a):
        c2 = c1[:]
        for j in range(b):
            if x[i] == y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]


if __name__ == "__main__":
    N = int(input())
    for _ in range(N):
        x = input()
        y = input()
        print(lcs(x, y))

Python: # -*- coding:utf-8 -*-
import sys


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
            else:
                row[j] = max(pre_row[j], row[j-1])
    return memo[-1][-1]


if __name__ == "__main__":
    n = int(input())
    strs = [list(val) for val in sys.stdin.read().splitlines()]
    result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
    print(*result, sep="\n")

Python: e=input
for _ in[0]*int(e()):
 X,z=e(),[]
 for y in e():
  s=i=0
  for k in z:
   t=X.find(y,s)+1
   if t<1:break
   if t<k:z[i]=t
   s=k;i+=1
  else:
   t=X.find(y,s)+1
   if t:z+=[t]
 print(len(z))