Go: package main

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

func max(x, y int) int {
	if x < y {
		return y
	} else {
		return x
	}
}

/*********************************************************************
長さmの列X_(m)と長さnの列Y_(n)の最長共通部分列LCSは、
	(1)X[m] == Y[n]ならば、X_(m-1)とY_(n-1)のLCSにX[m]を繋げたもの
	(2)X[m] != Y[n]ならば、X_(m-1)とY_(n)のLCSもしくはX_(m)とY_(n-1)のLCS
	のいずれかのうち長い方

c[m+1][n+1]：c[i][j]にX_(i)とY_(j)のLCSの長さを格納する二次元配列
*********************************************************************/

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	n, _ := strconv.Atoi(scanner.Text())
	for i := 0; i < n; i++ {
		scanner.Scan()
		s1 := scanner.Text()
		scanner.Scan()
		s2 := scanner.Text()
		s1, s2 = " " + s1 , " " + s2
		c := make([][]int, len(s1))
		for i := range c {
			c[i] = make([]int, len(s2))
		}

		LCS := 0

		for i := 1; i < len(s1); i++ {
			for j := 1; j < len(s2); j++ {
				if s1[i] == s2[j] {
					c[i][j] = c[i-1][j-1] + 1
				} else {
					c[i][j] = max(c[i-1][j], c[i][j-1])
				}
				LCS = max(LCS, c[i][j])
			}
		}
		fmt.Println(LCS)
	}
}

Python: N = int(input())

for _ in range(N):
    x = input()
    y = input()
    m, n = len(x), len(y)
    dp = [[0 for i in range(n+1)] for j in range(m+1)]
    
    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][j-1], dp[i-1][j])
                
    print(dp[m][n])

Python: q = int(input())

for i 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-1][j-1],lcs[i][j-1],lcs[i-1][j])
            else:
                lcs[i][j] = max(lcs[i-1][j-1] + 1,lcs[i][j-1],lcs[i-1][j])
    print(lcs[i][j])

Python: import bisect
import collections
import heapq
import itertools
import operator
import sys

def lcs(x, y):
    dp = [[0] * 1010 for _ in range(1010)]
    for i, c in enumerate(y):
        if c == x[0]:
            dp[0][i] = 1
    for i, c in enumerate(x):
        if c == y[0]:
            dp[i][0] = 1
    for i in range(len(x)):
        for j in range(len(y)):
            if x[i] == y[j]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
    return dp[len(x)-1][len(y)-1]

def main():
    n = int(sys.stdin.readline())
    for _ in range(n):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print(lcs(x, y))


if __name__ == '__main__':
    main()

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):
        si_1 = s[i-1]
        dpi = dp[i]
        dpi_1 = dp[i-1]
        for j in range(1,len(t)+1):
            d=1 if si_1 == t[j-1] and dpi_1[j-1] == dpi[j-1] else 0
            dpi[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: q = int(input())

for i in range(q):
    X = input()
    Y = input()
    x = len(X)
    y = len(Y)
    X = ' ' + X
    Y = ' ' + Y
    dp = [[None] * (y + 1)] * (x + 1)
    for i in range(1, x+1):
        dp[i][0] = 0
    for i in range(1, y+1):
        dp[0][i] = 0
    for j in range(1, x + 1):
        for k in range(1, y + 1):
            if X[j - 1] == Y[k - 1]:
                dp[j][k] = dp[j - 1][k - 1] + 1
            else:
                dp[j][k] = max(dp[j - 1][k],dp[j][k - 1])
    print(dp[x][y])

Python: #
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    Q=I()
    for _ in range(Q):
        S=ST()
        T=ST()[::-1]
        lis = []
        find, append = T.find, lis.append

        for c in S:
            i = find(c)+1
            while i:
                j = bisect_left(lis, -i)
                if j >= len(lis):
                    append(-i)
                else:
                    lis[j] = -i
                i = find(c, i)+1
        print(len(lis))
if __name__ == '__main__':
    main()

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(m+1)] for _ in range(n+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 lcs(m,n):
	N=len(n)
	dp=[0]*(N+1)
	for x in m:
		dp_kari=dp[:]
		for j, y in enumerate(n):
			if x==y:
				dp[j+1]=dp_kari[j]+1
			elif dp[j+1]<dp[j]:
				dp[j+1]=dp[j]
	return dp[N]
import sys
for _ in range(int(input())):
	m=sys.stdin.readline().rstrip()
	n=sys.stdin.readline().rstrip()
	print(lcs(m,n))

Python: from string import ascii_letters

def llcs(x, y):
    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

from sys import stdin

def solve():
    file_input == stdin
    q = int(file_input.readline())
    for i in range(q):
        s1 = file_input.readline().rstrip()
        s2 = file_input.readline().rstrip()
        print(llcs(s1, s2))

solve()

Python: q = int(input())
for i in range(q):
    x = input()
    y = input()
    n = len(x)
    m = len(y)
    dp = [0]*((n+1)*(m+1))
    for i in range(n):
        for j in range(m):
            a = (n+1)*(j+1)+i+1
            if x[i] == y[j]:
                b = (n+1)*j+i
                dp[a] = dp[b]+1
            else:
                c = (n+1)*j+i+1
                d = (n+1)*(j+1)+i
                dp[a] = max(dp[c],dp[d])
    print(dp[-1])