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: for _ in[0]*int(input()):
 X,Y,z=input(),input(),[]
 for y in Y:
  s=0
  for i,k in enumerate(z):
   t=X.find(y,s)+1
   if t<1:break
   if t<k:z[i]=t
   s=k
  else:
   t=X.find(y,s)+1
   if t:z+=[t]
 print(len(z))

Python: # dpテーブル生成
def gen_dp(row, col):
  print('row: {}'.format(row))
  print('col: {}'.format(col))
  print('----------')
  return [[0]*col for i in range(row)]
#dpテーブル表示
def show_dp(table):
  for line in range(len(table)):
    print(table[line])
  print('----------')

def solver(str_1 ,str_2):
  # テーブル生成
  dp = gen_dp(len(str_2) + 1, len(str_1) + 1)
  for r in range(len(str_2)):
    for c in range(len(str_1)):
      print('[str_2]:{}, [str_1]:{}'.format(r + 1, c + 1))
      # 末尾の文字が一致していれば
      if str_2[r] == str_1[c]:
        dp[r + 1][c + 1] = dp[r][c] + 1
      # 末尾の文字が違えば
      else:
        dp[r + 1][c + 1] = max(dp[r + 1][c], dp[r][c + 1])
      show_dp(dp)
  return dp[len(str_2)][len(str_1)]

# 実行
n = int(input())
for _ in range(n):
  str_1 = input()
  str_2 = input()
  print(solver(str_1, str_2))

Python: i=input
for _ in[0]*int(i()):
 X,z=i(),[]
 for y in i():
  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: def gen_dp(row, col):
  return [[0]*col for i in range(row)]

def solver(str_1 ,str_2):
  dp = gen_dp(len(str_2) + 1, len(str_1) + 1)
  for r in range(len(str_2)):
    for c in range(len(str_1)):
      if str_2[r] == str_1[c]:
        dp[r + 1][c + 1] = dp[r][c] + 1
      else:
        dp[r + 1][c + 1] = max(dp[r + 1][c], dp[r][c + 1])
  return dp[len(str_2)][len(str_1)]

n = int(input())
for _ in range(n):
  str_1 = input()
  str_2 = input()
  print(solver(str_1, str_2))

Python: q = int(input())
 
def lcss(x,y):
     
    lcs = [0]*(len(x)+1)
    for i in range(len(y)):
        w1 = y[i]
        lcs_2 = lcs[:]
        for j in range(len(x)):
            if x[j] == w1:
                lcs[j+1] = lcs_2[j] + 1  
            elif lcs[j+1] < lcs[j]:
                lcs[j+1] = lcs[j]
    return lcs[-1]
 
for i in range(q):
    x = input()
    y = input()
    print(lcss(x,y))

Python: def main():
    n=int(input())
    result=[]
    for i in range(n):
        a=input()
        b=input()
        array=[[1 for i in range(len(a))] for j in range(len(b))]
        for i in range(1,len(a)):
            for j in range(1,len(b)):
                c=0
                if a[j] == b[i]:
                    c=1
                array[i][j]=max(array[i-1][j],array[i][j-1],array[i-1][j-1]+c)
        result.append(array[len(a)-1][len(b)-1])
    for i in result:
        print(i)
if __name__ == "__main__":
    main()

Python: pcsl = [[0] * 1001] * 1001

def lcs(x, y):
    m = len(x)
    n = len(y)
    for i in range(m):
        for j in range(n):
            if x[i] == y[j]:
                pcsl[i][j] = pcsl[i - 1][j - 1] + 1
            elif pcsl[i - 1][j] > pcsl[i][j - 1]:
                pcsl[i][j] = pcsl[i - 1][j]
            else:
                pcsl[i][j] = pcsl[i][j - 1]
    print(pcsl[i][j])


q = int(input())

for i in range(q):
    ax = input()
    ay = input()
    lcs(ax, ay)

Python: def num_substr(s, t):
    dp = {}
    for i in range(len(s) + 1):
        dp[i] = {0: 0}
    for j in range(len(t) + 1):
        dp[0][j] = 0
    
    for i in range(1,len(s)+1):
        Flag=False
        for j in range(1,len(t)+1):
            d=1 if s[i-1] == t[j-1] and dp[i-1][j-1] == dp[i][j-1] else 0
            dp[i][j] = max(dp[i-1][j] ,
                           dp[i][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: # Longest Common Subsequence problem: LCS
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/10/ALDS1_10_C

import sys
input = sys.stdin.readline
ascii_letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'


def get_LCS(x: str, y: str):
    lx = len(x)
    ly = len(y)
    dp = [[0] * (lx + 1) for _ in range(ly + 1)]  # 1-indexed

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

    return dp[-1][-1]


def llcs(x, y):
    """solution author: bs5lNkJ"""
    pm = dict((zip(ascii_letters, [0] * 52)))
    for c in pm:
        for i, xc in enumerate(x):
            if c == xc:
                pm[c] |= (1 << i)

    V = (1 << len(x)) - 1

    for yc in y:
        V = ((V + (V & pm[yc])) | (V & ~pm[yc]))

    ans = bin(V)[-len(x):].count('0')

    return ans


n = int(input())

for _ in range(n):
    X = input().strip()
    Y = input().strip()
    print(llcs(X, Y))

Python: for _ in[0]*int(input()):
 X,Y,z=input(),input(),[]
 for y in Y:
  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: global memo
global ans

def judge_dup(list1,list2):#list1とlist2に共通した要素がある場合は１、ない場合は０
    tmp_list1=list(set(list1))
    tmp_list2=list(set(list2))
    judge=tmp_list1 + tmp_list2
    if(len(tmp_list1) + len(tmp_list2) == len(set(judge))):
        return 0
    else:
        return 1


def longest_common(data1,ind1,data2,ind2):
    #data1[ind1],data2[ind2]を先頭とする２つの部分文字列の最長common文字列の長さを返す
    if(len(data1) <=ind1 or len(data2) <=ind2):
        return 0
    if(memo[ind1][ind2]!=-1):
        return memo[ind1][ind2]

    tmp_data1=data1[ind1:]
    tmp_data2=data2[ind2:]
    tmp_max=0
    for i in range(len(tmp_data1)):
        x=tmp_data1[i]
        for j in range(len(tmp_data2)):
            if(x==tmp_data2[j]):
                if(judge_dup(tmp_data1[:i],tmp_data2[:j])==0):
                    #注目する文字以前に共通する文字があったら調査する意味なし
                    tmp = longest_common(data1,ind1+i+1,data2,ind2+j+1)
                    if(tmp_max < tmp +1):
                        tmp_max=tmp+1
                break
    
    memo[ind1][ind2]=tmp_max
    global ans
    if(ans < tmp_max):
        ans =tmp_max
    return tmp_max
            
    






                





n=int(input())


for loop in range(n):
    ans=0
    data1=input()
    data2=input()
    data1=list(data1)
    data2=list(data2)

    memo=[[-1]*len(data2) for i in range(len(data1))]
#memo[n][m]は、data1[n]、data2[m]それぞれを先頭とする
#部分文字列の最長common文字列の長さを格納する
    longest_common(data1,0,data2,0)
    print(ans)