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: def common():
   X = raw_input()
   Y = raw_input()
 
   s = [0 for i in range(len(Y)+1)]

   for j in range(0, len(X)):
      t = s + []
      for k in range(0, len(Y)):
         if X[j] == Y[k]:
            s[k+1] = t[k] + 1
         elif s[k+1] < s[k]:
            s[k+1] = s[k]
 
   return s[-1]

q = input()
for l in range(0, q):
   common()

Python: import itertools
import numpy
import time

c = [[0]*1001 for _ in range(1001)]

def make_lcs(lhs, rhs):
    llen = len(lhs)
    rlen = len(rhs)
    for l_i, r_i in itertools.product(range(llen), range(rlen)):
            c[l_i + 1][r_i + 1] = max(c[l_i][r_i + 1], c[l_i + 1][r_i]) if lhs[l_i] != rhs[r_i] else c[l_i][r_i] + 1
    print(c[llen][rlen])


if __name__ == '__main__':
    start = time.time()
    n = int(input())
    for _ in range(n):
        lhs = [i for i in input().rstrip()]
        rhs = [i for i in input().rstrip()]
        make_lcs(lhs, rhs)
    end = time.time() - start
    print('elapsed time: {}'.format(end))

Python: def lcs(str1,str2):
    c=[[0 for _ in range(1001)] for _ in range(1001)]
    m=len(str1)
    n=len(str2)
    maxl=0
    str1=" "+str1
    str2=" "+str2

    i=1
    j=1
    while(i<=m):
        while(j<=n):
            if(str1[i]==str2[j]):
                c[i][j]=c[i-1][j-1]+1
              #  print(c[i][j])
            else:
                c[i][j]=max(c[i-1][j],c[i][j-1])
            maxl=max(maxl,c[i][j])
            j+=1
        i+=1
        j=0

    return maxl

def main():
    n=int(input())
    i=0
    while(i<n):
        str1=str(input())
        str2=str(input())
        print(int(lcs(str1,str2)))
        i+=1

main()

Python: n = int(input())
xs = []
ys = []
for _ in range(n):
    x = input()
    y = input()
    xs.append(x)
    ys.append(y)

for i in range(n):
    a, b = xs[i], ys[i]
    L = []
    for bk in b:
        bgn_idx = 0
        for j, cur_idx in enumerate(L):
            chr_idx = a.find(bk, bgn_idx) + 1
            if not chr_idx:
                break
            L[j] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = a.find(bk, bgn_idx) + 1
            if chr_idx:
                L.append(chr_idx)
    print(len(L))

Python: q = int(input())
for i in range(q):
    x = input()
    y = input()
    n = len(x)
    m = len(y)
    d = [[0 for _ in range(m+1)] for _ in range(n+1)]
    for i in range(n):
        for j in range(m):
            if x[i] == y[j]:
                d[i+1][j+1] = d[i][j]+1
            else:
                d[i+1][j+1] = max(d[i+1][j],d[i][j+1])
    print(d[n][m])

Python: from bisect import bisect_left
q = int(input())
for _ in [0]*q:
    s1, s2 = input(), input()
    l1, l2 = len(s1), len(s2)

    p = []
    for i, c in enumerate(s1):
        s = 0
        while True:
            j = s2[s:].find(c)
            if j == -1:
                break
            p.append((i, s+j))
            s += j+1

    lis = []
    for _, y in sorted(p, key=lambda x: (x[0], -x[1])):
        i = bisect_left(lis, y)
        if len(lis) <= i:
            lis.append(y)
        else:
            lis[i] = y
    print(len(lis))

Python: n = int(input())
for _ in range(n):
    a = input()
    b = input()
    na=len(a)
    nb=len(b)
    #array = [[0]*nb for i in range(na)]
    array = [[0 for i in range(nb)] for j in range(na)]
    for i in range(na):
        for j in range(nb):
            c = 0
            if i==0:
                if a[i]==b[j]:
                    array[i][j]=1
            elif j==0:
                if a[i]==b[j]:
                    array[i][j]=1
            else:
                if a[i] == b[j]:
                    c = 1
                array[i][j] = max(
                    array[i-1][j],
                    array[i][j-1],
                    array[i-1][j-1]+c)
    print(array[na-1][nb-1])

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])