Go: package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)
	for i := 0; i < n; i++ {
		x := getNextString(scanner)
		y := getNextString(scanner)

		fmt.Fprintln(writer, lcs(x, y))
	}

	writer.Flush()
}

func lcs(x, y string) int {
	lx := len(x)
	ly := len(y)
	dp := make([][]int, lx+1)
	for i := 0; i <= lx; i++ {
		dp[i] = make([]int, ly+1)
	}
	for i := 0; i < lx; i++ {
		for ii := 0; ii < ly; ii++ {
			if x[i] == y[ii] {
				dp[i+1][ii+1] = dp[i][ii] + 1
				continue
			}
			dp[i+1][ii+1] = dp[i][ii+1]
			if dp[i+1][ii] > dp[i+1][ii+1] {
				dp[i+1][ii+1] = dp[i+1][ii]
			}
		}
	}
	return dp[lx][ly]
}

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

Python: import sys

def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    len1 = len(s1)
    len2 = len(s2)
    if len1 == 0 or len2 == 0:
        return 0

    primary = [0] * len1
    secondary = [0] * len1

    for i in range(len2):
        for j in range(len1):
            if s1[j] == s2[i]:
                match = 1
            else:
                match = 0
            if j == 0:
                secondary[j] = max(primary[j], match)
            else:
                sc1, p1, p2 = secondary[j-1], primary[j-1] + match, primary[j]
                if sc1 > p1:
                    if p1 > p2:
                        secondary[j] = sc1
                    elif p2 > sc1:
                        secondary[j] = p2
                    else:
                        secondary[j] = sc1
                else:
                    if sc1 > p2:
                        secondary[j] = p1
                    elif p1 > p2:
                        secondary[j] = p1
                    else:
                        secondary[j] = p2
                # secondary[j] = max(secondary[j-1], primary[j],
                #                    primary[j-1] + match)

        primary, secondary = secondary, primary

    return primary[len1-1]


def run():
    input()
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, len(s), 2):
        print(len_lcs(s[i], s[i+1]))


if __name__ == '__main__':
    run()