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: def lcs(str1, str2):
    lcslist = []
    for s in str2:
        m = n = 0
        for index in lcslist:
            t = str1.find(s, m) + 1
            if t <= 0:
                break
            elif t < index:
                lcslist[n] = t
            m = index
            n += 1
        else:
            t = str1.find(s, m) + 1
            if t > 0:
                lcslist.append(t)
    return len(lcslist)

if __name__ == '__main__':
    n = int(input())
    for i in range(n):
        str1 = input()
        str2 = input()
        print(lcs(str1, str2))

Python: q = int(input())

for k in range(q):
    x = list(input())
    y = list(input())
    lcs = [[0 for i in range(len(x)+1)] for j in range(len(y)+1)]
    for i in range(1,len(y) + 1):
        for j in range(1,len(x) + 1):
            if x[j-1] != y[i-1]:
                lcs[i][j] = max(lcs[i][j-1],lcs[i-1][j])
            else:
                lcs[i][j] = lcs[i-1][j-1] + 1
    print(lcs[len(y)][len(x)])

Python: def edit_distance(s, t):
 s = raw_input()
 t = raw_input()
 dp = {}
 for i in range(len(s) + 1):
  dp[i] = {0: i}
 for j in range(len(t) + 1):
  dp[0][j] = j
 for i in range(1, len(s) + 1):
  for j in range(1, len(t) + 1):
   if (s[i-1] == t[j-1]): 
    d = 0
   else:
    dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + d)
 return dp[len(s)][len(t)]

Python: def calc(x,y):
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        dp2 = dp1[:]
        for j in range(m):
            if x[i] == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    return dp1[-1]

q = int(input())
for i in range(q):
    x = input()
    y = input()
    print(calc(x,y))

Python: import sys


n = int(input())

primary = [0] * 1000
secondary = [0] * 1000


for i in range(n):
    s1 = sys.stdin.readline().strip()
    s2 = sys.stdin.readline().strip()

    len1 = len(s1)
    len2 = len(s2)

    for i in range(len1):
        primary[i] = 0
        secondary[i] = 0

    for i in range(len2):
        for j in range(len1):
            if s1[j] == s2[i]:
                matched = 1
            else:
                matched = 0

            if j == 0:
                secondary[j] = matched
            else:
                sc0 = secondary[j-1]
                pr0 = primary[j-1] + matched
                pr1 = primary[j]
                if sc0 > pr0:
                    if pr0 > pr1:
                        secondary[j] = sc0
                    elif sc0 > pr1:
                        secondary[j] = sc0
                    else:
                        secondary[j] = pr1
                else:
                    if sc0 > pr1:
                        secondary[j] = pr0
                    elif pr0 > pr1:
                        secondary[j] = pr0
                    else:
                        secondary[j] = pr1

        primary, secondary = secondary, primary

    print(primary[len1-1])

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

Python: def solve():
    n = int(input())
    dp = [[0] * 1005 for _ in range(1005)]
    for _ in range(n):
        x = input()
        y = input()
        len_x = len(x)
        len_y = len(y)
        for i in range(len_x):
            for j in range(len_y):
                if x[i] == y[j]:
                    dp[i + 1][j + 1] = dp[i][j] + 1
                else:
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
        print(dp[len_x][len_y])
solve()

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

Python: def num_substr(s, t):
    sl = len(s)
    tl = len(t)
    dp = {}
    for i in range(sl + 1):
        dp[i] = {0: 0}
    for j in range(sl + 1):
        dp[0][j] = 0
     
    for i in range(1,sl+1):
        si_1 = s[i-1]
        dpi = dp[i]
        dpi_1 = dp[i-1]
        for j in range(1,tl+1):
            d=1 if si_1 == t[j-1] and dpi_1[j-1] == dpi[j-1] else 0
            dp[i][j] = max(dpi_1[j] ,
                           dpi[j-1] +d)
    return dp[len(s)][len(t)]
 
n = int(input())
for i in range(n):
    s = input()
    t = input()
    print(num_substr(s,t))

Python: def lcs(X,Y):
    p=len(X)
    q=len(Y)
    Z=[[0 for i in range(q+1)]for j in range(p+1)]
    for i in range(p):
        for j in range(q):
            if X[i]==Y[j]:
                Z[i+1][j+1]=Z[i][j]+1
            else:
                if Z[i][j+1]>Z[i+1][j]:
                    Z[i+1][j+1]=Z[i][j+1]
                else:
                    Z[i+1][j+1]=Z[i+1][j]
    return Z[p][q]

n=int(input())
a=[0 for i in range(n)]
for i in range(n):
    X=input()
    Y=input()
    a[i]=lcs(X,Y)
for i in range(n):
       print(a[i])

Python: #!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
import re
import math
import collections
import itertools
import functools

DEBUG = True
DEBUG = False

def dbg(*args):
    if DEBUG:
        print("DBG: ", file=sys.stderr, end="")
        print(*args, file=sys.stderr)

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

def solve(x, y):
    m = len(x)
    n = len(y)

    for i in range(m+1):
        dp[i][0] = 0
    for j in range(n+1):
        dp[0][j] = 0

    for i in range(1, m+1):
        for j in range(1, n+1):
            if x[i-1] == y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

def main():
    n = int(input())

    for _ in range(n):
        x = input()
        y = input()
        dbg(x, y)

        lcs_len = solve(x, y)
        print(lcs_len)

if __name__ == "__main__": main()