Go: package main

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

// define
var (
	sc = bufio.NewScanner(os.Stdin)
)

func bordersInt(in_map [][]int, invalid int) [][]int{
	H, W := len(in_map), len(in_map[0])
	out_map := make([][]int, H+2)
	for h:=0; h<H+2; h++ {
		out_map[h] = make([]int, W+2)
		for w:=0; w<W+2; w++ {
			out_map[h][w] = invalid
		}
	}
	for h:=0; h<H; h++{
		for w:=0; w<W; w++{
			out_map[h+1][w+1] = in_map[h][w] 
		}
	}
	return out_map
}

func bordersString(in_map [][]string, invalid string) [][]string{
	H, W := len(in_map), len(in_map[0])
	out_map := make([][]string, H+2)
	for h:=0; h<H+2; h++ {
		out_map[h] = make([]string, W+2)
		for w:=0; w<W+2; w++ {
			out_map[h][w] = invalid
		}
	}
	for h:=0; h<H; h++{
		for w:=0; w<W; w++{
			out_map[h+1][w+1] = in_map[h][w] 
		}
	}
	return out_map
}

func scanIntLine(len int) []int{
	arr := make([]int, len)
	for i:=0; i<len; i++{
		sc.Scan()
		tmp, err := strconv.Atoi(sc.Text())
		if err == nil{
			arr[i] = tmp
		}
	}
	return arr
}

func scanStringLine(len int) []string{
	arr := make([]string, len)
	for i:=0; i<len; i++{
		sc.Scan()
		arr[i] = sc.Text()
	}
	return arr
}

func scanIntSplit(len int) []int{
	arr := make([]int, len)
	sc.Scan()
	for i, v := range strings.Split(sc.Text(), " "){
		tmp, err := strconv.Atoi(v)
		if err == nil{
			arr[i] = tmp
		}
	}
	return arr
}

func maxInt(args... int) int{
	sort.Ints(args)
	return args[len(args)-1]
}

func main(){
	buf := make([]byte, 0)
    sc.Buffer(buf, 1000000009)
	var n int 
	fmt.Scan(&n)
	dp := make([][]int, 1003)
	for i:=0; i<1003; i++ {
		dp[i] = make([]int, 1003)
	}
	input_lines := scanStringLine(2*n)
	for i:=0; i<n; i++ {
		S, T := input_lines[2*i], input_lines[2*i+1]
		lenS, lenT := len(S), len(T)
		for i:=1; i<lenS+1; i++ {
			for j:=1; j<lenT+1; j++ {
				if S[i-1] == T[j-1] {
					dp[i][j] = dp[i-1][j-1]+1
				} else if S[i-1] != T[j-1] && dp[i-1][j] > dp[i][j-1] {
					dp[i][j] = dp[i-1][j]
				} else {
					dp[i][j] = dp[i][j-1]
				}
				// if S[i-1] == T[j-1] {
				// 	dp[i][j] = maxInt(dp[i-1][j-1]+1, dp[i-1][j], dp[i][j-1])
				// } else {
				// 	dp[i][j] = maxInt(dp[i-1][j], dp[i][j-1])
				// }
			}
		}
		fmt.Println(dp[lenS][lenT])
	}
}

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])

Python: #!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys


def lcs(A, B):
    m, n = len(A), len(B)
    count_list = tuple([[0] * (n + 1) for _ in range(m + 1)])

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                count_list[i][j] = count_list[i - 1][j - 1] + 1
            else:
                count_list[i][j] = max(count_list[i - 1][j], count_list[i][j - 1])

    return count_list[m][n]


def lcs_recursive(A, B, m, n):
    if m == 0 or n == 0:
        return 0
    elif A[m - 1] == B[n - 1]:
        return 1 + lcs_recursive(A, B, m - 1, n - 1)
    else:
        return max(lcs_recursive(A, B, m, n - 1), lcs_recursive(A, B, m - 1, n))


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num
    # for k in range(0, len(word_list), 2):
    #     print(lcs(word_list[k].strip(), word_list[k + 1].strip()))

    for pair in zip(word_list[::2], word_list[1::2]):
        w1, w2 = map(lambda x: x.strip(), pair)
        l1, l2 = len(w1), len(w2)
        print(lcs_recursive(w1, w2, l1, l2))

Python: def L_common(str1,str2):
    d = [0 for i in range(len(str2)+1)]
    
    for n1 in str1:
        tmp = d[:]
        for (j,n2) in enumerate(str2):
            if n1 == n2:
                d[j+1] = tmp[j]+1
            elif d[j+1]<d[j]:
                d[j+1] = d[j]
    return d[len(str2)]

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

for i in stock:
    print(i)

Python: n=int(input())

for i in range(n):
    a=list(input())
    b=list(input())

    r=[[0 for j in range(len(b)+1)]for i in range(len(a)+1)]

    for j in range(1,len(a)+1):
        for k in range(1,len(b)+1):
            c=max(r[j-1][k-1],r[j-1][k],r[j][k-1])
            if a[j-1]==b[k-1]:
                c=max(r[j-1][k-1]+1,r[j-1][k],r[j][k-1])
            
            r[j][k]=c
  
    
    print(r[len(a)][len(b)])