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: def main():
    num = int(stdin.readline())
 
    for _ in xrange(num):
        x = stdin.readline().rstrip()
        y = stdin.readline().rstrip()
 
        n = len(y) + 1
 
        cim1 = [0] * n
        for i, xi in enumerate(x, start=1):
            ci = [0] * n
            for j, yj in enumerate(y, start=1):
                if xi == yj:
                    ci[j] = cim1[j-1] + 1
                elif cim1[j] >= ci[j-1]:
                    ci[j] = cim1[j]
                else:
                    ci[j] = ci[j-1]
            cim1 = ci

Python: import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7


def lcs(s1, s2):##
	dp = []
	for s2_k in s2:
		bgn_idx = 0
		for i, cur_idx in enumerate(dp):
			chr_idx = s1.find(s2_k, bgn_idx) + 1
			if not chr_idx:
				break
			dp[i] = min(cur_idx, chr_idx)
			bgn_idx = cur_idx
		else:
			chr_idx = s1.find(s2_k, bgn_idx) + 1
			if chr_idx:
				dp.append(chr_idx)
	return len(dp)

q = INT()

for _ in range(q):
	S = input()
	T = input()
	print(lcs(S, T))

Python: import sys

c = [[0 for _ in range(1001)] for _ in range(1001)]
for _ in range(int(sys.stdin.readline())):
    x = sys.stdin.readline().rstrip()
    y = sys.stdin.readline().rstrip()
    c[0][0]=0
    for i,xi in enumerate(x):
        for j,yj in enumerate(y):
            if xi==yj:
                c[i+1][j+1] = c[i][j]+1
            elif c[i][j+1] > c[i+1][j]:
                c[i+1][j+1] = c[i][j+1]
            else:
                c[i+1][j+1] = c[i+1][j]
            
    print(c[len(x)][len(y)])

Python: # ライブラリのインポート
#import re #正規表現
import sys
#import heapq
#import collections
#import math

def main():
    q = int(input())
    STR = [str.strip("\n") for str in sys.stdin]
    for i in range(q):
        x = STR[2*i]
        y = STR[2*i+1]
        print(lcs(x,y))


def lcs(x, y):
    dp = []
    for y_k in y:
        ps = 0
        for i, pdp in enumerate(dp):
            p = x.find(y_k, ps) + 1 #.find method returns -1 if there is no element
            if not p: break
            dp[i] = min(p,pdp)
            ps = pdp
        else: #else block is executed when for block has done completedly
            p = x.find(y_k, ps) + 1
            if p: dp.append(p)
    return len(dp)


if __name__ == '__main__':
    main()

Python: n = int(input())
for i in range(n):
    a = input()
    b = input()
    L = [[0 for j  in range(len(a) + 1)] for k in range(len(b) + 1)]
    for  m in range(1, len(a) + 1):
        for n in range(1, len(b) + 1):
            if a[m-1] == b[n-1]:
                L[n][m] = L[n-1][m-1] + 1
            else:
                L[n][m] = max(L[n-1][m], L[n][m-1])
    print(L[-1][-1])

Python: from typing import List


def compute_lcs(x_str: str, y_str: str) -> int:
    if len(x_str) <= len(y_str):
        shorter_str, longer_str = x_str, y_str
    else:
        shorter_str, longer_str = y_str, x_str

    lcs_idx: List[int] = []
    for s_ch in shorter_str:
        l_bgn_idx = 0
        for i, l_cur_idx in enumerate(lcs_idx):
            l_idx = longer_str.find(s_ch, l_bgn_idx)
            if -1 == l_idx:
                break
            lcs_idx[i] = min(l_cur_idx, l_idx)
            l_bgn_idx = l_cur_idx + 1  # Move to the next ch.
        l_idx = longer_str.find(s_ch, l_bgn_idx)
        if -1 != l_idx:
            lcs_idx.append(l_idx)
    return len(lcs_idx)


if __name__ == "__main__":
    num_pairs = int(input())

    for _ in range(num_pairs):
        x_str = input()
        y_str = input()
        lcs = compute_lcs(x_str, y_str)
        print(f"{lcs}")

Python: 
n=int(input())
cnt=[]
for k in range(n):
    a=input()
    b=input()
    lc=[[0 for j in range(len(b)+1)]for i in range(len(a)+1)]
    for i in range(len(a)):
        for j in range(len(b)):
            if a[i]==b[j]:
                lc[i+1][j+1]=lc[i][j]+1
            else:
                if lc[i][j+1]>lc[i+1][j]:
                    lc[i+1][j+1]=lc[i][j+1]
                else:
                    lc[i+1][j+1]=lc[i+1][j]
    cnt.append(lc[-1][-1])
for i in range(len(cnt)):
    print(cnt[i])