Go: package main

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

//Util
func nextStr() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func maxInt(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func minInt(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

func absInt(a int) int {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

func absFloat64(a float64) float64 {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

func minFloat64(a, b float64) float64 {
	if a > b {
		return b
	} else {
		return a
	}
}

func str2Int(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}

//Main
var sc = bufio.NewScanner(os.Stdin)
var q int
var X, Y string

func lcs(X, Y string) int {
	lenX := len(X)
	lenY := len(Y)
	dp := make([][]int, lenX+1)
	for i := 0; i < lenX+1; i++ {
		dp[i] = make([]int, lenY+1)
	}

	res := 0
	for i := 1; i < lenX+1; i++ {
		for j := 1; j < lenY+1; j++ {
			if X[i-1] == Y[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = maxInt(dp[i-1][j], dp[i][j-1])
			}
			//fmt.Println(dp)
			res = maxInt(res, dp[i][j])
		}

	}
	return res
}

func main() {
	sc.Split(bufio.ScanWords)
	q = nextInt()

	for i := 0; i < q; i++ {
		X = nextStr()
		Y = nextStr()

		fmt.Println(lcs(X, Y))
	}
}

Python: from collections import defaultdict
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 = g(c[s2_k], bgn_idx)
            if chr_idx == INF:
                continue
            dp[i] = min(cur_idx, chr_idx + 1)
            bgn_idx = cur_idx
        else:
            chr_idx = g(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: #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])
            idx=Y[:y+1].rfind(X[x])
            if idx!=-1:
                dp[x][y]=max(dp[x-1][idx-1]+1,dp[x][y])
            idx=X[:x+1].rfind(Y[y])
            if 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):
    if not len(X) or not len(Y):
        return 0
    if X[-1] == Y[-1]:
        return 1 + lcs(X[:-1], Y[:-1])
    else:
        return max(lcs(X[:-1], Y), lcs(X, Y[:-1]))

q = int(input())
for i in range(q):
    X = input()
    Y = input()
    print(lcs(X, Y))

Python: m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    A = [0]*(len(str2)+1)
    for char1 in str1:
        A_copy = A[:]
        for j,char2 in enumerate(str2):
            if(char1==char2):
                A[j+1] = A_copy[j]+1
            elif(A[j] > A[j+1]):
                A[j+1] = A[j]
    print(A[-1])

Python: q = int(input())
for _ in range(q):
    X = input()
    Y = input()
    NX = len(X)
    NY = len(Y)
    dp = [[0] * (NY+1) for _ in range(NX+1)]
    jx = [0 for _ in range(NX)]
    jy = [0 for _ in range(NY)]
    for x in range(NX):
        for y in range(NY):
            if jx[x] == 0 and jy[y] == 0 and X[x] == Y[y]:
                dp[x+1][y+1] = max(dp[x][y+1], dp[x+1][y]) + 1
                jx[x] = 1
                jy[y] = 1
            else:
                dp[x+1][y+1] = max(dp[x][y+1], dp[x+1][y])

    print(dp[NX][NY])

Python: n=int(input())
al=[]
bl=[]
for i in range(n):
	al.append(list(input()))
	bl.append(list(input()))

for i in range(n):
	a=al.pop(0)
	b=bl.pop(0)
	dp=[[0 for i in range(len(b))] for j in range(len(a))]

	for i in range(len(a)):
		for j in range(len(b)):
			if i==0:
				if j==0:
					if a[i]==b[j]:
						dp[i][j]=1
					else:
						dp[i][j]=0
				elif a[i]==b[j]:
					dp[i][j]=1
				else:
					dp[i][j]=dp[i][j-1]
			elif j==0:
				if a[i]==b[j]:
					dp[i][j]=1
				else:
					dp[i][j]=dp[i-1][j]

			elif a[i]!=b[j]:
				dp[i][j]=max(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])
			else:
				dp[i][j]=dp[i-1][j-1]+1

	print(dp[len(a)-1][len(b)-1])

Python: #dj 16D8101012J ito jun
n = int(input())
for _ in range(n):
    a = input()
    b = input()
    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]
    print(array[na][nb])

Python: from itertools import chain
from sys import stdin
def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0] * 1001 for i in range(1002)]
    # x = " " + x
    # y = " " + y
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i-1] == y[j-1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
    return max(chain.from_iterable(c))


n = int(input().rstrip())
strs = stdin.readlines()
ret = []
for i in range(n):
    s1 = strs[i*2].rstrip()
    s2 = strs[i*2+1].rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")

Python: def LCS(x,y):
    n,m=len(x),len(y)
    DP=[0 for _ in range(m+1)]
    for i in range(n):
        tmp=DP[:]
        num=x[i]
        for j in range(m):
            if num==y[j]:DP[j+1]=tmp[j]+1
            elif DP[j+1]<DP[j]:DP[j+1]=DP[j]
    return DP[-1]


n=int(input())
for _ in range(n):
    print(LCS(input(),input()))

Python: e=input
a=[]
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]
 a+=[z]
print('\n'.join(map(str,map(len,a))))

Python: #!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys

sys.setrecursionlimit(int(1e5))


def lcs(w1, w2):
    m, n = len(w1), len(w2)
    dp = tuple([[0] * (n + 1) for _ in range(m + 1)])
    max_l = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if w1[i - 1] == w2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            max_l = max(max_l, dp[i][j])

    return max_l


def lcs_recursive(w1, w2, m, n):
    if m == 0 or n == 0:
        return 0
    elif w1[m - 1] == w2[n - 1]:
        return 1 + lcs_recursive(w1, w2, m - 1, n - 1)
    else:
        return max(
            lcs_recursive(w1, w2, m, n - 1), lcs_recursive(w1, w2, m - 1, n))


def solve():
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num

    for pair in zip(word_list[::2], word_list[1::2]):
        cw1, cw2 = map(lambda x: x.strip(), pair)
        # print(lcs(cw1, cw2))
        print(lcs_recursive(cw1, cw2, len(cw1), len(cw2)))

    return None


if __name__ == '__main__':
    solve()