Go: package main

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

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func lcs(a, b string) int {
	lenA := len(a)
	lenB := len(b)
	dp := make([][]int, lenA+1)
	for i := range dp {
		dp[i] = make([]int, lenB+1)
	}

	for i := 1; i <= lenA; i++ {
		for j := 1; j <= lenB; j++ {
			if a[i-1] == b[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = max(dp[i][j-1], dp[i-1][j])
			}
		}
	}
	return dp[lenA][lenB]
}

func main() {
	n := scanInt()
	w := bufio.NewWriter(os.Stdout)
	for i := 0; i < n; i++ {
		a := scanString()
		b := scanString()
		fmt.Fprintln(w, lcs(a, b))
	}
	w.Flush()
}

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

Python: def length_of_lcs(x, y):
    n = len(y)
    #pre_row = [0] * (n + 1)
    cur_row = [0] * (n + 1)
    for x_c in x:
        prev_row = cur_row[:]
        for j, y_c in enumerate(y):
            if x_c == y_c:
                cur_row[j+1] = prev_row[j] + 1
            elif cur_row[j] > cur_row[j+1]:
                cur_row[j+1] = cur_row[j]

    return cur_row[n]


if __name__ == '__main__':
    N = int(input())
    for _ in range(N):
        x = input()
        y = input()
        print(length_of_lcs(x, y))

Python: def lcs(X, Y):
    dp = []
    for y in Y:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = X.find(y, bgn_idx) + 1
            
            if not chr_idx:
                break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = X.find(y, bgn_idx) + 1
            if chr_idx:
                dp.append(chr_idx)
    return len(dp)

q = int(input())
for i in range(q):
    X = input()
    Y = input()
    print(lcs(X, Y))

Python: import sys
sys.setrecursionlimit(10000)

def calc(x,y):
    i = len(x)
    j = len(y)
    if not d[i][j] == None:
        return d[i][j]
    else:
        if x[-1] == y[-1]:
            tmp = max(calc(x[:-1],y[:-1])+1,calc(x[:-1],y),calc(x,y[:-1]))
            d[i][j] = tmp
            return tmp
        else:
            tmp = max(calc(x[:-1],y),calc(x,y[:-1]))
            d[i][j] = tmp
            return tmp
        
q = int(input())
for i in range(q):
    x = input()
    y = input()
    d = [[0 if i == 0 or j == 0 else None for i in range(len(y)+1)] for j in range(len(x)+1)]
    print(calc(x,y))

Python: # -*- coding: utf-8 -*-
"""
Created on Fri May  4 20:33:37 2018
ALDS1_10_C
@author: maezawa
"""

def longest(x, y):
    m = len(x)
    n = len(y)
    c = [[0 for _ in range(n+1)] for _ in range(m+1)]
    for i in range(m):
        for j in range(n):
            #print(i,j)
            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])
    return c[m-1][n-1]

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

Python: def longest_common_subsequence(X, Y):
    X = " " + X
    Y = " " + Y

    length_X = len(X)
    length_Y = len(Y)

    c = [0] * length_Y

    for i in range(1, length_X):
        
        c_ = c[:]

        for j in range(1, length_Y):
            if X[i] == Y[j]:
                c[j] = c_[j - 1] + 1
            elif c_[j] < c[j - 1]:
                c[j] = c[j - 1]

    return c[-1]


q = int(input())


for _ in range(q):

    X = input()
    Y = input()

    print(longest_common_subsequence(X, Y))

Python: n=int(input())
ans=[]
for k in range(n):
    s1=input()
    s2=input()
    dp=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)]
    for i in range(1,len(s1)+1):
        for j in range(1,len(s2)+1):
            if s1[i-1]==s2[j-1]:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])


    ans.append(dp[len(s1)][len(s2)])
for a in ans:
    print(a)

Python: for _ in[0]*int(input()):
 X,Y=' '+input(),' '+input()
 m,n=len(X),len(Y)
 c=[[0]*n for _ in[0]*m]
 print(c)
 for i in range(1,m):
  for j in range(1,n):c[i][j]=(max(c[i-1][j],c[i][j-1]),1+c[i-1][j-1])[X[i]==Y[j]]
 print(c[m-1][n-1])

Python: # -*- coding: utf-8 -*-
"""
Created on Fri May  4 20:33:37 2018
ALDS1_10_C
@author: maezawa
"""

def longest(x, y):
    m = len(x)
    n = len(y)
    c = [[0 for _ in range(n+1)] for _ in range(m+1)]
    for i in range(m):
        for j in range(n):
            #print(i,j)
            if x[i] == y[j]:
                c[i][j] = c[i-1][j-1] + 1
            elif c[i-1][j] >= c[i][j-1]:
                c[i][j] = c[i-1][j]
            else:
                c[i][j] = c[i][j-1]
    return c[m-1][n-1]
                
    

q = int(input())

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

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 Ics(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)

    for i in range(a):
        d = x[i]
        c2 = c1[:]
        for j in range(n):
            if d == y[j]:
                c1[j + 1] = c2[j] + 1
            elif c1[j + 1] < c1[j]:
                c1[j + 1] = c1[j]
    return c1[-1]

q = int(input().rstrip())
r = []
for k in range(q):
    s1 = input().rstrip()
    s2 = input().rstrip()
    r.append(Ics(s1, s2))

print(*r, sep = "/n")

Python: n = int(input())
dataset = []
for i in range(n):
    x = input()
    y = input()
    dataset.append([x,y])

for data in dataset:
    m = len(data[0])
    n = len(data[1])
    dp = []
    for x in range(n+1):
        dp.append([0] *(m+1))

    for j in range(n):
        for i in range(m):
            if data[0][i] == data[1][j]:
                dp[j+1][i+1] = dp[j][i] + 1
            elif dp[j+1][i]>dp[j][i+1]:
                dp[j+1][i+1] = dp[j+1][i] 
            else:
                dp[j+1][i+1] = dp[j][i+1]

    print(dp[n][m])

Python: def lcs(X, Y):
    row, colums = len(X) + 1, len(Y) + 1
    lcs_list = [[0] * colums for x in range(row)]
    for i in range(row):
        for j in range(colums):
            if i == 0 or j == 0:
                lcs_list[i][j] = 0
            elif X[i-1] == Y[j-1]:
                lcs_list[i][j] = lcs_list[i-1][j-1] + 1
            else:
                lcs_list[i][j] = max(lcs_list[i][j-1], lcs_list[i-1][j])
    return lcs_list[-1][-1]

import sys
n = int(input())
strs = [list(val) for val in sys.stdin.read().splitlines()]
result = [lcs(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")

Python: from collections import defaultdict


def lcs(x, y):
    dp = [defaultdict(int) for _ in range(len(x) + 1)]
    dp[0] = [0]*(len(y) + 1)
    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])
    return dp[len(x)][len(y)]


N = int(input())
for _ in range(N):
    x = input()
    y = input()
    print(lcs(x, y))